2015/07/11 by Annie Raymond, Mohit Singh, Raymond, Annie +3 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Optimization and Control (math.OC) #cs.DM #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.1507.03059
28 pages; changed some notation and definitions to better match the literature; added a conclusion
openalex publication_date 2015/07/11 · arxiv created 2017/08/28 · arxiv updated 2017/08/30 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
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.