The Flag Algebra of Rooted Binary Trees

Daniel Brosch

(joint work with Diane Puges)

University of Klagenfurt

April 15, 2023

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

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

Extremal graph theory

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

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

Investigating nonnegativity

Extremal tree theory

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

Scaling limits - compact metric spaces

Sparse limits of trees

^{[Bubeck, Linial, 2014]}

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

$$\Rightarrow$$

Subtrees

$$\Rightarrow$$

Subtrees

$$\Rightarrow$$

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

Questions

• What are the inducibilities of trees?
  
  
  Inducibility of $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

$\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}$

Irrational inducibility?

Irrational inducibility?

Outer approximation of tree profiles

Outer approximation of tree profiles

Outer approximation of tree profiles

Open questions

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