Simple Graph Density Inequalities with No Sum of Squares Proofs
- PDF / 386,332 Bytes
- 17 Pages / 442.205 x 665.008 pts Page_size
- 61 Downloads / 214 Views
Bolyai Society – Springer-Verlag
Combinatorica 17pp. DOI: 10.1007/s00493-019-4124-y
SIMPLE GRAPH DENSITY INEQUALITIES WITH NO SUM OF SQUARES PROOFS GRIGORIY BLEKHERMAN, ANNIE RAYMOND, MOHIT SINGH, REKHA R. THOMAS Received December 28, 2018 Revised August 1, 2019 Establishing inequalities among graph densities is a central pursuit in extremal combinatorics. A standard tool to certify the nonnegativity of a graph density expression is to write it as a sum of squares. In this paper, we identify a simple condition under which a graph density expression cannot be a sum of squares. Using this result, we prove that the Blakley–Roy inequality does not have a sum of squares certificate when the path length is odd. We also show that the same Blakley–Roy inequalities cannot be certified by sums of squares using a multiplier of the form one plus a sum of squares. These results answer two questions raised by Lov´ asz. Our main tool is used again to show that the smallest open case of Sidorenko’s conjectured inequality cannot be certified by a sum of squares. Finally, we show that our setup is equivalent to existing frameworks by Razborov and Lov´ asz–Szegedy, and thus our results hold in these settings too.
1. Introduction A graph G has vertex set V (G) and edge set E(G). All graphs are assumed to be simple, without loops or multiple edges. The homomorphism density of a graph H in a graph G, denoted by t(H; G), is the probability that a random map from V (H) to V (G) is a graph homomorphism, i.e., it maps every edge of H to an edge of G. An inequality between homomorphism Mathematics Subject Classification (2010): 05C35, 90C22; 90C35 Grigoriy Blekherman was partially supported by NSF grant DMS-1352073. This material is partially based upon work supported by the National Science Foundation under Grant No. 1440140, while Annie Raymond and Rekha Thomas were in residence at the Mathematical Sciences Research Institute in Berkeley, California, during the fall of 2017. Mohit Singh was partially supported by NSF grant CCF-1717947 and Rekha Thomas was partially supported by NSF grant DMS-1719538.
2
G. BLEKHERMAN, A. RAYMOND, M. SINGH, R. R. THOMAS
densities refers to an inequality between t(Hi ; G), for some finite graphs Hi , that is valid for all graphs G. Many results and problems in extremal graph theory can be restated as inequalities between homomorphism densities [14,19]. The Cauchy–Schwarz calculus of Razborov [19] has been one of the powerful tools used to verify density inequalities for graphs and hypergraphs [6,9,14,20]. This proof method is equivalent to the general sum of squares (sos) proof method that has been widely used in optimization [2]. Moreover, sos proofs naturally yield a computerized search via semidefinite programming. It was shown by Lov´ asz and Szegedy [16] that every true inequality between homomorphism densities is a limit of inequalities arising from Cauchy–Schwarz calculus. On the other hand, Hatami and Norine [10] show significant computational limitations on verifying inequalities between homom
Data Loading...
