Search

In 1967 Harary, Hedetniemi, and Prins showed that every graph G admits a complete t -coloring for every t with χ (G) ≤ t ≤ ψ (G) , where χ (G) denotes the chromatic number of G and ψ (G) denotes the achromatic number of G which is the maximum number r for which G admits a complete r -coloring. Recently, Edwards and Rza̧żewski (2020) showed that this result fails for hypergraphs by proving that for every integer k with k ≥ 9 , there exists a k -uniform hypergraph H with a complete χ (H) -coloring and a complete ψ (H) -coloring, but no complete t -coloring for some t with χ (H) < t < ψ (H). They also asked whether there would exist such an example for 3-uniform hypergraphs and posed another problem to strengthen their result. In this paper, we generalize their result to all cases k with k ≥ 3 and settle their problems by giving several examples of 3-uniform hypergraphs. In particular, we disprove a recent conjecture due to Matsumoto and Ohno (2020) who suggested a special family of 3-uniform hypergraph to satisfy the desired interpolation property. [ABSTRACT FROM AUTHOR]

Let G be a t -uniform hypergraph, and let c (G) denote the cyclic index of the adjacency tensor of G. Let m , s be positive integers such that s ≥ 2 and m = s t. The generalized power G m , s of G is obtained from G by blowing up each vertex into an s -set and preserving the adjacency relation. It was conjectured that c (G m , s) = s ⋅ c (G). In this paper, by using a matrix equation over Z m that characterizes the spectral symmetry or cyclic index of an m -uniform hypergraph, we give an equivalent condition for the equality in the conjecture. Finally we show that the conjecture is false by a counterexample. [ABSTRACT FROM AUTHOR]

For two s -uniform hypergraphs H and F , the Turán number e x s (H , F) is the maximum number of edges in an F -free subgraph of H. Let s , r , k , n 1 , ... , n r be integers satisfying 2 ≤ s ≤ r and n 1 ≤ n 2 ≤ ⋯ ≤ n r . De Silva, Heysse and Young determined e x 2 (K n 1 , ... , n r , k K 2) and De Silva, Heysse, Kapilow, Schenfisch and Young determined e x 2 (K n 1 , ... , n r , k K r). In this paper, as a generalization of these results, we consider three Turán-type problems for k disjoint cliques in r -partite s -uniform hypergraphs. First, we consider a multi-partite version of the Erdős matching conjecture and determine e x s (K n 1 , ... , n r (s) , k K s (s) ) for n 1 ≥ s 3 k 2 + s r. Then, using a probabilistic argument, we determine e x s (K n 1 , ... , n r (s) , k K r (s) ) for all n 1 ≥ k. Recently, Alon and Shikhelman determined asymptotically, for all F , the generalized Turán number e x 2 (K n , K s , F) , which is the maximum number of copies of K s in an F -free graph on n vertices. Here we determine e x 2 (K n 1 , ... , n r , K s , k K r) with n 1 ≥ k and n 3 = ⋯ = n r . Utilizing a result on rainbow matchings due to Glebov, Sudakov and Szabó, we determine e x 2 (K n 1 , ... , n r , K s , k K r) for all n 1 , ... , n r with n 4 ≥ r r (k − 1) k 2 r − 2 . [ABSTRACT FROM AUTHOR]