$$\require{color}$$ $$\definecolor{darkorange}{rgb}{0.8, 0.45, 0}$$

The Flag Algebra of Rooted Binary Trees

Joint work with Diane Puges and Stephan Wagner


Daniel Brosch

University of Klagenfurt

Europt, August 25, 2023

Is the set of trees convex?

Is the set of trees convex?

How many copies of a small tree can we fit into a very big tree?

Is the set of trees convex?

How many copies of a small tree can we fit into a very big tree?

And what does this even mean?

Is the set of trees convex?

How many copies of a small tree can we fit into a very big tree?

And what does this even mean?

Extremal graph theory

We are interested in limit objects of sequences of graphs $$ \mathcal{G} = (G_i)_{i\geq 0},$$ where $G_i$ is a graph on $i$ vertices.

How many edges can there be in a triangle free graph?

Graphons (Graph-functions)

[Lovász, Szegedy, 2006]

Limits of adjacency matrices: symmetric measurable functions $$W\colon[0,1]^2\to[0,1]$$

Flag Algebras

[Razborov, 2007]

Record only the limits of subgraph densities: $$\phi_{\mathcal{G}}(H) = \lim_{i\to\infty} (\text{density of $H$ in $G_i$}).$$ Flag Algebras consider the relations between different values $\phi_{\mathcal{G}}(H)$ and $\phi_{\mathcal{G}}(H')$.

Subgraph densities

We define the (non-induced) density of a finite graph $\color{darkorange}H$ in $\mathcal{G}$ as $$\phi_{\mathcal{G}}({\color{darkorange}H}):= \lim_{i\to\infty} \text{density of $\color{darkorange}H$ in $G_i$}$$

$$=\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.

Triangle free graphs

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?

Multiplying subgraph densities

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):

Flag Sums-of-Squares

  • Flags $F$ send graph sequences to real numbers: $$ F (\mathcal{G}) \in [0,1]$$
  • Then so do real linear combinations of flags
    The literature calls these "Quantum graphs".
  • Squares of real numbers are nonnegative:

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.

Polynomial Sums-of-Squares

  • Let ${\color{darkorange}[x]} = (m_1,\ldots, m_k)^\top$ be a vector containing a finite subset of a basis of $\mathbb{R}{\color{darkorange}[x]}$.

Polynomial Sums-of-Squares

  • Let ${\color{darkorange}[x]} = (m_1,\ldots, m_k)^\top$ be a vector containing a finite subset of a basis of $\mathbb{R}{\color{darkorange}[x]}$.
  • We can write polynomials in the form $$\small p = \sum_{i=1}^k c_i m_i = c^\top{\color{darkorange}[x]}$$

Polynomial Sums-of-Squares

  • Let ${\color{darkorange}[x]} = (m_1,\ldots, m_k)^\top$ be a vector containing a finite subset of a basis of $\mathbb{R}{\color{darkorange}[x]}$.
  • We can write polynomials in the form $$\small p = \sum_{i=1}^k c_i m_i = c^\top{\color{darkorange}[x]}$$
  • And squares as $$\small p^2 = (c^\top{\color{darkorange}[x]})^2 = {\color{darkorange}[x]}^\top (cc^\top) {\color{darkorange}[x]} = \langle c c^\top, {\color{darkorange}[x]}{\color{darkorange}[x]}^\top\rangle$$

Polynomial Sums-of-Squares

  • And squares as $$\small p^2 = (c^\top{\color{darkorange}[x]})^2 = {\color{darkorange}[x]}^\top (cc^\top) {\color{darkorange}[x]} = \langle c c^\top, {\color{darkorange}[x]}{\color{darkorange}[x]}^\top\rangle$$
  • Sums-of-squares correspond to PSD matrices: $$\small \sum p_i^2 = \left\langle \sum c_ic_i^\top, {\color{darkorange}[x]}{\color{darkorange}[x]}^\top\right\rangle =\left\langle M, {\color{darkorange}[x]}{\color{darkorange}[x]}^\top\right\rangle,$$ for some $M \in \mathbb{S}^n_+$.

Flag Sums-of-Squares

  • Let ${\color{darkorange}\mathcal{F}}$ be a (finite) vector of flags.

Flag Sums-of-Squares

  • Let ${\color{darkorange}\mathcal{F}}$ be a (finite) vector of flags.
  • Linear combinations of flags are of the form $$f = c^\top {\color{darkorange}\mathcal{F}}.$$

Flag Sums-of-Squares

  • Let ${\color{darkorange}\mathcal{F}}$ be a (finite) vector of flags.
  • Linear combinations of flags are of the form $$f = c^\top {\color{darkorange}\mathcal{F}}.$$
  • Unlabelled squares can be written as

Flag Sums-of-Squares

  • Linear combinations of flags are of the form $$f = c^\top {\color{darkorange}\mathcal{F}}.$$
  • Unlabelled squares can be written as

  • Flag sums-of-squares are of the form
    for positive semidefinite matrices $M$.

Flag Sums-of-Squares

  • Flag sums-of-squares are of the form
    for positive semidefinite matrices $M$.

In practice: Use "smarter" hierarchies, block diagonalized by combinatorial ideas and/or symmetries.

Graph profiles

We saw that triangle free graphs have at most edge density $\frac{1}{2}$.


What happens if we allow some triangles?

[Razborov, 2008]

Investigating nonnegativity

Let $p=a_1 G_1 + a_2 G_2 + \ldots + a_k G_k$ be a linear combination of unlabeled graphs.


[Lovász, Szegedy 2009]:
If $p\geq 0$, then $p + \varepsilon$ is a SOS for any $\varepsilon > 0$.


[Hatami, Norin, 2011]:
The question "Does $p \geq 0$ hold?"
is undecidable.

Extremal tree theory

Let $\mathcal{T} = (T_i)_{i\geq 0}$ be a sequence of trees, where $T_i$ has $i$ vertices. Let $S$ be a finite tree. $$\phi_{\mathcal{T}}({\color{darkorange}S}):=\lim_{i\to\infty} \mathbb{P}[{\color{green}\sigma_i}({\color{darkorange}S}) \text{ is a subtree of }T_i ] {\color{red}=0}.$$

All subtree densities are $0$.

  • The induciblity of any tree is zero.
  • All profiles of trees are $\{0\}$.
  • Deciding nonnegativity of quantum trees is trivial.

The end

The end

?

Scaling limits - compact metric spaces

[Picture by Igor Kortchemski]

Scaling limits - compact metric spaces


Still unclear how to define subtree densities.

Sparse limits of trees

[Bubeck, Linial, 2014]

At every $n$, normalize the sum of densities of trees with the same number of vertices to be $1$.

For a tree ${\color{darkorange}S}$ with $k$ vertices we set $$\phi_{\mathcal{T}}({\color{darkorange}S}):= \lim_{i\to\infty}\frac{\text{number of copies of ${\color{darkorange}S}$ in $T_i$}}{\text{number of trees with $k$ vertices in $T_i$}}$$

Sparse limits of trees

[Bubeck, Linial, 2014]

  • Profiles of trees with the same number of vertices are convex.

  • It is unclear how to extend flag algebras to this setting.

A change of perspective

[Czabarka, Székely, Wagner, 2017]

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.)

A change of perspective

[Czabarka, Székely, Wagner, 2017]

Motivation: phylogenetic trees, tanglegrams

Subtrees

Subtrees





$$\longrightarrow$$

Subtrees





$$\longrightarrow$$

Subtrees





$$\longrightarrow$$


Subtree densities

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})$.


We can encode the limit object as sequence $$(\phi_{\mathcal{T}}({\color{darkorange}S_1}),\phi_{\mathcal{T}}({\color{darkorange}S_2}),\phi_{\mathcal{T}}({\color{darkorange}S_3}),\ldots )\in [0,1]^{\aleph_0}.$$

Questions

  • What are the inducibilities of trees?

    Inducibility of $S= \mathrm{Ind}(S) :=\max_\mathcal{T}\phi_\mathcal{T}(S)$

    Various upper and lower bounds by Wagner et al.

  • Are profiles of trees convex?

    Open!

The flag algebra of binary rooted trees

$\varnothing \equiv 1$

$\equiv 1$

$\equiv 1$

$\equiv 1$

$+$ $\equiv 1$

Products of subtree densities

$\cdot$ $\stackrel{?}{=}\large($ $\large)$
$\cdot$ $=$ $+$
$\cdot$ $= \frac{9}{5}$ $+\frac{9}{5}$ $+\frac{3}{5}$

Inducibility of small trees


$\mathrm{Ind}\bigg($ $\bigg)\leq 1.0$
$\mathrm{Ind}\bigg($ $\bigg)\leq 1.0$
$\mathrm{Ind}\bigg($ $\bigg)\leq 1.0$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.42857$
$\mathrm{Ind}\bigg($ $\bigg)\leq 1.0$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.66667$
$\mathrm{Ind}\bigg($ $\bigg)\leq 1.0$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.24718$
$\mathrm{Ind}\bigg($ $\bigg)\leq 1.0$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.19166$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.32258$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.46875$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.34121$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.20738$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.16972$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.25593$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.34568$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.24722$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.20864$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.2381$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.10488$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.08879$
$\mathrm{Ind}\bigg($ $\bigg)\leq 1.0$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.14409$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.54688$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.10891$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.15392$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.10069$
$\mathrm{Ind}\bigg($ $\bigg)\leq 1.0$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.13499$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.13142$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.07846$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.04778$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.27344$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.29397$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.22385$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.4375$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.10921$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.05062$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.14794$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.07021$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.15873$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.15785$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.11242$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.0618$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.3156$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.1106$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.21818$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.07672$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.05459$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.32813$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.07269$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.16773$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.14118$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.03742$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.06838$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.0546$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.06361$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.06572$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.06916$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.09701$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.10656$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.05395$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.1674$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.30674$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.15159$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.04657$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.19236$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.15381$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.10694$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.03393$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.09637$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.02046$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.08361$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.03807$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.12347$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.11441$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.49219$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.07703$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.20609$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.09881$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.15142$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.11154$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.13361$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.0417$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.06798$
$\mathrm{Ind}\bigg($ $\bigg)\leq 1.0$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.03665$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.03196$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.12142$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.17236$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.04644$
$\mathrm{Ind}\bigg($ $\bigg)\leq 0.10636$

Irrational inducibility?

[Dossou-Olory, Wagner, 2019]:

$0.247071\leq\mathrm{Ind}\bigg($ $\bigg)\leq 0.24745$

Irrational inducibility?

[Dossou-Olory, Wagner, 2019]:

$0.247071\leq\mathrm{Ind}\bigg($ $\bigg)\leq{\color{red} 0.24718}\leq 0.24745$

Outer approximation of tree profiles

We can obtain a lower bound of the profile of two trees ${\color{darkorange}S},{\color{green}T}$ on the interval ${\color{darkorange}S}\in[a,b]\subseteq [0,1]$ by approximating $$ \begin{align*} \max \enspace&\int_{a}^{b} f_\text{lower}(x) \,dx \\ \text{s.t.}\enspace&{\color{green}T} - f_\text{lower}({\color{darkorange}S}) \geq 0\text{ if ${\color{darkorange}S}\in[a,b]$},\\ &f_\text{lower}\in\mathbb{R}[x] \end{align*} $$ using flag sums-of-squares.

Outer approximation of tree profiles

For ${\color{darkorange}S}=$ and ${\color{green}T}=$ :

Outer approximation of tree profiles

Open questions

  • Is the question "Is this linear combination of tree-densities nonnegative?" decidable?
  • Is the inducibility of irrational?
  • Can we define limit objects in the form of "Tree-ons"?