Extremal Combinatorics in Julia

Daniel Brosch

University of Klagenfurt

ÖMG Tagung, Graz, September 19, 2023

Software: FlagSOS.jl

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 $$[\![f^2]\!]=\left\langle cc^\top, [\![{\color{darkorange}\mathcal{F}}{\color{darkorange}\mathcal{F}}^\top]\!]\right\rangle$$

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 $$[\![f^2]\!]=\left\langle cc^\top, [\![{\color{darkorange}\mathcal{F}}{\color{darkorange}\mathcal{F}}^\top]\!]\right\rangle$$
• Flag sums-of-squares are of the form $$\left\langle M, [\![{\color{darkorange}\mathcal{F}}{\color{darkorange}\mathcal{F}}^\top]\!]\right\rangle$$ for positive semidefinite matrices $M$.

Flag Sums-of-Squares

• Flag sums-of-squares are of the form $$\left\langle M, [\![{\color{darkorange}\mathcal{F}}{\color{darkorange}\mathcal{F}}^\top]\!]\right\rangle$$ 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

Software: FlagSOS.jl

Razborov's flag algebras

And yet all existing software focuses on specific flag algebras.

FlagSOS.jl is designed to be easily extendable to new theories.

Currently implemented theories

• Graphs,
• Directed graphs,
• Hypergraphs,
• Symmetric functions,
• Constant weight codes,
• Phylogenetic rooted binary trees,
• Colored, (partially) labeled, and induced variants.

New theories can be added by definining a few simple black-box functions. The package provides functions to canonically label and generate models up to isomorphism.

Supported problem types

Available hierarchies

• Lasserre hierarchy:
  For problems formulated in sparse, large models. Based on polynomial optimization, representation theory and consistent sequences.
• Razborov hierarchy:
  For problems formulated in small, dense models. Based on Möbius transforms of finite lattices. Also implemented in Vaughan's Flagmatic (2011).

Planned: Sums-of-binomial-squares, entropy based optimization

Installation

            pkg> add "https://github.com/DanielBrosch/FlagSOS.jl"
          

            pkg> add FlagSOS
          

Examples:

Advanced example: Extremal tree theory

All subtree densities are $0$.

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 $\color{darkorange}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= \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

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

To-Do's

• Finish any of the projects the software is used in.
• Documentation needs work.
• Automatic generation of exacty rational certificates.
• More model theories, hierarchies?

For details (for now): Check out my thesis!