Independent sets in hypergraphs with a forbidden link. Issue 4 (17th March 2021)

• Record Type: Journal Article
• Authors: Fox, Jacob; He, Xiaoyu
• Is Part Of: Proceedings of the London Mathematical Society. Volume 123:Issue 4(2021)
• Page Start: 384
• Page End: 409
• Publication Date: 2021-03-17
• Subjects: 05C55 -- 05C65 -- 05D10 -- 05D40 (primary); Mathematics -- Periodicals; Mathematics; Periodicals; 510
• DOI: 10.1112/plms.12400
• Languages: English
• ISSNs: 0024-6115

Abstract

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.