Department of Mathematics - Master Calendar

Speaker: Fan Wei (Duke University)

Title. Decidability for 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? In this talk I will talk about some recent development on this topic and related questions for formal product of matrices.