On Lagrangians of r-uniform hypergraphs

详细信息    查看全文

• 作者：Yuejian Peng ; Qingsong Tang ; Cheng Zhao
• 关键词：Cliques of hypergraphs ; Lagrangians of hypergraphs ; Optimization
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：30
• 期：3
• 页码：812-825
• 全文大小：441 KB
• 参考文献：Budinich M (2003) Exact bounds on the order of the maximum clique of a graph. Discrete Appl Math 127:535-43MathSciNet CrossRef MATH
  Busygin S (2006) A new trust region technique for the maximum weight clique problem. Discrete Appl Math 304(4):2080-096MathSciNet CrossRef
  Frankl P, Füredi Z (1989) Extremal problems whose solutions are the blow-ups of the small Witt-designs. J Comb Theory (A) 52:129-47CrossRef MATH
  Frankl P, R?dl V (1984) Hypergraphs do not jump. Combinatorica 4:149-59MathSciNet CrossRef MATH
  Gibbons LE, Hearn DW, Pardalos PM, Ramana MV (1997) Continuous characterizations of the maximum clique problem. Math Oper Res 22:754-68MathSciNet CrossRef MATH
  He G, Peng Y, Zhao C, On finding Lagrangians of 3-uniform hypergraphs, Ars Combinatoria (accepted)
  Motzkin TS, Straus EG (1965) Maxima for graphs and a new proof of a theorem of Turán. Can J Math 17:533-40MathSciNet CrossRef MATH
  Mubayi D (2006) A hypergraph extension of Turan’s theorem. J Comb Theory B 96:122-34MathSciNet CrossRef MATH
  Pavan M, Pelillo M (2003) Generalizing the motzkin-straus theorem to edge-weighted graphs, with applications to image segmentation. Lect Notes Comput Sci 2683:485-00CrossRef
  Pardalos PM, Phillips AT (1990) A global optimization approach for solving the maximum clique problem. Int J Comput Math 33:209-16CrossRef MATH
  Peng Y, Zhao C (2013) A Motzkin–Straus type result for 3-uniform hypergraphs. Graphs Comb 29:681-94MathSciNet CrossRef MATH
  Peng Y, Zhao C (2012) On Lagrangians of hypergraphs and cliques. Recent Adv Comput Sci Inf Eng 125:7-2CrossRef
  Peng Y, Zhu HG, Zheng Y, Zhao C On cliques and Lagrangians of 3-uniform hypergraphs. http://?arxiv.?org/?abs/-211.-508
  Rota Buló S, Pelillo M (2008) A continuous characterization of maximal cliques in k-uniform hypergraphs. Learn Intellig Optim 5313:220-33CrossRef
  Rota Buló S, Pelillo M (2009) A generalization of the Motzkin–Straus theorem to hypergraphs. Optim Lett 3(2):287-95MathSciNet CrossRef MATH
  Rota Buló S, Torsello A, Pelillo M (2007) A continuous-based approach for partial clique enumeration. Graph-Based Represent Patt Recogn 4538:61-0CrossRef
  Sidorenko AF (1987) Solution of a problem of Bollobás on 4-graphs. Mat Zametki 41:433-55MathSciNet
  Sós V, Straus EG (1982) Extremal of functions on graphs with applications to graphs and hypergraphs. J Comb Theory B 63:189-07
  Talbot J (2002) Lagrangians of hypergraphs. Comb Probab Comput 11:199-16MathSciNet CrossRef MATH
  Tang QS, Peng YJ, Zhang XD, Zhao C Some results on Lagrangians of hypergraphs. Discrete Appl Math (accepted)
  Tang QS, Peng YJ, Zhang XD, Zhao C On Frankl and Füredi’s conjecture for \(3\) -uniform hypergraphs. http://?arxiv.?org/?abs/-211.-056
  Turán P (1941) On an extremal problem in graph theory. Mat Fiz Lapok 48:436-52 (in Hungarian)MathSciNet
  Wilf HS (1986) Spectral bounds for the clique and independence number of graphs. J Comb Theory B 40:113-17MathSciNet CrossRef MATH
  
• 作者单位：Yuejian Peng (1)
  Qingsong Tang (2) (3)
  Cheng Zhao (4) (5)
  
  1. College of Mathematics, Hunan University, Changsha, 410082, People’s Republic of China
  2. College of Sciences, Northeastern University, Shenyang, 110819, People’s Republic of China
  3. Mathematics School, Jilin University, Changchun, 130012, People’s Republic of China
  4. School of Mathematics, Jilin University, Changchun, 130022, People’s Republic of China
  5. Department of Mathematics and Computer Science, Indiana State University, Terre Haute, IN, 47809, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

A remarkable connection between the order of a maximum clique and the Lagrangian of a graph was established by Motzkin and Straus in Can J Math 17:533-40 (1965). This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It has been also applied in spectral graph theory. Estimating the Lagrangians of hypergraphs has been successfully applied in the course of studying the Turán densities of several hypergraphs as well. It is useful in practice if Motzkin–Straus type results hold for hypergraphs. However, the obvious generalization of Motzkin and Straus-result to hypergraphs is false. We attempt to explore the relationship between the Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range. In this paper, we give some Motzkin–Straus type results for r-uniform hypergraphs. These results generalize and refine a result of Talbot in Comb Probab Comput 11:199-16 (2002) and a result in Peng and Zhao (Graphs Comb, 29:681-94, 2013). Keywords Cliques of hypergraphs Lagrangians of hypergraphs Optimization