pith. sign in

arxiv: 1909.05988 · v2 · pith:ZHLTTRT4new · submitted 2019-09-13 · 🧮 math.CO

Independent sets in hypergraphs with a forbidden link

classification 🧮 math.CO
keywords hypergraphramseytightverticesboundboundsconstructionedges
0
0 comments X
read the original 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\H{o}s and Hajnal in Ramsey theory. We further extend this result to prove tight bounds on various other hypergraph Ramsey numbers.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.