<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 3" %>
Using Lagrangians of Hypergraphs to Find Non-Jumping Numbers (I)
Yuejian Peng
Department of Mathematics and Computer Science, Indiana State University, Terre Haute, IN 47809, USA
Annals of Combinatorics 12 (3) pp.307-324 September, 2008
AMS Subject Classification: 05D05, 05C65
Let $r\ge 2$ be an integer. A real number $\alpha\in [0,\,1)$ is a jump for $r$ if for any $\epsilon>0$ and any integer $m$, $m\ge r$, any $r$-uniform graph with $n > n_0(\epsilon,\, m)$ vertices and density at least $\alpha + \epsilon$ contains a subgraph with $m$ vertices and density at least $\alpha + c$, where $c=c(\alpha)$ does not depend on $\epsilon$ or $m$. It follows from a result of Erd\H os, Stone, and Simonovits that every $\alpha\in [0,\, 1)$ is a jump for $r=2$. Erd\H os asked whether the same is true for $r\ge 3$. Frankl and R\"odl gave a negative answer by showing an infinite sequence of non-jumping numbers for $r\ge 3$. However, there are a lot of unknowns on determining whether a number is a jump for $r\ge 3$. In this paper, we first find two infinite sequences of non-jumping numbers for $r=4$, then we extend one of the results to every $r\ge 4$. Our approach is still based on the approach developed by Frankl and R\"odl.
Keywords: extremal problems in combinatorics, Erd\H os jumping constant conjecture, Lagrangians of uniform graphs


1. P. Erdos, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964) 183-–190.

2. P. Erdos and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51-–57.

3. P. Erdos and A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946) 1087-–1091.

4. P. Frankl and Z. F¨uredi, Extremal problems whose solutions are the blow-ups of the small Witt-designs, J. Combin. Theory Ser. A 52 (1) (1989) 129-–147.

5. P. Frankl, Y. Peng, V. R¨odl, and J. Talbot, A note on the jumping constant conjecture of Erdos, J. Combin. Theory Ser. B 97 (2) (2007) 204–-216.

6. P. Frankl and V. R¨odl, Hypergraphs do not jump, Combinatorica 4 (2-3) (1984) 149–-159.

7. G. Katona, T. Nemetz, and M. Simonovits, On a graph problem of Tur´an, Mat. Lapok 15 (1964) 228–-238.

8. T.S. Motzkin and E.G. Straus, Maxima for graphs and a new proof of a theorem of Tur´an, Canad. J. Math. 17 (1965) 533-–540.

9. Y. Peng, Non-jumping numbers for 4-uniform hypergraphs, Graphs Combin. 23 (1) (2007) 97-–110.

10. Y. Peng, Using Lagrangians of hypergraphs to nd non-jumping numbers (II), Discrete Math. 307 (14) (2007) 1754–-1766.

11. J. Talbot, Lagrangians of hypergraphs, Combin. Probab. Comput. 11 (2) (2002) 199–-216.