Independent sets in hypergraphs with a forbidden link

Abstract

We prove that there exists a 3-uniform hypergraph on N vertices with independence number O ( log N / log log N ) in which there are at most two edges among any four vertices. This bound is tight and solves a longstanding open problem of Erdős and Hajnal in Ramsey theory. The proof is based on a carefully designed probabilistic construction and the analysis depends on entropy methods. We further extend this result to prove tight bounds on various other hypergraph Ramsey numbers.

Topics & Concepts