Homogeneous multilinear functions on hypergraph cliques

다국어 초록 (Multilingual 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.

참고문헌 (Reference)

1 R. Gu, "Some Motzkin-Straus type results for non-uniform hypergraphs" 31 (31): 223-238, 2016

2 A. F. Sidorenko, "On the maximal number of edges in a homogeneous hypergraph that does not contain prohibited subgraphs" 41 (41): 433-455, 1987

3 Q. Tang, "On the graph-Lagrangians of 3-uniform hypergraphs containing dense subgraphs" 163 (163): 31-56, 2014

4 P. Tur´an, "On an extremal problem in graph theory" 48 : 436-452, 1941

5 Y. Peng, "On Lagrangians of r-uniform hypergraphs" 30 (30): 812-825, 2015

6 Q. Tang, "On Frankl and F¨uredi’s conjecture for 3-uniform hypergraphs" 32 (32): 95-112, 2016

7 T. S. Motzkin, "Maxima for graphs and a new proof of a theorem of Tur´an" 17 : 533-540, 1965

8 P. Frankl, "Hypergraphs do not jump" 4 (4): 149-159, 1984

9 M. Pavan, "Generalizing the Motzkin-Straus theorem to edge-weighted graphs, with applications to image segmentation" Spring 485-500, 2003

10 V. T. S´os, "Extremals of functions on graphs with applications to graphs and hypergraphs" 32 (32): 246-257, 1982

11 P. Frankl, "Extremal problems whose solutions are the blowups of the small Witt-designs" 52 (52): 129-147, 1989

12 M. Budinich, "Exact bounds on the order of the maximum clique of a graph" 127 (127): 535-543, 2003

13 I. M. Bomze, "Evolution towards the maximum clique" 10 (10): 143-164, 1997

14 L. E. Gibbons, "Continuous characterizations of the maximum clique problem" 22 (22): 754-768, 1997

15 Q. Tang, "Connection between the clique number and the Lagrangian of 3-uniform hypergraphs" 10 (10): 685-697, 2016

16 Y. Peng, "An extension of Motzkin-Straus theorem to non-uniform hypergraphs and its applications" 200 : 170-175, 2016

17 X. Lu, "A note on Lagrangians of 4-uniform hypergraphs" 121 : 329-340, 2015

18 S. Busygin, "A new trust region technique for the maximum weight clique problem" 154 (154): 2080-2096, 2006

19 D. Mubayi, "A hypergraph extension of Tur´an’s theorem" 96 (96): 122-134, 2006

20 P. M. Pardalos, "A global optimization approach for solving the maximum clique problem" 33 : 209-216, 1990

21 S. R. Bul`o, "A generalization of the Motzkin-Straus theorem to hypergraphs" 3 (3): 287-295, 2009

22 S. R. Bul´o, "A continuous-based approach for partial clique enumeration" Spring 61-70, 2007

23 S. R. Bul`o, "A continuous characterization of maximal cliques in k-uniform hypergraphs" Spring 220-233, 2008

24 Y. Peng, "A Motzkin-Straus type result for 3-uniform hypergraphs" 29 (29): 681-694, 2013