Independent sets in hypergraphs with a forbidden link. Issue 4 (17th March 2021) - Fox, Jacob; He, Xiaoyu
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.