Extremal Graph Theory and Sums of Squares

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

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.