Browse issues
no. 2
Symmetry in Turán sums of squares polynomials from flag algebras
Raymond, Annie1; Singh, Mohit2; Thomas, Rekha R.3
1 Department of Mathematics and Statistics University of Massachusetts Amherst Amherst, MA 01003
2 H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology, Atlanta, GA 30332
3 Department of Mathematics University of Washington Box 354350 Seattle, WA 98195
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:
Accepted:
Published online:
DOI: 10.5802/alco.5
Classification: 05D99, 12D15, 90C22
Keywords: sums of squares, semidefinite programming, flag algebras, extremal combinatorics, symmetry

Raymond, Annie 1; Singh, Mohit 2; Thomas, Rekha R. 3

1 Department of Mathematics and Statistics University of Massachusetts Amherst Amherst, MA 01003
2 H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology, Atlanta, GA 30332
3 Department of Mathematics University of Washington Box 354350 Seattle, WA 98195
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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},
     mrnumber = {MR3856524},
     zbl = {06882341},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.5/}
}
TY  - JOUR
AU  - Raymond, Annie
AU  - Singh, Mohit
AU  - Thomas, Rekha R.
TI  - Symmetry in Turán sums of squares polynomials from flag algebras
JO  - Algebraic Combinatorics
PY  - 2018
SP  - 249
EP  - 274
VL  - 1
IS  - 2
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.5/
DO  - 10.5802/alco.5
LA  - en
ID  - ALCO_2018__1_2_249_0
ER  - 
%0 Journal Article
%A Raymond, Annie
%A Singh, Mohit
%A Thomas, Rekha R.
%T Symmetry in Turán sums of squares polynomials from flag algebras
%J Algebraic Combinatorics
%D 2018
%P 249-274
%V 1
%N 2
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.5/
%R 10.5802/alco.5
%G en
%F 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/articles/10.5802/alco.5/

[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 | DOI | MR | Zbl

[2] Semidefinite Optimization and Convex Algebraic Geometry (Blekherman, G.; Parrilo, P. A.; Thomas, R. R., eds.), MOS-SIAM Series on Optimization, 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2013, 476 pages | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

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

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

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

Cited by Sources: