Abstract
A real number α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c > 0 such that for any ∈ > 0 and any integer m ≥ r, there exists an integer n 0 such that any r-uniform graph with n > n 0 vertices and density ≥ α + ∈ contains a subgraph with m vertices and density ≥ α + c. It follows from a fundamental theorem of Erdös and Stone that every α ∈ [0, 1) is a jump for r = 2. Erdös also showed that every number in [0, r!/r r) is a jump for r ≥ 3 and asked whether every number in [0, 1) is a jump for r ≥ 3 as well. Frankl and Rödl gave a negative answer by showing a sequence of non-jumps for every r ≥ 3. Recently, more non-jumps were found for some r ≥ 3. But there are still a lot of unknowns on determining which numbers are jumps for r ≥ 3. The set of all previous known non-jumps for r = 3 has only an accumulation point at 1. In this paper, we give a sequence of non-jumps having an accumulation point other than 1 for every r ≥ 3. It generalizes the main result in the paper ‘A note on the jumping constant conjecture of Erdös’ by Frankl, Peng, Rödl and Talbot published in the Journal of Combinatorial Theory Ser. B. 97 (2007), 204–216.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Erdös, P.: On extremal problems of graphs and generalized graphs. Israel J. Math. 2, 183–190 (1964)
Erdös, P., Stone, A.H.: On the structure of linear graphs. Bull. Amer. Math. Soc. 52, 1087–1091 (1946)
Frankl, P., Füredi, Z.: Extremal problems whose solutions are the blow-ups of the small Witt-designs. J. Comb. Theory A 52, 129–147 (1989)
Frankl, P., Rödl, V.: Hypergraphs do not jump. Combinatorica 4, 149–159 (1984)
Frankl, P., Peng, Y., Rödl, V., Talbot, J.: A note on the jumping constant conjecture of Erdös. J. Comb. Theory Ser. B. 97, 204–216 (2007)
Katona, G., Nemetz, T., Simonovits, M.: On a graph-problem of Turán. Mat. Fiz. Lapok 48, 436–452 (1941)
Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math 17, 533–540 (1965)
Peng, Y.: Non-jumping numbers for 4-uniform hypergraphs. Graphs Comb. 23, 97–110 (2007)
Peng, Y.: Using Lagrangians of hypergraphs to find non-jumping numbers(I). Ann. Comb. 12(3), 307–324 (2008)
Peng, Y.: Using Lagrangians of hypergraphs to find non-jumping numbers(II). Discrete Math. 307, 1754–1766 (2007)
Peng, Y.: Subgraph densities in hypergraphs. Discuss. Math. Graph Theory 27(2), 281–298 (2007)
Peng, Y.: A note on the structure of Turán densities. Graphs Comb. 24(2), 113–125 (2008)
Peng, Y.: On jumping densities of hypergraphs. Graphs Comb., in press
Peng, Y., Zhao, C.: Generating non-jumping numbers recursively. Discrete Appl. Math. 156(10), 1856–1864 (2008)
Peng, Y., Zhao, C.: On non-strong jumping numbers and density structures of hypergraphs. Discrete Math. 309, 3917–3929 (2009)
Talbot, J.: Lagrangians of hypergraphs. Comb. Prob. Comput. 11, 199–216 (2002)
Turán, P.: On an extremal problem in graph theory. Mat. Fiz. Lapok 48, 436–452 (1941) (in Hungarian)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Peng, Y. On Substructure Densities of Hypergraphs. Graphs and Combinatorics 25, 583–600 (2009). https://doi.org/10.1007/s00373-009-0859-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-009-0859-3