Connection between the clique number and the Lagrangian of 3-uniform hypergraphs

详细信息    查看全文

• 作者：Qingsong Tang ; Yuejian Peng ; Xiangde Zhang ; Cheng Zhao
• 关键词：Cliques of hypergraphs ; Colex ordering ; Lagrangians of hypergraphs ; Polynomial optimization
• 刊名：Optimization Letters
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：10
• 期：4
• 页码：685-697
• 全文大小：440 KB
• 参考文献：1.Caen, D.D.: Extension of a theorem of Moon and Moser on complete hypergraphs. Ars Combin. 16, 5–10 (1983)MathSciNet MATH
  2.Bulò Rota, S., Pelillo, M.: A generalization of the Motzkin-Straus theorem to hypergraphs. Optim. Lett. 3, 287–295 (2009)
  3.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)MathSciNet CrossRef MATH
  4.Frankl, P., Rödl, V.: Hypergraphs do not jump. Combinatorica. 4, 149–159 (1984)MathSciNet CrossRef MATH
  5.Keevash, P.: Hypergraph Turán problems. http://​www.​maths.​qmul.​ac.​uk/​keevash/​papers/​turan-survey
  6.Mubayi, D.: A hypergraph extension of Turán’s theorem. J. Combin. Theory. Ser. B. 96, 122–134 (2006)MathSciNet CrossRef MATH
  7.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)MathSciNet CrossRef MATH
  8.Peng, Y., Tang, Q., Zhao, C.: On Lagrangians of \(r\) -uniform Hypergraphs. J. Comb. Optim. doi:10.​1007/​s10878-013-9671-3 (in press)
  9.Peng, Y., Zhao, C.: A Motzkin-Straus type result for 3-uniform hypergraphs. Graphs Comb. 29, 681–694 (2013)MathSciNet CrossRef MATH
  10.Peng, Y., Zhu, H., Zheng, Y., Zhao, C.: On cliques and Lagrangians of 3-uniform hypergraphs. arXiv preprint arXiv:​1211.​6508 , (2012)
  11.Sidorenko, A.F.: Solution of a problem of Bollobás on 4-graphs. Mat. Zametki. 41, 433–455 (1987)MathSciNet
  12.Talbot, J.M.: Lagrangians of hypergraphs. Comb. Probab. Comput. 11, 199–216 (2002)MathSciNet CrossRef MATH
  13.Turán, P.: On an extremal problem in graph theory. Mat. Fiz. Lapok. 48, 436–452 (1941)MathSciNet
  14.Tang, Q., Peng, H., Wang, C., Peng Y.: On Frankl and Füredi’s conjecture for \(3\) -uniform hypergraphs, submitted
  15.Tang, Q., Peng, Y., Zhang, X., Zhao, C.: Some results on Lagrangians of Hypergraphs. Discrete Appl. Math. 166, 222–238 (2014)MathSciNet CrossRef MATH
  16.Tang, Q., Peng Y., Zhang, X., Zhao,C.: On the graph-Lagrangians of 3-uniform hypergraphs containing dense subgraphs, J. Optim. Theory Appl. 163, 31–56 (2014)
  
• 作者单位：Qingsong Tang (1) (4)
  Yuejian Peng (2)
  Xiangde Zhang (1)
  Cheng Zhao (3) (4)
  
  1. College of Sciences, Northeastern University, Shenyang, 110819, People’s Republic of China
  4. School of Mathematics, Jilin University, Changchun, 130012, People’s Republic of China
  2. College of Mathematics, Hunan University, Changsha, 410082, People’s Republic of China
  3. Department of Mathematics and Computer Science, Indiana State University, Terre Haute, 47809, IN, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

There is a remarkable connection between the clique number and the Lagrangian of a 2-graph proved by Motzkin and Straus (J Math 17:533–540, 1965). It would be useful in practice if similar results hold for hypergraphs. However, the obvious generalization of Motzkin and Straus’ result to hypergraphs is false. Frankl and Füredi conjectured 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. For \(r=2\), Motzkin and Straus’ theorem confirms this conjecture. For \(r=3\), it is shown by Talbot 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 3-uniform hypergraphs. As an application of this connection, we confirm that Frankl and Füredi’s conjecture holds for bigger ranges of m when \(r=3\). We also obtain two weaker versions of Turán type theorem for left-compressed 3-uniform hypergraphs.