Advances in a Hypergraph Coloring Conjecture

Lucas de Oliveira Contiero, Carlos Hoppen


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.


Extremal Set Theory, Hypergraphs, Colorings.

Texto completo:




  • Não há apontamentos.

SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120

Normas para publicação | Contato