Report
Symmetric Sums of Squares over $k$-Subset Hypercubes
| العنوان: | Symmetric Sums of Squares over $k$-Subset Hypercubes |
|---|---|
| المؤلفون: | Raymond, Annie, Saunderson, James, Singh, Mohit, Thomas, Rekha R. |
| سنة النشر: | 2016 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Mathematics - Optimization and Control |
| الوصف: | 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 Razborov 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. Comment: 32 pages; corrected typo in acknowledgments |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1606.05639 |
| رقم الانضمام: | edsarx.1606.05639 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |