The study of limit objects of growing combinatorial structures.
This talk: graph limits $${\color{darkorange}\mathcal{G}} = (G_i)_{i=1}^\infty,$$ where $G_i$ is a graph on $i$ vertices.
Flag algebras' limit functionals $$\phi_{\mathcal{G}}\colon \{\text{finite graphs}\}\to[0,1]$$ correspond to graphons "up to isomorphism".
They form a compact metric space.
The density of a graph $\color{green}H$ in $\color{darkorange}\mathcal{G}= (G_i)_{i=1}^\infty$ is $$\phi_{\mathcal{G}}({\color{green}H}) := \lim_{i\to\infty} \mathbb{P}[{\color{red}\sigma_i}({\color{green}H}) \text{ is a subgraph of }{\color{darkorange}G_i}],$$ where ${\color{red}\sigma_i}$ is a random permutation in $S_i$.
Maximize the edge density in a triangle free sequence $\mathcal{G}$ of graphs of increasing size:
We saw that
but how can we prove an upper bound?
To multiply two subgraph densities, we glue together the graphs:
These relationships are independent of $\mathcal{G}$, motivating the definition
where a graph $H$ now stands for the function $$\small H(\mathcal{G}) = \phi_{\mathcal{G}}(H)= \lim_{i\to\infty} \mathbb{P}[{\sigma_i}({H}) \text{ is a subgraph of }{G_i}].$$
We can fix entries of the $\sigma_i$ to fix (flag) some vertices, and extend the gluing operation to partially labeled graphs (Flags):
We can average Flags over all choices of labels, unlabeling them:
We can now find an upper bound for the edge density in triangle free graphs:
As with polynomial optimization, we can model Flag-SOS using semidefinite programming.
In practice: Use "smarter" hierarchies, block diagonalized by combinatorial ideas and/or symmetries.
We saw that triangle free graphs have at most edge density $\frac{1}{2}$.
What happens if we allow some triangles?
Applications to Turán and Ramsey type problems, inducibility, fractalizers,...