×

zbMATH — the first resource for mathematics

Symmetric sums of squares over \(k\)-subset hypercubes. (English) Zbl 1383.05306
Summary: We consider the problem of finding sum of squares (sos) expressions to establish the non-negativity of a symmetric polynomial over a discrete hypercube whose coordinates are indexed by the \(k\)-element subsets of \([n]\). For simplicity, we focus on the case \(k=2\), but our results extend naturally to all values of \(k \geq 2\). We develop a variant of the Gatermann-Parrilo symmetry-reduction method tailored to our setting that allows for several simplifications and a connection to flag algebras. We show that every symmetric polynomial that has a sos expression of a fixed degree also has a succinct sos expression whose size depends only on the degree and not on the number of variables. Our method bypasses much of the technical difficulties needed to apply the Gatermann-Parrilo method, and offers flexibility in obtaining succinct sos expressions that are combinatorially meaningful. As a byproduct of our results, we arrive at a natural representation-theoretic justification for the concept of flags as introduced by A. A. Razborov [J. Symb. Log. 72, No. 4, 1239–1282 (2007; Zbl 1146.03013)] in his flag algebra calculus. Furthermore, this connection exposes a family of non-negative polynomials that cannot be certified with any fixed set of flags, answering a question of Razborov in the context of our finite setting.

MSC:
05D99 Extremal combinatorics
12D15 Fields related with sums of squares (formally real fields, Pythagorean fields, etc.)
20C30 Representations of finite symmetric groups
90C22 Semidefinite programming
90C27 Combinatorial optimization
Software:
Flagmatic
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bai, Y; Klerk, E; Pasechnik, DV; Sotirov, R, Exploiting group symmetry in truss topology optimization, Optim. Eng., 10, 331-349, (2009) · Zbl 1400.90242
[2] Blekherman, G; Gouveia, J; Pfeiffer, J, Sums of squares on the hypercube, Math. Z., 284, 41-54, (2016) · Zbl 1375.14187
[3] Bachoc, C., Gijswijt, D.C., Schrijver, A., Vallentin, F.: Invariant semidefinite programs. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, volume 166 of International Series on Operation Research and Management Science, pp. 219-269. Springer, New York (2012) · Zbl 1334.90097
[4] Blekherman, G., Parrilo, P.A., Thomas, R.R. (eds.): Semidefinite Optimization and Convex Algebraic Geometry, volume 13 of MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2013) · Zbl 1260.90006
[5] Bachoc, C; Vallentin, F, New upper bounds for kissing numbers from semidefinite programming, J. AMS, 21, 909-924, (2008) · Zbl 1223.90039
[6] Klerk, E; Maharry, J; Pasechnik, DV; Richter, RB; Salazar, G, Improved bounds for crossing numbers of \(k_{m, n}\) and \(k_n\), SIAM J. Discret. Math., 20, 189-202, (2006) · Zbl 1111.05029
[7] de Klerk, E., Pasechnik, D.V.: Solving SDP’s in non-commutative algebras part I: the dual-scaling algorithm. Discussion paper from Tilburg University, Center for Economic Research (2005) · Zbl 1035.90056
[8] Klerk, E; Pasechnik, DV; Schrijver, A, Reduction of symmetric semidefinite programs using the regular \(*\)-representation, Math. Program. Ser. B, 109, 613-624, (2007) · Zbl 1200.90136
[9] Klerk, E; Sotirov, R, Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Math. Program. Ser. A, 122, 225-246, (2010) · Zbl 1184.90120
[10] Fulton, W., Harris, J.: Representation Theory: A First Course. Number 129 in Graduate Texts in Mathematics. Springer, Berlin (1991) · Zbl 0744.22001
[11] Falgas-Ravry, V; Vaughan, ER, Applications of the semi-definite method to the Turán density problem for 3-graphs, Combin. Probab. Comput., 22, 21-54, (2013) · Zbl 1257.05077
[12] Fässler, A., Stiefel, E.: Group Theoretical Methods and Their Applications. Birkhäuser, Basel (1992) · Zbl 0769.20002
[13] Gijswijt, D.: Block diagonalization for algebra’s associated with block codes. arXiv:0910.4515 (2014) · Zbl 1184.90120
[14] Gvozdenović, N; Laurent, M, Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization, SIAM J. Optim., 19, 592-615, (2008) · Zbl 1213.05081
[15] Gvozdenović, N; Laurent, M; Vallentin, F, Block-diagonal semidefinite programming hierarchies for 0/1 programming, Oper. Res. Lett., 37, 27-31, (2009) · Zbl 1154.90606
[16] Gatermann, K; Parrilo, PA, Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra, 192, 95-128, (2004) · Zbl 1108.13021
[17] Grigoriev, D, Complexity of positivstellensatz proofs for the knapsack, Comput. Complex., 10, 139-154, (2001) · Zbl 0992.68077
[18] Gijswijt, D., Schrijver, A., Tanaka, H.: New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming. J. Combin. Theory Ser. A 113, 1719-1731 (2006) · Zbl 1105.94027
[19] Hatami, H; Norine, S, Undecidability of linear inequalities in graph homomorphism densities, J. Am. Math. Soc., 24, 547-565, (2011) · Zbl 1259.05088
[20] Jansson, L., Lasserre, J.B., Riener, C., Theobald, T.: Exploiting symmetries in SDP-relaxations for polynomial optimization. Math. Oper. Res 38(1), 122-141 (2013) · Zbl 1291.90167
[21] Kurpisz, A., Leppänen, S., Mastrolilli, M.: Sum-of-squares hierarchy lower bounds for symmetric formulations. In: Louveaux, Q., Skutella, Integer Programming and Combinatorial Optimization, pp. 362-374. Springer, Cham (2016) · Zbl 1419.90070
[22] Kanno, Y; Ohsaki, M; Murota, K; Katoh, N, Group symmetry in interior-point methods for semidefinite program, Optim. Eng., 2, 293-320, (2001) · Zbl 1035.90056
[23] Kóvari, T., Sós, V., Turán, P.: On a problem of K. Zarankiewicz. Colloq Math. 3(1), 50-57 (1954)
[24] Laurent, M, Strengthened semidefinite bounds for codes, Math. Program., 109, 239-261, (2007) · Zbl 1147.90034
[25] Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry, volume 149 of IMA Volume in Mathematical Applications, pp. 157-270. Springer, New York (2009) · Zbl 1163.13021
[26] Lovász, L.: Large Networks and Graph Limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI (2012) · Zbl 1292.05001
[27] Litjens, B., Polak, S., Schrijver, A.: Semidefinite bounds for nonbinary codes based on quadruples. In: Designs, Codes and Cryptography, pp. 1-14. Springer, US (2016) · Zbl 1404.94155
[28] Lee, T., Prakash, A., de Wolf, R., Yuen, H.: On the sum-of-squares degree of symmetric quadratic functions. arXiv:1601.02311 (2016) · Zbl 1380.68203
[29] Parrilo, P.A.: An explicit construction of distinguished representations of polynomials nonnegative over finite sets. Technical Report IfA AUT 02-02, ETH Zürich (2002) · Zbl 1154.90606
[30] Radziszowski, S.P., et al.: Small Ramsey numbers. Electron. J. Combin. 1(7) (1994) · Zbl 1200.90136
[31] Razborov, AA, Flag algebras, J. Symb. Log., 72, 1239-1282, (2007) · Zbl 1146.03013
[32] Razborov, AA, On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J. Discret. Math., 24, 946-963, (2010) · Zbl 1223.05204
[33] Razborov, AA, On turán’s (3, 4)-problem with forbidden subgraphs, Math. Notes, 95, 245-252, (2014) · Zbl 1310.05126
[34] Raymond, A., Singh, M., Thomas, R.R.: Symmetry in Turán sums of squares polynomials from flag algebras. arXiv:1507.03059 (2015)
[35] Sagan, B.E.: The Symmetric Group, volume 203 of Graduate Texts in Mathematics. Springer, New York (2001). (2nd edn, Representations, Combinatorial Algorithms, and Symmetric Functions)
[36] Schrijver, A.: Association Schemes and the Shannon Capacity: Eberlein Polynomials and the Erdös-Ko-Rado Theorem. Number 25 in Algebraic Methods in Graph Theory, Vol. I, II (Szeged, 1978), Colloqium Mathematical Society. János Bolyai, North-Holland, Amsterdam (1981)
[37] Schrijver, A, New code upper bounds from the Terwilliger algebra, IEEE Trans. Inf. Theory, 51, 2859-2866, (2005) · Zbl 1298.94152
[38] Serre, J.-P.: Linear Representations of Finite Groups. Springer, New York. Translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42 (1977) · Zbl 1223.90039
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.