Departmental Colloquium
Fan Wei
Duke
Graph density inequalities
Abstract: Given a graph $H$ and a (weighted) graph $G$, let $t(H, G)$ denote the density of $H$ in $G$. Given a fixed set of graphs $H_1, H_2, \dots, H_k$, what can we say about the possible tuples $(t(H_1, G), t(H_2, G), \dots, t(H_k, G))$ as $G$ ranges over all (weighted) graphs? What inequalities of the form $\sum c_i t(H_i, G) \geq 0$ are always valid? Can all such inequalities be verified by sum of squares? When are such inequalities optimized when $G$ is a random graph? These questions are connected to several long-standing open problems in extremal combinatorics. In this talk, we will discuss recent progress on these problems.
Friday January 30, 2026 at 3:00 PM in 636 SEO