Homogeneous multilinear functions on hypergraph cliques
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Motzkin and Straus established a close connection between the maximum clique problem and a solution (namely graph-Lagrangian) to the maximum value of a class of homogeneous quadratic multilinear functions over the standard simplex of the Euclidean space in 1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique problem in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we develop a homogeneous multilinear function based on the structure of hypergraphs and their complement hypergraphs. Its maximum value generalizes the graph-Lagrangian. Specifically, we establish a connection between the clique number and the generalized graph-Lagrangian of $3$-uniform graphs, which supports the conjecture posed in this paper.
Abstract
Motzkin and Straus established a close connection between the maximum clique problem and a solution (namely graph-Lagrangian) to the maximum value of a class of homogeneous quadratic multilinear functions over the standard simplex of the Euclidean space in 1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique problem in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we develop a homogeneous multilinear function based on the structure of hypergraphs and their complement hypergraphs. Its maximum value generalizes the graph-Lagrangian. Specifically, we establish a connection between the clique number and the generalized graph-Lagrangian of $3$-uniform graphs, which supports the conjecture posed in this paper.
참고문헌 (24)
- I. M. Bomze, "Evolution towards the maximum clique", J. Global Optim, 10(2), pp.143~164 (1997)
- M. Budinich, "Exact bounds on the order of the maximum clique of a graph", Discrete Appl. Math, 127(3), pp.535~543 (2003)
- S. R. Bul`o, "A continuous characterization of maximal cliques in k-uniform hypergraphs", pp.220~233 (2008), Spring
- S. R. Bul`o, "A generalization of the Motzkin-Straus theorem to hypergraphs", Optim. Lett, 3(2), pp.287~295 (2009)
- S. R. Bul´o, "A continuous-based approach for partial clique enumeration", pp.61~70 (2007), Spring
- S. Busygin, "A new trust region technique for the maximum weight clique problem", Discrete Appl. Math, 154(15), pp.2080~2096 (2006)
- P. Frankl, "Extremal problems whose solutions are the blowups of the small Witt-designs", J. Combin. Theory Ser. A, 52(1), pp.129~147 (1989)
- P. Frankl, "Hypergraphs do not jump", Combinatorica, 4(2-3), pp.149~159 (1984)
- L. E. Gibbons, "Continuous characterizations of the maximum clique problem", Math. Oper. Res, 22(3), pp.754~768 (1997)
- R. Gu, "Some Motzkin-Straus type results for non-uniform hypergraphs", J. Comb. Optim, 31(1), pp.223~238 (2016)
- X. Lu, "A note on Lagrangians of 4-uniform hypergraphs", Ars Combin, 121, pp.329~340 (2015)
- T. S. Motzkin, "Maxima for graphs and a new proof of a theorem of Tur´an", Canad. J. Math, 17, pp.533~540 (1965)
- D. Mubayi, "A hypergraph extension of Tur´an’s theorem", J. Combin. Theory Ser. B, 96(1), pp.122~134 (2006)
- P. M. Pardalos, "A global optimization approach for solving the maximum clique problem", Int. J. Comput. Math, 33, pp.209~216 (1990)
- M. Pavan, "Generalizing the Motzkin-Straus theorem to edge-weighted graphs, with applications to image segmentation", pp.485~500 (2003), Spring
- Y. Peng, "An extension of Motzkin-Straus theorem to non-uniform hypergraphs and its applications", Discrete Appl. Math, 200, pp.170~175 (2016)
- Y. Peng, "On Lagrangians of r-uniform hypergraphs", J. Comb. Optim, 30(3), pp.812~825 (2015)
- Y. Peng, "A Motzkin-Straus type result for 3-uniform hypergraphs", Graphs Combin, 29(3), pp.681~694 (2013)
- A. F. Sidorenko, "On the maximal number of edges in a homogeneous hypergraph that does not contain prohibited subgraphs", Mat. Zametki, 41(3), pp.433~455 (1987)
- V. T. S´os, "Extremals of functions on graphs with applications to graphs and hypergraphs", J. Combin. Theory Ser. B, 32(3), pp.246~257 (1982)
- Q. Tang, "On Frankl and F¨uredi’s conjecture for 3-uniform hypergraphs", Acta Math. Appl. Sin. Engl. Ser, 32(1), pp.95~112 (2016)
- Q. Tang, "On the graph-Lagrangians of 3-uniform hypergraphs containing dense subgraphs", J. Optim. Theory Appl, 163(1), pp.31~56 (2014)
- Q. Tang, "Connection between the clique number and the Lagrangian of 3-uniform hypergraphs", Optimization Lett, 10(4), pp.685~697 (2016)
- P. Tur´an, "On an extremal problem in graph theory", Mat. Fiz. Lapok, 48, pp.436~452 (1941)