Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: optimal vector

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Subgraph densities in hypergraphs

100%

Peng Y.

Discussiones Mathematicae Graph Theory

2007

tom 27

nr 2

281-297

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Peng Y.

1 2007

Wyniki wyszukiwania

Subgraph densities in hypergraphs