Hypergraphs Do Jump
Top Cited Papers
- 13 July 2010
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 20 (2) , 161-171
Abstract
We say that α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c(α) > 0 such that for all ϵ > 0 and all t ≥ 1, any r-graph with n ≥ n0(α, ϵ, t) vertices and density at least α + ϵ contains a subgraph on t vertices of density at least α + c.The Erdős–Stone–Simonovits theorem [4, 5] implies that for r = 2, every α ∈ [0, 1) is a jump. Erdős [3] showed that for all r ≥ 3, every α ∈ [0, r!/rr) is a jump. Moreover he made his famous ‘jumping constant conjecture’, that for all r ≥ 3, every α ∈ [0, 1) is a jump. Frankl and Rödl [7] disproved this conjecture by giving a sequence of values of non-jumps for all r ≥ 3.We use Razborov's flag algebra method [9] to show that jumps exist for r = 3 in the interval [2/9, 1). These are the first examples of jumps for any r ≥ 3 in the interval [r!/rr, 1). To be precise, we show that for r = 3 every α ∈ [0.2299, 0.2316) is a jump.We also give an improved upper bound for the Turán density of K4− = {123, 124, 134}: π(K4−) ≤ 0.2871. This in turn implies that for r = 3 every α ∈ [0.2871, 8/27) is a jump.Keywords
This publication has 7 references indexed in Scilit:
- On 3-Hypergraphs with Forbidden 4-Vertex ConfigurationsSIAM Journal on Discrete Mathematics, 2010
- Flag algebrasThe Journal of Symbolic Logic, 2007
- A note on the jumping constant conjecture of ErdősJournal of Combinatorial Theory, Series B, 2007
- CSDP, A C library for semidefinite programmingOptimization Methods and Software, 1999
- Hypergraphs do not jumpCombinatorica, 1984
- On some extremal problems on r-graphsDiscrete Mathematics, 1971
- On the structure of linear graphsBulletin of the American Mathematical Society, 1946