Abstract
The paper explores the connection of Graph-Lagrangians and its maximum cliques for 3-uniform hypergraphs. Motzkin and Straus showed that the Graph-Lagrangian of a graph is the Graph-Lagrangian of its maximum cliques. This connection provided a new proof of Turán classical result on the Turán density of complete graphs. Since then, Graph-Lagrangian has become a useful tool in extremal problems for hypergraphs. Peng and Zhao attempted to explore the relationship between the Graph-Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range. They showed that if G is a 3-uniform graph with m edges containing a clique of order t − 1, then λ(G) = λ([t − 1](3)) provided \(\left( {\begin{array}{*{20}{c}} {t - 1} \\ 3 \end{array}} \right) \leqslant m \leqslant \left( {\begin{array}{*{20}{c}} {t - 1} \\ 3 \end{array}} \right) + \left( {\begin{array}{*{20}{c}} {t - 2} \\ 2 \end{array}} \right)\). They also conjectured: If G is an r-uniform graph with m edges not containing a clique of order t − 1, then λ(G) < λ([t − 1](r)) provided \(\left( {\begin{array}{*{20}{c}} {t - 1} \\ r \end{array}} \right) \leqslant m \leqslant \left( {\begin{array}{*{20}{c}} {t - 1} \\ r \end{array}} \right) + \left( {\begin{array}{*{20}{c}} {t - 2} \\ {r - 1} \end{array}} \right)\). It has been shown that to verify this conjecture for 3-uniform graphs, it is sufficient to verify the conjecture for left-compressed 3-uniform graphs with \(m = \left( {\begin{array}{*{20}{c}} {t - 1} \\ 3 \end{array}} \right) + \left( {\begin{array}{*{20}{c}} {t - 2} \\ 2 \end{array}} \right)\). Regarding this conjecture, we show: If G is a left-compressed 3-uniform graph on the vertex set [t] with m edges and |[t − 1](3) E(G)| = p, then λ(G) < λ([t− 1](3)) provided \(m = \left( {\begin{array}{*{20}{c}} {t - 1} \\ 3 \end{array}} \right) + \left( {\begin{array}{*{20}{c}} {t - 2} \\ 2 \end{array}} \right)\) and t ≥ 17p/2 + 11.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Frankl, P., Füredi, Z.: Extremal problems whose solutions are the blow-ups of the small Witt-designs. J. Combin. Theory Ser. A, 52, 129–147 (1989)
Frankl, P., Rödl, V.: Hypergraphs do not jump. Combinatorica, 4, 149–159 (1984)
Hefetz, D., Keevash, P.: A hypergraph Turán theorem via lagrangians of intersecting families. J. Combin. Theory Ser. A, 120, 2020–2038 (2013)
Keevash, P.: Hypergrah Turán problems. Surveys in Combinatorics, Cambridge University Press, Oxford city, 2011, 83–140
Motzkin, T. S., Straus, E. G.: Maxima for graphs and a new proof of a theorem of Turán. Canad. J. Math., 17, 533–540 (1965)
Peng, Y., Tang, Q. S., Zhao, C.: On Lagrangians of r-uniform hypergraphs. J. Comb. Optim., 30, 812–825 (2015)
Peng, Y., Zhao, C.: A Motzkin–Straus type result for 3-uniform hypergraphs. Graphs Combin., 29, 681–694 (2013)
Peng, Y., Tang, Q. S., Zhao, C., et al.: On clique and Graph-Lagrangians of 3-uniform hypergraphs, submitted
Sidorenko, A.: The maximal number of edges in a homogeneous hypergraph containing no prohibited subgraphs. Math. Notes, 41, 247–259 (1987), Translated from Mat. Zametki
Sun, Y. P., Tang, Q. S., Zhao, C., et al.: On the largest Graph-Lagrangian of 3-graphs with fixed number of edges. J. Optim. Theory Appl., 163, 57–79 (2014)
Talbot, J.: Lagrangians of hypergraphs. Combin. Probab. Comput., 11, 199–216 (2002)
Tang, Q. S., Peng, H., Wang, C., et al.: On Frankl and Füredi’s conjecture for 3-uniform hypergraphs. Acta Math. Appl. Sin. Engl. Ser., 32 1, 95–112 (2016)
Tang, Q. S., Peng, Y., Zhang, X. D., et al.: Some results on Lagrangians of hypergraphs. Discrete Appl. Math., 166, 222–238 (2014)
Tang, Q. S., Peng, Y., Zhang, X. D., et al.: On Graph-Lagrangians of hypergraphs containing dense subgraphs. J. Optim. Theory Appl., 163, 31–56 (2014)
Turán, P.: On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok, 48, 436–452 (1941)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported in part by National Natural Science Foundation of China (Grant No. 11271116)
Rights and permissions
About this article
Cite this article
Sun, Y.P., Peng, Y.J. & Wu, B. On Graph-Lagrangians and clique numbers of 3-uniform hypergraphs. Acta. Math. Sin.-English Ser. 32, 943–960 (2016). https://doi.org/10.1007/s10114-016-5472-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10114-016-5472-9