Advances in a Hypergraph Coloring Conjecture

Abstract

We consider a conjecture introduced by Hoppen, Kohayakawa and Lefmann. For fixed positive integers k, q and t with 1 ≤ t < k and a k-uniform hypergraph H, let κ(H, q, t) denote the number of q-colorings of the set of hyperedges of H for which any two hyperedges in the same color class intersect in at least t elements. Consider the function KC(n, k, q, t) = maxH∈Hn κ(H, q, t), where the maximum runs over the family Hn,k of all k-uniform hypergraphs on n vertices. Hoppen, Kohayakawa and Lefmann found the hypergraph H which satisfies κ(H, q, t) = KC(n, k, q, t) when q ≤ 4 or k ≥ 2t − 1. They proposed a conjecture when q ≥ 5 and k < 2t − 1. In this work we proved this conjecture for q ≤ 9.