The study of limit objects of growing combinatorial structures.
This talk: graph limits $${\color{orange}\mathcal{G}} = (G_i)_{i=1}^\infty,$$ where $G_i$ is a graph on $i$ vertices.
Flag algebras' limit functionals $$\phi\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{orange}\mathcal{G}= (G_i)_{i=1}^\infty$ is $$\phi({\color{green}H}) := \lim_{i\to\infty} \mathbb{P}[{\color{red}\sigma_i}({\color{green}H}) \text{ is a subgraph of }{\color{orange}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 $$H(\mathcal{G}) = \phi_{\mathcal{G}}(H).$$
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.
We saw that triangle free graphs have at most edge density $\frac{1}{2}$.
What happens if we allow some triangles?
Razborov introduces two derivatives:
Lovász translates the definition to graphons.
Diao, Guillot, Khare, Bajaratnam consider Gateaux derivatives in the space of graphons.
Let ${\color{orange}f}$ be a linear combination of subgraph densities, with minimizer $\mathcal{G}$ .
We can add additional constraints to optimization problems!
We can find better SOS certificates in the quadratic module given by these constraints.
Problem: We have to pic the elements "independently enough".
We show that the proofs generalize to more complicated actions on three or more vertices.
Main observation: We only ever need to apply the operation $\Theta(n^2)$ times! We can construct bigger "independent" sets probabilistically.
For fixed edge density $\rho$, the Erdős–Rényi random graph $\mathrm{ER}(\rho, n)$ minimizes the density of every bipartite graph as $n\to\infty$.
For every bipartite graph $H$,