文档介绍:Discrete Mathematics 307 (2007) 1754–1766
Using Lagrangians of hypergraphs to find non-jumping numbers(II)
Yuejian Peng
Department of Mathematics and Computer Science, Indiana State University, Terre Haute, IN 47809, USA
Received 7 November 2005; received in revised form 7 September 2006; accepted 7 September 2006
Available online 28 November 2006
Abstract
Let r 2 be an integer. A real number ∈[0, 1) is a jump for r if for any > 0 and any integer mr,anyr-uniform graph with
n>n0(,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˝os, Stone and Simonovits implies that every ∈[0, 1) is a jump for r = 2. Erd˝os asked
whether the same is true for r 3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumping numbers
for every r 3. However, there are a lot of unknowns on determining whether or not a number is a jump for r 3. In this paper, we
find two infinite sequences of non-jumping numbers for r = 4, and extend one of the results to every r 4. Our approach is still
based on the approach developed by Frankl and Rödl.
© 2006 Elsevier . All rights reserved.
Keywords: Erd˝os jumping constant conjecture; Lagrangian of an r-uniform graph; Optimal vector
1. Introduction
For a finite set V and a positive integer r we denote by V the family of all r-subsets of V .Anr-uniform
r
graph G consists of a set V (G) of vertices and a set E(G) ⊆ V (G) of edges. The density of G is defined by
r