2012/11/29 by Qingsong Tang, Yuejian Peng, Tang, Qingsong +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.1211.7057
openalex publication_date 2012/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1965, Motzkin and Straus [5] provided a new proof of Turan's theorem based on a continuous characterization of the clique number of a graph using the Lagrangian of a graph. This new proof aroused interests in the study of Lagrangians of r-uniform graphs. The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Sidorenko and Frankl-Furedi applied Lagrangians of hypergraphs in finding Turan densities of hypergraphs. Frankl and Rodl applied it in disproving Erdos' jumping constant conjecture. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Furedi conjectured that the r-uniform graph with m edges formed by taking the first m sets in the colex ordering of N^(r) has the largest Lagrangian of all r-uniform graphs with m edges. Talbot in [14] provided some evidences for Frankl and Furedi's conjecture. In this paper, we prove that the r-uniform graph with m edges formed by taking the first m sets in the colex ordering of N^(r) has the largest Lagrangian of all r-uniform graphs on t vertices with m edges when t choose r-3 or t choose r-4. As an implication, we also prove that Frankl and Furedi's conjecture holds for 3-uniform graphs with t choose 3-3 or t choose 3-4 edges.