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.
Accepted:
Published online:
DOI: 10.5802/alco.5
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 = {http://archive.numdam.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 - http://archive.numdam.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 http://archive.numdam.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. http://archive.numdam.org/articles/10.5802/alco.5/
[1] 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] An upper bound for the Turán number , J. Combin. Theory Ser. A, Volume 87 (1999) no. 2, pp. 381-389 | DOI | MR | Zbl
[4] 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] On the structure of linear graphs, Bull. Amer. Math. Soc, Volume 52 (1946) no. 3, pp. 1087-1091 | DOI | MR | Zbl
[6] 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] Group Theoretical Methods and Their Applications, Birkhäuser, 1992 | DOI | MR | Zbl
[8] An exact result for -graphs, Discrete Math., Volume 50 (1984) no. 2-3, pp. 323-328 | DOI | MR | Zbl
[9] Representation Theory: A First Course, Graduate Texts in Mathematics, Springer, 1991 no. 129 | MR | Zbl
[10] 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] Hypergraph Turán problems, Surveys in combinatorics, Volume 392 (2011), pp. 83-140 | MR | Zbl
[12] 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] An exact result for hypergraphs and upper bounds for the Turán density of , SIAM J. Discrete Math., Volume 23 (2009) no. 3, pp. 1324-1334 | DOI | MR | Zbl
[14] Problem 28, Wiskundige Opgaven, Volume 10 (1907) no. 320, pp. 60-61 | Zbl
[15] Semidefinite programming relaxations for semialgebraic problems, Math. Program., Ser. B, Volume 96 (2003) no. 2, pp. 293-320 | DOI | MR | Zbl
[16] An exact Turán result for the generalized triangle, Combinatorica, Volume 28 (2008) no. 2, pp. 187-208 | DOI | MR | Zbl
[17] Symmetric sums of squares over k-subset hypercubes, Mathematical Programming, Volume 167 (2018) no. 2, pp. 315-354 | DOI | MR | Zbl
[18] Flag algebras, J. Symbolic Logic, Volume 72 (2007) no. 4, pp. 1239-1282 | DOI | MR | Zbl
[19] 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] Flag algebras: an interim report, The Mathematics of Paul Erdős II, Springer, 2013, pp. 207-232 | DOI | MR
[21] 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] Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization, Mathematics of Operations Research, Volume 38 (2013) no. 1, pp. 122-141 | DOI | MR | Zbl
[23] The Symmetric Group, Graduate Texts in Mathematics, 203, Springer-Verlag, New York, 2001, xvi+238 pages | MR | Zbl
[24] A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory, Volume 25 (1979), pp. 425-429 | DOI | MR | Zbl
[25] Asymptotic solution for a new class of forbidden -graphs, Combinatorica, Volume 9 (1989) no. 2, pp. 207-215 | DOI | MR | Zbl
[26] Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, Volume 48 (1941), pp. 436-452 | MR | Zbl
[27] Research problem, Közl MTA Mat. Kutató Int., Volume 6 (1961), pp. 417-423 | MR
Cited by Sources: