Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-24T23:51:06.407Z 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: [email protected], [email protected])
JOHN TALBOT
Affiliation:
Department of Mathematics, UCL, London, WC1E 6BT, UK (e-mail: [email protected], [email protected])

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 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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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