Graph densities, matrices, positivity

A central theme in extremal combinatorics is determining when random constructions are optimal. Notable examples include problems in Ramsey theory, Sidorenko’s conjecture, and Lovász’s positivity conjecture. As Lovász observed, many of these questions can be recast as determining the nonnegativity of linear inequalities in graph densities, offering an analytic and algorithmic perspective on inherently combinatorial problems. In this talk, we discuss techniques and limitations for establishing such inequalities, and highlight a somewhat surprising connection to eigenvalues of matrix products.

For information about the Richard P. Stanley Seminar in Combinatorics, visit… https://math.mit.edu/combin/