2014/04/30 by Qingsong Tang, Xiaojun Lu, Tang, Qingsong +5
Computer Science · Mathematics · #05C35 #05C65 #05D99 #90C27 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1405.2855
openalex publication_date 2014/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is conjectured by Frankl and Füredi that the r-uniform hypergraph with m edges formed by taking the first m sets in the colex ordering of \mathbb N(r) has the largest Lagrangian of all r-uniform hypergraphs with m edges in \citeFF. Motzkin and Straus' theorem confirms this conjecture when r=2. For r=3, it is shown by Talbot in \citeT that this conjecture is true when m is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for r-uniform hypergraphs. As an implication of this connection, we prove that the r-uniform hypergraph with m edges formed by taking the first m sets in the colex ordering of \mathbb N(r) has the largest Lagrangian of all r-uniform graphs with t vertices and m edges satisfying t-1\choose r≤ m ≤ t-1\choose r+ t-2\choose r-1-[(2r-6)×2r-1+2r-3+(r-4)(2r-7)-1](t-2\choose r-2-1) for r≥ 4.