- Tytuł:
- Subgraph densities in hypergraphs
- Autorzy:
- Peng, Yuejian
- Powiązania:
- https://bibliotekanauki.pl/articles/743780.pdf
- Data publikacji:
- 2007
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Erdös jumping constant conjecture
Lagrangian
optimal vector - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2007, 27, 2; 281-297
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł