ALGEBRAIC COMBINATORICS

Symmetry in Turán sums of squares polynomials from flag algebras
Algebraic Combinatorics, Volume 1 (2018) no. 2, p. 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
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{\'a}n sums of squares polynomials from flag algebras},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {1},
     number = {2},
     year = {2018},
     pages = {249-274},
     doi = {10.5802/alco.5},
     language = {en},
     url = {http://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, p. 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, Springer, New York (Internat. Ser. Oper. Res. Management Sci.) 166 (2012), p. 219 -269 MR 2894697 | Zbl 1334.90097 | Article

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

[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, Springer, New York (Internat. Ser. Oper. Res. Management Sci.) 166 (2012), p. 171 -199 MR 2894695 | Zbl 1334.90100 | Article

[5] Erdős, P.; Stone, A. H. On the structure of linear graphs, Bull. Amer. Math. Soc, 52 (1946) no. 3, p. 1087 -1091 MR 18807 | Zbl 0063.01277 | Article

[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 (2013) no. 1, p. 21 -54 MR 3002572 | Zbl 1257.05077 | Article

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

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

[9] Fulton, W.; Harris, J. Representation Theory: A First Course, Springer, Graduate Texts in Mathematics (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, 192 (2004) no. 1-3, p. 95 -128 MR 2067190 | Zbl 1108.13021 | Article

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

[12] Laurent, M. Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry, Springer, New York (IMA Vol. Math. Appl.) 149 (2009), p. 157 -270 MR 2500468 | Zbl 1163.13021 | Article

[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 (2009) no. 3, p. 1324 -1334 MR 2538655 | Zbl 1228.05282 | Article

[14] Mantel, W. Problem 28, Wiskundige Opgaven, 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, 96 (2003) no. 2, p. 293 -320 MR 1993050 | Zbl 1043.14018 | Article

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

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

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

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

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

[21] Razborov, A. A. On Turán’s (3, 4)-problem with forbidden subgraphs, Mathematical Notes, 95 (2014) no. 1-2, p. 245 -252 MR 3267212 | Zbl 1310.05126 | Article

[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 (2013) no. 1, p. 122 -141 MR 3029481 | Zbl 1291.90167 | Article

[23] Sagan, B. E. The Symmetric Group, Springer-Verlag, New York, Graduate Texts in Mathematics, 203 (2001) MR 1824028 | Zbl 0964.05070

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

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

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

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