Title

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

Flag Sums of Squares for Sidorenko's Conjecture

Daniel Brosch

University of Klagenfurt

November 13, 2023

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.

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

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.

Sidorenko's Conjecture

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

Progress on Sidorenko's Conjecture

[Mulholland, Smith 1959]: paths

Progress on Sidorenko's Conjecture

[Mulholland, Smith 1959]: paths
[Sidorenko 1991]: trees, even cycles, $K_{n,m}$, bipartite graphs with at most $4$ vertices on one side

Progress on Sidorenko's Conjecture

[Mulholland, Smith 1959]: paths
[Sidorenko 1991]: trees, even cycles, $K_{n,m}$, bipartite graphs with at most $4$ vertices on one side
[Hitomi 2008]: Hypercube graphs, norming graphs

Progress on Sidorenko's Conjecture

[Sidorenko 1991]: trees, even cycles, $K_{n,m}$, bipartite graphs with at most $4$ vertices on one side
[Hitomi 2008]: Hypercube graphs, norming graphs
[Conlon, Fox, Sudakov 2010]:
If one vertex connects to all vertices on the other side

Progress on Sidorenko's Conjecture

[Hitomi 2008]: Hypercube graphs, norming graphs
[Conlon, Fox, Sudakov 2010]:
If one vertex connects to all vertices on the other side
[Sidorenko 1991], [Li, Szegedy 2011], [Kim, Lee, Lee 2013]:
Various recursive constructions

Progress on Sidorenko's Conjecture

[Conlon, Fox, Sudakov 2010]:
If one vertex connects to all vertices on the other side
[Sidorenko 1991], [Li, Szegedy 2011], [Kim, Lee, Lee 2013]:
Various recursive constructions
[Conlon, Lee 2018]: For every bipartite graph $H$ exists a $p$ such that the $p$-blow up of $H$ is Sidorenko.

Progress on Sidorenko's Conjecture

[Sidorenko 1991], [Li, Szegedy 2011], [Kim, Lee, Lee 2013]:
Various recursive constructions
[Conlon, Lee 2018]: For every bipartite graph $H$ exists a $p$ such that the $p$-blow up of $H$ is Sidorenko.
[Blekherman, Raymond, Singh, Thomas 2018]:
$P_3-e^3$ is not (rational) flag-SOS. The smallest open case $K_{5,5}\setminus C_{10}-e^{15}$ is not not (rational) flag-SOS.

Progress on Sidorenko's Conjecture

[Blekherman, Raymond, Singh, Thomas 2018]:
$P_3-e^3$ is not (rational) flag-SOS. The smallest open case $K_{5,5}\setminus C_{10}-e^{15}$ is not not (rational) flag-SOS.
[Garg, Raymond, Redlich 2022]: Many cases of Sidorenko's Conjecture cannot be shown using flag-SOS. Most known cases can potentially be recovered using flag-SOS.

Interest for alternative proofs of $P_3-e^3\geq 0$!

The space of graph limits

Linear combinations of subgraph densities are continuous functions in this space.
How can we move in the space without leaving it?
Can we define directional derivatives of flags?

Derivatives of flags

[Razborov, 2007] introduces two derivatives:

In direction of deleting a vertex $v$.
In direction of deleting an edge $e$.

Lovász translates the definition to graphons.

Diao, Guillot, Khare, Bajaratnam consider Gateaux derivatives in the space of graphons.

$\partial_{\color{darkorange}v}$: Deleting the vertex ${\color{orange}v}$

Usual directional derivatives:

$\partial_{\color{darkorange}v}$: Deleting the vertex ${\color{orange}v}$

Usual directional derivatives:

Vertex deletion derivative for flags:

$\partial_{\color{darkorange}v}$: Deleting the vertex ${\color{orange}v}$

Vertex deletion derivative for flags:

$\partial_{\color{darkorange}e}$: Deleting the edge ${\color{orange}e}$

How to actually "move" in a direction?

If $\partial_{\color{darkorange}v}(f)(\mathcal{G}) < 0$, can we actually find a new graph limit $\mathcal{G}'$ with $f(\mathcal{G}') < f(\mathcal{G})$?

Problem: We can only delete a vertex ${\color{darkorange}v}$ (or edge) once. In a graph limit, deleting one vertex does not shift its subgraph densities!

Solution: We instead assume that $\partial_{\color{darkorange}v}(f)(\mathcal{G}) < 0$ for a positive fraction of vertices $v$. We can then (very carefully) pick a subset of these to delete.

Using the derivatives in optimization

Let ${\color{orange}f}$ be a linear combination of subgraph densities, with minimizer $\mathcal{G}$ .

Then $\partial_{\color{red}v} {\color{orange}f}(\mathcal{G}) = 0$ for nearly all vertices ${\color{red}v}$.
Then $\partial_{\color{red}e} {\color{orange}f}(\mathcal{G}) \geq 0$ for nearly all edges ${\color{red}e}$.

We can add additional constraints to optimization problems!

Using the derivatives in optimization

$$ \begin{align} \min_{\mathcal{G}}\enspace& {\color{orange}f}(\mathcal{G}) &= \min_{\mathcal{G}}\enspace& {\color{orange}f}(\mathcal{G})\\ &&\text{s.t. }& \mathbb{P}[\partial_{\color{red}v} {\color{orange}f}(\mathcal{G}) = 0]=1, \\ &&& \mathbb{P}[\partial_{\color{red}e} {\color{orange}f}(\mathcal{G}) \geq 0]=1. \end{align} $$

We can find better SOS certificates in the quadratic module given by these constraints.

Proof idea

Assume there is an $\varepsilon$-subset of vertices/edges that violate the constraints.
Show that there exists a subset of $\Theta(n)$ vertices resp. $\Theta(n^2)$ edges we can remove consecutively to shift the objective.

Problem: We have to pick the elements "independently enough".
Otherwise we cannot guarantee that after removing some vertices, the derivatives of the remaining vertices do not change their sign.

Main contribution

We show that the proofs generalize to more complicated actions on three or more vertices. The resulting functions are derivations of the flag algebra (i.e. Leibniz's rule holds).

Main observation: We only ever need to apply the operation $\Theta(n^2)$ times! We can construct bigger "independent" sets probabilistically.

Hinge-switch derivative

We define the derivative $\partial_{\text{hinge}}$ based on the operation on vertices $i,j,k$, which swaps the edges $\{i,j\}$ and $\{i,k\}$.

Edge-swap derivative

We define the derivative $\partial_{\text{swap}}$ based on the operation on vertices $i,j,k, l$, which swaps the edges $\{i,j\}$ and $\{k,l\}$.

And many more complicated ones!

SOS based proof for small cases of Sidorenko's

We found an exact (and easily human checkable) flag-SOS certificate for \begin{align} 0 = \min\enspace& P_3 - e^3\\ \text{s.t. }& \mathbb{P}[\partial_{\text{swap}}(P_3 - e^3) \geq 0 ]=1 \end{align}

And numeric certificates for the two next bigger cases with no "pure" flag-SOS based proof.

SOS-based proof of $P_3-e^3\geq 0$

In a minimizer, we have

Software:

Julia package implementing multiple symmetry reduced flag-SOS hierarchies for arbitrary Flags:
https://github.com/DanielBrosch/FlagSOS.jl


        pkg> add FlagSOS

The package also supports non-asymptotic problems, and problems that are not combinatoric (e.g. SOS for (multi-)symmetric functions in $n$ variables).

Paper:

Very much work in progress. Other work related to flag algebras is in my thesis.