Finitely forcible graphons with an almost arbitrary structure

Finitely forcible graphons with an almost arbitrary structure, Discrete Analysis 2020:9, 36 pp.

A basic result from the theory of quasirandom graphs, due to Andrew Thomason, is that if $G$ is a graph with $n$ vertices and density $p$, and if the number of 4-cycles in $G$ is approximately $p^4\binom n4$, then $G$ resembles a random graph of the same density. In particular, between any two sets $A$ and $B$ of vertices the number of edges is approximately $p|A||B|$. (Here, “approximately” means "to within a small fraction of $n^2$, so the statement is non-trivial only for sets $A$ and $B$ that are not too small.)

This conclusion can be thought of as saying that a large quasirandom graph of density $p$ is close, in a suitable sense, to the constant function that maps each pair of vertices to $p$.

Let us say that the subgraph density of a graph $H$ with $k$ vertices inside a graph $G$ with $n$ vertices is the probability that a random map from the vertices of $H$ to the vertices of $G$ takes every edge of $H$ to an edge of $G$. Then Thomason’s results says that if the subgraph density of a single edge in $G$ is $p$ and the subgraph density of a 4-cycle is $p^4$, then $G$ is approximately equal to the constant function $p$.

This point of view was developed by Lovász and Szegedy into the theory of graph limits. They defined a graphon to be a symmetric measurable function $W:[0,1]^2\to[0,1]$ and showed that every sequence of graphs has a subsequence that converges in an appropriate sense to a graphon. To give an idea of how this works, a sequence of quasirandom graphs of density $p$ converges to the constant function $p$. More generally, one can apply Szemerédi’s regularity lemma to obtain a partition of the vertices into sets $V_1,\dots,V_k$ of roughly equal density such that almost all the bipartite graphs induced by pairs $(V_i,V_j)$ are quasirandom of density $d_{ij}$, and such a graph is close to the graphon where one partitions $[0,1]$ into intervals $I_1,\dots,I_k$ of size $1/k$ and defines $W(x,y)$ to be $d_{ij}$ if $x\in I_i$ and $y\in I_j$.

The notion of subgraph density makes sense for graphons as well: we define the subgraph density of $H$ to be the expectation of $\prod_{xy\in E(H)}W(\phi(x),\phi(y))$ for a random map $\phi:V(H)\to[0,1]$. Then Thomason’s result turns out to be equivalent to the statement that the constant function $p$ is the only graphon such that the edge density is $p$ and the 4-cycle density is $p^4$.

More generally, a graphon is said to be finitely forcible if it is completely determined by the densities of a finite number of subgraphs. Lovasz and Szegedy conjectured that all finitely forcible graphons have a certain simple form. This conjecture was disproved in a very strong way by Cooper, Král’ and Martins, who showed that if $W$ is an arbitrary graphon, then there is a finitely forcible graphon $W_0$ such that $W$ is a subgraphon of $W$ induced by a subset of the vertices of measure at least $1/14$.

With a careful running of their argument, one can improve this fraction $1/14$ to $1/2-\epsilon$. This paper goes even further, and improves it to $1-\epsilon$. One can think of the result as saying that every graphon is close to a finitely forcible graphon (but the notion of closeness here is much stronger than the notion discussed above). Another message from the paper (and indeed from the earlier paper of Cooper, Král’ and Martins) is that fairly simple extremal problems in graph theory can have unique solutions that are very complicated indeed.