Polynomial to exponential transition in Ramsey theory
arXiv:1901.06029 · doi:10.1112/plms.12320
Abstract
Given , let be the minimum such that there exist arbitrarily large -uniform hypergraphs whose independence number is at most polylogarithmic in the number of vertices and in which every vertices span at most edges. Erd\H os and Hajnal conjectured (1972) that can be calculated precisely using a recursive formula and Erd\H os offered $500 for a proof of this. For this has been settled for many values of including powers of three but it was not known for any and . Here we settle the conjecture for all . We also answer a question of Bhat and Rödl by constructing, for each , a quasirandom sequence of -uniform hypergraphs with positive density and upper density at most . This result is sharp.
arXiv comment27 pages
References in corpus (9)
- On the Number of Pentagons in Triangle-Free Graphs
- Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
- Erdos-Szekeres-type theorems for monotone paths and convex bodies
- A Note on the Inducibility of 4-vertex Graphs
- Rainbow triangles in three-colored graphs
- A bound on the inducibility of cycles
- Hypergraphs with vanishing Turán density in uniformly dense hypergraphs
- The inducibility of small oriented graphs
- On high-dimensional acyclic tournaments