Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-12T01:11:11.678Z Has data issue: false hasContentIssue false

Hypergraphs Do Jump

Published online by Cambridge University Press:  13 July 2010

RAHIL BABER
Affiliation:
Department of Mathematics, UCL, London, WC1E 6BT, UK (e-mail: rahilbaber@hotmail.com, talbot@math.ucl.ac.uk)
JOHN TALBOT
Affiliation:
Department of Mathematics, UCL, London, WC1E 6BT, UK (e-mail: rahilbaber@hotmail.com, talbot@math.ucl.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 nn0(α, ϵ, 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.

Type
Paper
Copyright
Copyright © Cambridge University Press 2010

References

[1]Borchers, B. (1999) CSDP, A C library for semidefinite programming. Optim. Methods Software 11 613623.CrossRefGoogle Scholar
[2]de Caen, D. (1983) Extension of a theorem of Moon and Moser on complete subgraphs. Ars Combinatoria 16 510.Google Scholar
[3]Erdős, P. (1971) On some extremal problems on r-graphs. Discrete Math. 1 16.CrossRefGoogle Scholar
[4]Erdős, P. and Simonovits, M. (1966) A limit theorem in graph theory. Studia Sci. Math. Hung. Acad. 1 5157.Google Scholar
[5]Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 10871091.CrossRefGoogle Scholar
[6]Frankl, P., Peng, Y., Rödl, V. and Talbot, J. (2007) A note on the jumping constant conjecture of Erdős. J. Combin. Theory Ser. B 97 204216.CrossRefGoogle Scholar
[7]Frankl, P. and Rödl, V. (1984) Hypergraphs do not jump. Combinatorica 4 149159.CrossRefGoogle Scholar
[8]Razborov, A. A. (2007) Flag algebras. J. Symbolic Logic 72 12391282.CrossRefGoogle Scholar
[9]Razborov, A. A. (2010) On 3-hypergraphs with forbidden 4-vertex configurations. http://people.cs.uchicago.edu/~razborov/files/turan.pdfCrossRefGoogle Scholar