ALGEBRAIC COMBINATORICS

no. 2

Symmetry in Turán sums of squares polynomials from flag algebras
Algebraic Combinatorics, Volume 1 (2018) no. 2, pp. 249-274.

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 Razborov 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 Gatermann and Parrilo. 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.

Received: 2017-08-24
Accepted: 2017-10-09
Published online: 2018-03-02
DOI: https://doi.org/10.5802/alco.5
Classification: 05D99,  12D15,  90C22
Keywords: sums of squares, semidefinite programming, flag algebras, extremal combinatorics, symmetry 
@article{ALCO_2018__1_2_249_0,
     author = {Raymond, Annie and Singh, Mohit and Thomas, Rekha R.},
     title = {Symmetry in Tur\'an sums of squares polynomials from flag algebras},
     journal = {Algebraic Combinatorics},
     pages = {249--274},
     publisher = {MathOA foundation},
     volume = {1},
     number = {2},
     year = {2018},
     doi = {10.5802/alco.5},
     zbl = {06882341},
     mrnumber = {MR3856524},
     language = {en},
     url = {alco.centre-mersenne.org/item/ALCO_2018__1_2_249_0/}
}
Raymond, Annie; Singh, Mohit; Thomas, Rekha R. Symmetry in Turán sums of squares polynomials from flag algebras. Algebraic Combinatorics, Volume 1 (2018) no. 2, pp. 249-274. doi : 10.5802/alco.5. https://alco.centre-mersenne.org/item/ALCO_2018__1_2_249_0/

[1] Bachoc, C.; Gijswijt, D. C.; Schrijver, A.; Vallentin, F. Invariant semidefinite programs, Handbook on Semidefinite, Conic and Polynomial Optimization (Internat. Ser. Oper. Res. Management Sci.) Volume 166, Springer, New York, 2012, pp. 219-269 | Article | MR 2894697 | Zbl 1334.90097

[2] Blekherman, G.; Parrilo, P. A.; Thomas, R. R. Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Series on Optimization, Volume 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2013, 476 pages | MR 3075433 | 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, Volume 87 (1999) no. 2, pp. 381-389 | Article | MR 1704268 | Zbl 0946.05063

[4] de Klerk, E.; de Oliveira Filho, F. M.; Pasechnik, D.V. Relaxations of combinatorial problems via association schemes, Handbook on Semidefinite, Conic and Polynomial Optimization (Internat. Ser. Oper. Res. Management Sci.) Volume 166, Springer, New York, 2012, pp. 171-199 | Article | MR 2894695 | Zbl 1334.90100

[5] Erdős, P.; Stone, A. H. On the structure of linear graphs, Bull. Amer. Math. Soc, Volume 52 (1946) no. 3, pp. 1087-1091 | Article | MR 18807 | 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., Volume 22 (2013) no. 1, pp. 21-54 | Article | MR 3002572 | Zbl 1257.05077

[7] Fässler, A.; Stiefel, E. Group Theoretical Methods and Their Applications, Birkhäuser, 1992 | Article | MR 1158662 | Zbl 0769.20002

[8] Frankl, P.; Füredi, Z. An exact result for 3-graphs, Discrete Math., Volume 50 (1984) no. 2-3, pp. 323-328 | Article | MR 753720 | Zbl 0538.05050

[9] Fulton, W.; Harris, J. Representation Theory: A First Course, Graduate Texts in Mathematics, Springer, 1991 no. 129 | MR 1153249 | Zbl 0744.22001

[10] Gatermann, K.; Parrilo, P. A. Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra, Volume 192 (2004) no. 1-3, pp. 95-128 | Article | MR 2067190 | Zbl 1108.13021

[11] Keevash, P. Hypergraph Turán problems, Surveys in combinatorics, Volume 392 (2011), pp. 83-140 | MR 2866732 | Zbl 1244.05159

[12] Laurent, M. Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry (IMA Vol. Math. Appl.) Volume 149, Springer, New York, 2009, pp. 157-270 | Article | MR 2500468 | 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., Volume 23 (2009) no. 3, pp. 1324-1334 | Article | MR 2538655 | Zbl 1228.05282

[14] Mantel, W. Problem 28, Wiskundige Opgaven, Volume 10 (1907) no. 320, p. 60-61 | Zbl 38.0270.01

[15] Parrilo, P. A. Semidefinite programming relaxations for semialgebraic problems, Math. Program., Ser. B, Volume 96 (2003) no. 2, pp. 293-320 | Article | MR 1993050 | Zbl 1043.14018

[16] Pikhurko, O. An exact Turán result for the generalized triangle, Combinatorica, Volume 28 (2008) no. 2, pp. 187-208 | Article | MR 2399018 | Zbl 1175.05137

[17] Raymond, A.; Saunderson, J.; Singh, M.; Thomas, R.R. Symmetric sums of squares over k-subset hypercubes, Mathematical Programming, Volume 167 (2018) no. 2, pp. 315-354 | Article | MR 3755735 | Zbl 06845431

[18] Razborov, A. A. Flag algebras, J. Symbolic Logic, Volume 72 (2007) no. 4, pp. 1239-1282 | Article | MR 2371204 | Zbl 1146.03013

[19] Razborov, A. A. On 3-hypergraphs with forbidden 4-vertex configurations, SIAM Journal on Discrete Mathematics, Volume 24 (2010) no. 3, pp. 946-963 | Article | MR 2680226 | Zbl 1223.05204

[20] Razborov, A. A. Flag algebras: an interim report, The Mathematics of Paul Erdős II, Springer, 2013, pp. 207-232 | Article | MR 3186665

[21] Razborov, A. A. On Turán’s (3, 4)-problem with forbidden subgraphs, Mathematical Notes, Volume 95 (2014) no. 1-2, pp. 245-252 | Article | MR 3267212 | 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, Volume 38 (2013) no. 1, pp. 122-141 | Article | MR 3029481 | Zbl 1291.90167

[23] Sagan, B. E. The Symmetric Group, Graduate Texts in Mathematics, Volume 203, Springer-Verlag, New York, 2001, xvi+238 pages | MR 1824028 | Zbl 0964.05070

[24] Schrijver, A. A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory, Volume 25 (1979), pp. 425-429 | Article | MR 536232 | Zbl 0444.94009

[25] Sidorenko, A. F. Asymptotic solution for a new class of forbidden r-graphs, Combinatorica, Volume 9 (1989) no. 2, pp. 207-215 | Article | MR 1030374 | Zbl 0732.05031

[26] Turán, P. Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, Volume 48 (1941), pp. 436-452 | MR 18405 | Zbl 0026.26903

[27] Turán, P. Research problem, Közl MTA Mat. Kutató Int., Volume 6 (1961), pp. 417-423 | MR 177847