Symmetry in Turán Sums of Squares Polynomials from Flag Algebras
Symmetry in Turán Sums of Squares Polynomials from Flag Algebras
复制标题
DOI：
10.5802/alco.5
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
Annie Raymond;Mohit Singh;Rekha R. Thomas
中科院分区：
文献类型：
--
作者：
Annie Raymond;Mohit Singh;Rekha R. Thomas
极值组合学中的Tur\'an问题要求找到避免指定子图的图和超图的边密度的渐近界。由Razborov提出的旗代数理论提供了基于半定规划的强有力的方法来寻找平方和，建立边密度不等式的Tur\'an问题。多项式类似物的旗代数实体的工作，我们证明了这样的总和的平方创建的旗代数可以检索到从一个限制版本的自适应半定方案提出的Gatermann和Parrilo。这涉及到使用的代表性理论的对称群找到简洁的总和平方表达式不变的多项式。这种联系揭示了旗代数平方和的若干组合和结构性质，为研究Tur 'an及其它相关问题提供了新的工具.
Tur\'an 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\'an 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\'an and other related problems.