Abstract
A remarkable connection between the order of a maximum clique and the Lagrangian of a graph was established by Motzkin and Straus in 1965. This connection and its extensions were applied in Turán problems of graphs and uniform hypergraphs. Very recently, the study of Turán densities of non-uniform hypergraphs has been motivated by extremal poset problems. Peng et al. showed a generalization of Motzkin–Straus result for \(\{1,2\}\)-graphs. In this paper, we attempt to explore the relationship between the Lagrangian of a non-uniform hypergraph and the order of its maximum cliques. We give a Motzkin–Straus type result for \(\{1,r\}\)-graphs. Moreover, we also give an extension of Motzkin–Straus theorem for \(\{1, r_2, \cdots , r_l\}\)-graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bomze IM (1997) Evolution towards the maximum clique. J Glob Optim 10:143–164
Budinich M (2003) Exact bounds on the order of the maximum clique of a graph. Discret Appl Math 127:535–543
Buló SR, Pelillo M (2008) A continuous characterization of maximal cliques in \(k\)-uniform hypergraphs. In: Maniezzo V, Battiti R, Watson JP (eds) Lecture Notes in Computer Science. Spring, New York, pp 220–233
Buló SR, Pelillo M (2009) A generalization of the Motzkin-Straus theorem to hypergraphs. Optim Lett 3:287–295
Buló SR, Torsello A, Pelillo M (2007) A continuous-based approach for partial clique enumeration. In: Escolano F, Vento M (eds) Lecture Notes in Computer Science, vol 4538. Spring, New York, pp 61–70
Busygin S (2006) A new trust region technique for the maximum weight clique problem. Discret Appl Math 154:2080–2096
Frankl P, Füredi Z (1988) Extremal problems and the Lagrange function of hypergraphs. Bull Inst Math Acad Sin 16:305–313
Frankl P, Füredi Z (1989) Extremal problems whose solutions are the blow-ups of the small Witt-designs. J Comb Theory Ser A 52:129–147
Frankl P, Peng Y, Rödl V, Talbot J (2007) A note on the jumping constant conjecture of Erdös. J Comb Theory Ser B 97:204–216
Frankl P, Rödl V (1984) Hypergraphs do not jump. Combinatorica 4:149–159
Frankl P, Rödl V (1989) Some Ramsey-Turán type results for hypergraphs. Combinatorica 8:129–147
Gibbons LE, Hearn DW, Pardalos PM, Ramana MV (1997) Continuous characterizations of the maximum clique problem. Math Oper Res 22:754–768
Griggs J, Katona G (2008) No four subsets forming an N. J Comb Theory Ser A 115:677–685
Griggs J, Lu L (2009) On families of subsets with a forbidden subposet. Comb Probab Comput 18:731–748
Hefetz D, Keevash P (2013) A hypergraph Turán theorem via lagrangians of intersecting families. J Combin Theory Ser A 120:2020–2038
Johston T Lu L Turán problems on non-uniform hypergraphs (2013), submitted
Katona G, Nemetz T, Simonovits M (1987) On a graph problem of Bollobás on \(4\)-graphs. Mat Zametki 41:433–455
Keevash P (2011) Hypergrah Turán problems. Cambridge University Press, Surveys in Combinatorics
Keevash P, Lenz J, Mubayi D Spectral extremal problems for hypergraphs, preprint available at arXiv:1304.0050
Motzkin T, Straus E (1965) Maxima for graphs and a new proof of a theorem of Turán. Can J Math 17:533–540
Mubayi D (2006) A hypergraph extension of Turáns theorem. J Comb Theory Ser B 96:122–134
Nikiforov V Analytic methods for uniform hypergraphs, preprint available at arXiv:1308.1654v3
Pardalos PM, Phillips A (1990) A global optimization approach for solving the maximum clique problem. Int J Comput Math 33:209–216
Pavan M, Pelillo M (2003) Generalizing the Motzkin-Straus theorem to edge-weighted graphs, with applications to image segmentation. In: Rangarajan A, Figueiredo A, Mrio AT, Zerubia J (eds) Lecture Notes in Computer Science. Spring, New York, pp 485–500
Peng Y (2007) Using Lagrangians of hypergrpahs to find non-jumping numbers II. Discret Math 307:1754–1766
Peng Y (2008) Using Lagrangians of hypergrpahs to find non-jumping numbers I. Ann Comb 12:307–324
Peng Y (2009) On substructure densities of hypergraphs. Graphs Comb 25:583–600
Peng Y, Peng H, Tang Q, Zhao C An extension of Motzkin-Straus thorem to non-uniform hypergraphs and its applications, preprint available in arXiv:1312.4135v1
Peng Y, Yao Y On polynomial optimization related to non-uniform hypergraphs, preprint available at arXiv:1312.3034v1
Peng Y, Zhao C (2008) Generating non-jumping numbers recursively. Discret Appl Math 156:1856–1864
Peng Y, Zhao C (2013) A Motzkin-Straus type result for \(3\)-uniform hypergraphs. Graphs Comb 29:681–694
Math Notes (1987) The maximal number of edges in a homogeneous hypergraph containing no prohibited subgraphs. 41:247–259 Translated from Mat. Zametki
Sós VT, Straus EG (1982) Extremals of functions on graphs with applications to graphs and hypergraphs. J. Combin. Theory. Ser A 32:246–257
Talbot J (2002) Lagrangians of hypergraphs. Comb Probab Comput 11:199–216
Tang Q, Peng Y, Zhang X, Zhao C (2013) Some results on Lagrangians of hypergraphs. Discret Appl Math. http://dx.doi.org/10.10.16/j.dam.2013.09.023
Tang Q, Peng Y, Zhang X, Zhao C On graph-Lagrangians of hypergraphs containing dense subgraphs. J. Optimiz. Theory App.10.1007/s10957-013-0485-3
Turán P (1941) On an extremal problem in graph theory (in Hungarian). Mat Fiz Lapok 48:436–452
Wilf HS (1986) Spectral bounds for the clique and independence numbers of graphs. J Comb Theory Ser B 40:113–117
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by NSFC and the 973 program.
Rights and permissions
About this article
Cite this article
Gu, R., Li, X., Peng, Y. et al. Some Motzkin–Straus type results for non-uniform hypergraphs. J Comb Optim 31, 223–238 (2016). https://doi.org/10.1007/s10878-014-9736-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-014-9736-y