Extremal Graph Theory and Sums of Squares

工程、科学、经济和社会科学中的许多问题都涉及可以用图表示的复杂系统。例如，道路网络、人脑、社交网络以及蛋白质之间的相互作用都可以用图来表示。这些图包含有关原始问题的有价值的信息，但它们也往往非常大，以至于很难处理它们。研究这种大型图的一种技术是通过确定某些小型子图的流行程度来局部地理解它们，例如通过同态密度。此外，极值图论中的许多问题可以被视为证明同态密度不等式的有效性，这是本项目的核心主题。该项目还旨在使更高层次的数学，特别是离散数学，更广泛地接触到人口。 这个项目的目的是确定平方和方法的优势和局限性，以证明这种不平等涉及同态密度，利用其优势来解决长期存在的极值图论问题，并提供更好的证书时，平方和失败。更具体地说，PI将（i）调查有理平方和是否形成比平方和更严格更强的方法，（ii）研究图轮廓和平方轮廓的热带化，以更好地理解涉及图同态的二项式不等式，（iii）将这些工具用于极值图论问题，如Sidorenko猜想和树之间的图同态，以及（iv）比较其他非负性证书的表现，特别是非负性电路的总和，这是一种基于相对熵的方法。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Many problems in engineering, science, economics, and social sciences involve complicated systems that can be represented as graphs. For example, road networks, the human brain, social networks, and interactions between proteins can all be represented as graphs. These graphs contain valuable information about the original problem, but they also tend to be so large that it can be hard to work with them. One technique to study such large graphs is to understand them locally by determining how prevalent certain small subgraphs are, for example through homomorphism densities. Moreover, many questions from extremal graph theory can be viewed as certifying the validity of inequalities involving homomorphism densities, a theme that is central to this project. This project also seeks to make higher-level math, in particular discrete mathematics, accessible to a greater segment of the population. The objective of this project is to determine the strengths and limitations of the sums of squares method to certify such inequalities involving homomorphism densities, to capitalize on its strengths to solve longstanding problems in extremal graph theory, and to provide better certificates whenever sums of squares fail. More specifically, the PI will (i) investigate whether rational sums of squares form a strictly stronger method than sums of squares, (ii) study the tropicalizations of graph profiles and sums of squares profiles to better understand binomial inequalities involving graph homomorphisms, (iii) use these tools on extremal graph theoretical problems such as Sidorenko's conjecture and graph homomorphisms between trees, and (iv) compare how other certificates of nonnegativity fare, in particular sums of nonnegative circuits, a method based on relative entropy.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.