$$=\lim_{i\to\infty} \mathbb{P}[{\color{green}\sigma_i}({\color{darkorange}H}) \text{ is a subgraph of }G_i ],$$ where ${\color{green}\sigma_i}\colon V({\color{darkorange}H})\to V(G_i)$ is a random injective mapping.
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.
Unlabelled squares can be written as
Unlabelled squares can be written as
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?
All subtree densities are $0$.
Profiles of trees with the same number of vertices are convex.
It is unclear how to extend flag algebras to this setting.
What happens, if we only consider the leaves of trees to be the "vertices" of the tree?
(Inner vertices are now part of the "edges" of the tree.)
Motivation: phylogenetic trees, tanglegrams
Let $\mathcal{T} = (T_i)_{i\geq 0}$ be a sequence of trees, where $T_i$ has $i$ leaves. Let $S$ be a finite tree. $$\phi_{\mathcal{T}}({\color{darkorange}S}):=\lim_{i\to\infty} \mathbb{P}[\left.(T_i)\right|_{ {\color{green}V_i}} \cong {\color{darkorange}S}],$$ where $\color{green}V_i$ is a random subset of leaves of $T_i$ of size $V({\color{darkorange}S})$.