×

zbMATH — the first resource for mathematics

Symmetry in Turán sums of squares polynomials from flag algebras. (English) Zbl 1388.05186
Summary: Turán problems in extremal combinatorics ask to find asymptotic bounds on the edge densities of graphs and hypergraphs that avoid specified subgraphs. The theory of flag algebras proposed by A. A. Razborov [J. Symb. Log. 72, No. 4, 1239–1282 (2007; Zbl 1146.03013)] provides powerful methods based on semidefinite programming to find sums of squares that establish edge density inequalities in Turán problems. Working with polynomial analogs of the flag algebra entities, we prove that such sums of squares created by flag algebras can be retrieved from a restricted version of the symmetry-adapted semidefinite program proposed by K. Gatermann and P. A. Parrilo [J. Pure Appl. Algebra 192, No. 1–3, 95–128 (2004; Zbl 1108.13021)]. This involves using the representation theory of the symmetric group for finding succinct sums of squares expressions for invariant polynomials. The connection reveals several combinatorial and structural properties of flag algebra sums of squares, and offers new tools for Turán and other related problems.
MSC:
05D99 Extremal combinatorics
12D15 Fields related with sums of squares (formally real fields, Pythagorean fields, etc.)
90C22 Semidefinite programming
Software:
Flagmatic
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bachoc, C.; Gijswijt, D. C.; Schrijver, A.; Vallentin, F., Handbook on Semidefinite, Conic and Polynomial Optimization, 166, Invariant semidefinite programs, 219-269, (2012), Springer, New York · Zbl 1334.90097
[2] Blekherman, G.; Parrilo, P. A.; Thomas, R. R., Semidefinite Optimization and Convex Algebraic Geometry, 13, 476 pp., (2013), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA · Zbl 1260.90006
[3] Chung, F.; Lu, L., An upper bound for the Turán number \(t_3(n,4)\), J. Combin. Theory Ser. A, 87, 2, 381-389, (1999) · Zbl 0946.05063
[4] de Klerk, E.; de Oliveira Filho, F. M.; Pasechnik, D. V., Handbook on Semidefinite, Conic and Polynomial Optimization, 166, Relaxations of combinatorial problems via association schemes, 171-199, (2012), Springer, New York · Zbl 1334.90100
[5] Erdős, P.; Stone, A. H., On the structure of linear graphs, Bull. Amer. Math. Soc, 52, 3, 1087-1091, (1946) · Zbl 0063.01277
[6] Falgas-Ravry, V.; Vaughan, E. R., Applications of the semi-definite method to the Turán density problem for 3-graphs, Combin. Probab. Comput., 22, 1, 21-54, (2013) · Zbl 1257.05077
[7] Fässler, A.; Stiefel, E., Group Theoretical Methods and Their Applications, (1992), Birkhäuser · Zbl 0769.20002
[8] Frankl, P.; Füredi, Z., An exact result for \(3\)-graphs, Discrete Math., 50, 2-3, 323-328, (1984) · Zbl 0538.05050
[9] Fulton, W.; Harris, J., Representation Theory: A First Course, 129, (1991), Springer · Zbl 0744.22001
[10] Gatermann, K.; Parrilo, P. A., Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra, 192, 1-3, 95-128, (2004) · Zbl 1108.13021
[11] Keevash, P., Hypergraph Turán problems, Surveys in combinatorics, 392, 83-140, (2011) · Zbl 1244.05159
[12] Laurent, M., Emerging Applications of Algebraic Geometry, 149, Sums of squares, moment matrices and optimization over polynomials, 157-270, (2009), Springer, New York · Zbl 1163.13021
[13] Lu, L.; Zhao, Y., An exact result for hypergraphs and upper bounds for the Turán density of \(K_{r+1}^r\), SIAM J. Discrete Math., 23, 3, 1324-1334, (2009) · Zbl 1228.05282
[14] Mantel, W., Problem 28, Wiskundige Opgaven, 10, 320, 60-61, (1907) · JFM 38.0270.01
[15] Parrilo, P. A., Semidefinite programming relaxations for semialgebraic problems, Math. Program., Ser. B, 96, 2, 293-320, (2003) · Zbl 1043.14018
[16] Pikhurko, O., An exact Turán result for the generalized triangle, Combinatorica, 28, 2, 187-208, (2008) · Zbl 1175.05137
[17] Raymond, A.; Saunderson, J.; Singh, M.; Thomas, R. R., Symmetric sums of squares over k-subset hypercubes, Mathematical Programming, 167, 2, 315-354, (2018) · Zbl 1383.05306
[18] Razborov, A. A., Flag algebras, J. Symbolic Logic, 72, 4, 1239-1282, (2007) · Zbl 1146.03013
[19] Razborov, A. A., On 3-hypergraphs with forbidden 4-vertex configurations, SIAM Journal on Discrete Mathematics, 24, 3, 946-963, (2010) · Zbl 1223.05204
[20] Razborov, A. A., The Mathematics of Paul Erdős II, Flag algebras: an interim report, 207-232, (2013), Springer
[21] Razborov, A. A., On turán’s (3, 4)-problem with forbidden subgraphs, Mathematical Notes, 95, 1-2, 245-252, (2014) · Zbl 1310.05126
[22] Riener, C.; Theobald, T.; Jansson Andrén, L.; Lasserre, J. B., Exploiting symmetries in SDP-relaxations for polynomial optimization, Mathematics of Operations Research, 38, 1, 122-141, (2013) · Zbl 1291.90167
[23] Sagan, B. E., The Symmetric Group, 203, xvi+238 pp., (2001), Springer-Verlag, New York · Zbl 0964.05070
[24] Schrijver, A., A comparison of the delsarte and lovász bounds, IEEE Trans. Inform. Theory, 25, 425-429, (1979) · Zbl 0444.94009
[25] Sidorenko, A. F., Asymptotic solution for a new class of forbidden \(r\)-graphs, Combinatorica, 9, 2, 207-215, (1989) · Zbl 0732.05031
[26] Turán, P., Eine extremalaufgabe aus der graphentheorie, Mat. Fiz. Lapok, 48, 436-452, (1941) · JFM 67.0732.03
[27] Turán, P., Research problem, Közl MTA Mat. Kutató Int., 6, 417-423, (1961)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.