Independent sets in hypergraphs with a forbidden link

Abstract

We give a probabilistic construction of 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. We further extend this result to prove tight bounds on various other hypergraph Ramsey numbers.

References in corpus (3)

• Three tutorial lectures on entropy and counting
• Hypergraphs with vanishing Turán density in uniformly dense hypergraphs
• Polynomial to exponential transition in Ramsey theory

Cited by in corpus (3)

• Coloring the normalized Laplacian for oriented hypergraphs
• On ordered Ramsey numbers of tripartite 3-uniform hypergraphs
• Maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs