Subgraph densities in hypergraphs

Yuejian Peng

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 2, page 281-297
  • ISSN: 2083-5892

Abstract

top
Let r ≥ 2 be an integer. A real number α ∈ [0,1) is a jump for r if for any ε > 0 and any integer m ≥ r, any r-uniform graph with n > n₀(ε,m) vertices and density at least α+ε contains a subgraph with m vertices and density at least α+c, where c = c(α) > 0 does not depend on ε and m. A result of Erdös, Stone and Simonovits implies that every α ∈ [0,1) is a jump for r = 2. Erdös asked whether the same is true for r ≥ 3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumps for every r ≥ 3. However, there are still a lot of open questions on determining whether or not a number is a jump for r ≥ 3. In this paper, we first find an infinite sequence of non-jumps for r = 4, then extend one of them to every r ≥ 4. Our approach is based on the techniques developed by Frankl and Rödl.

How to cite

top

Yuejian Peng. "Subgraph densities in hypergraphs." Discussiones Mathematicae Graph Theory 27.2 (2007): 281-297. <http://eudml.org/doc/270519>.

@article{YuejianPeng2007,
abstract = {Let r ≥ 2 be an integer. A real number α ∈ [0,1) is a jump for r if for any ε > 0 and any integer m ≥ r, any r-uniform graph with n > n₀(ε,m) vertices and density at least α+ε contains a subgraph with m vertices and density at least α+c, where c = c(α) > 0 does not depend on ε and m. A result of Erdös, Stone and Simonovits implies that every α ∈ [0,1) is a jump for r = 2. Erdös asked whether the same is true for r ≥ 3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumps for every r ≥ 3. However, there are still a lot of open questions on determining whether or not a number is a jump for r ≥ 3. In this paper, we first find an infinite sequence of non-jumps for r = 4, then extend one of them to every r ≥ 4. Our approach is based on the techniques developed by Frankl and Rödl.},
author = {Yuejian Peng},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Erdös jumping constant conjecture; Lagrangian; optimal vector},
language = {eng},
number = {2},
pages = {281-297},
title = {Subgraph densities in hypergraphs},
url = {http://eudml.org/doc/270519},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Yuejian Peng
TI - Subgraph densities in hypergraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 2
SP - 281
EP - 297
AB - Let r ≥ 2 be an integer. A real number α ∈ [0,1) is a jump for r if for any ε > 0 and any integer m ≥ r, any r-uniform graph with n > n₀(ε,m) vertices and density at least α+ε contains a subgraph with m vertices and density at least α+c, where c = c(α) > 0 does not depend on ε and m. A result of Erdös, Stone and Simonovits implies that every α ∈ [0,1) is a jump for r = 2. Erdös asked whether the same is true for r ≥ 3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumps for every r ≥ 3. However, there are still a lot of open questions on determining whether or not a number is a jump for r ≥ 3. In this paper, we first find an infinite sequence of non-jumps for r = 4, then extend one of them to every r ≥ 4. Our approach is based on the techniques developed by Frankl and Rödl.
LA - eng
KW - Erdös jumping constant conjecture; Lagrangian; optimal vector
UR - http://eudml.org/doc/270519
ER -

References

top
  1. [1] D.P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, NY, 1982). Zbl0572.90067
  2. [2] P. Erdös, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964) 183-190, doi: 10.1007/BF02759942. Zbl0129.39905
  3. [3] P. Erdös and M. Simonovits, A limit theorem in graph theory, Studia Sci. Mat. Hung. Acad. 1 (1966) 51-57. 
  4. [4] P. Erdös and A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946) 1087-1091, doi: 10.1090/S0002-9904-1946-08715-7. Zbl0063.01277
  5. [5] P. Frankl and Z. Füredi, Extremal problems whose solutions are the blow-ups of the small Witt-designs, J. Combin. Theory (A) 52 (1989) 129-147, doi: 10.1016/0097-3165(89)90067-8. Zbl0731.05030
  6. [6] P. Frankl and V. Rödl, Hypergraphs do not jump, Combinatorica 4 (1984) 149-159, doi: 10.1007/BF02579215. Zbl0663.05047
  7. [7] P. Frankl, Y. Peng, V. Rödl and J. Talbot, A note on the jumping constant conjecture of Erdös, J. Combin. Theory (B) 97 (2007) 204-216, doi: 10.1016/j.jctb.2006.05.004. Zbl1110.05052
  8. [8] G. Katona, T. Nemetz and M. Simonovits, On a graph problem of Turán, Mat. Lapok 15 (1964) 228-238. Zbl0138.19402
  9. [9] T.S. Motzkin and E.G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math. 17 (1965) 533-540, doi: 10.4153/CJM-1965-053-6. Zbl0129.39902
  10. [10] Y. Peng, Non-jumping numbers for 4-uniform hypergraphs, Graphs and Combinatorics 23 (2007) 97-110, doi: 10.1007/s00373-006-0689-5. Zbl1115.05045
  11. [11] Y. Peng, Using Lagrangians of hypergraphs to find non-jumping numbers (I), submitted. Zbl1201.05101
  12. [12] Y. Peng, Using Lagrangians of hypergraphs to find non-jumping numbers (II), Discrete Math. 307 (2007) 1754-1766, doi: 10.1016/j.disc.2006.09.024. Zbl1128.05029
  13. [13] J. Talbot, Lagrangians of hypergraphs, Combinatorics, Probability & Computing 11 (2002) 199-216, doi: 10.1017/S0963548301005053. Zbl0998.05049

NotesEmbed ?

top

You must be logged in to post comments.