# Existence of a symmetric bipodal phase in the edge-triangle model

Joe Neeman and Charles Radin and Lorenzo Sadun  Joe Neeman
Department of Mathematics
The University of Texas at Austin
Austin, TX 78712<EMAIL_ADDRESS>Charles Radin
Department of Mathematics
The University of Texas at Austin
Austin, TX 78712<EMAIL_ADDRESS>Lorenzo Sadun
Department of Mathematics
The University of Texas at Austin
Austin, TX 78712<EMAIL_ADDRESS>
###### Abstract.

In the edge-triangle model with edge density close to 1/2 and triangle density
below 1/8 we prove that the unique entropy-maximizing graphon is symmetric
bipodal. We also prove that, for any edge density $e$ less than
$e_{0}=(3-\sqrt{3})/6\approx 0.2113$ and triangle density slightly less than
$e^{3}$, the entropy-maximizing graphon is not symmetric bipodal.

This work was partially supported by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) under Germany’s Excellence Strategy – EXC-2047/1 –
390685813, and by a fellowship from the Alfred P. Sloan Foundation. This
material is based upon work supported by the National Science Foundation under
Grant Nos. 2145800 and 2204449. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the author(s) and do
not necessarily reflect the views of the National Science Foundation.

##  1\. Introduction and Results

###  1.1. Results

We study emergent smoothness with respect to change of competing constraints
in asymptotically large dense random graphs. More specifically, we determine
and study smooth phases separated by sharp transitions. We derive a new phase
in the model with sharp constraints on edge and triangle densities. The phase
is “symmetric bipodal” and we show how to use its symmetry to distinguish the
phase intrinsically from other phases. Unlike in previous work, graphs in this
phase are not small perturbations of Erdős-Rényi graphs; this requires new
techniques, which we develop.

Let $g(x,y)$ be a graphon, a measurable symmetric function
$g:[0,1]^{2}\to[0,1]$. Let

(1) $\varepsilon(g)=\iint g(x,y)\,dx\,dy,\qquad\tau(g)=\iiint
g(x,y)g(y,z)g(z,x)\,dx\,dy\,dz,$

and

(2) $S(g)=\iint H[g(x,y)]\,dx\,dy,\hbox{ where
}H(u)=-[u\ln(u)+(1-u)\ln(1-u)].$

The integrals $\varepsilon(g)$ and $\tau(g)$ represent the overall edge and
triangle densities of graphs whose adjacency matrices are close to the graphon
in the “cut metric” [17], while $S(g)$ is proportional to the entropy of a
random process for generating such graphs. We refer to $S(g)$ as the “entropy
of the graphon $g$,” distinct but related to the Boltzmann entropy defined in
the next paragraph. The quantities $\varepsilon(g)$, $\tau(g)$ and $S(g)$ are
all invariant under measure-preserving transformations of $[0,1]$. All
statements about uniqueness of graphons should be understood to mean “unique
up to measure-preserving transformations of $[0,1]$.”

We consider constrained systems, where the edge and triangle densities are
constrained to a vanishingly small tolerance as follows. For each achievable
ordered pair $(e,t)$, we define the Boltzmann entropy in terms of the
partition function $Z^{n,\delta}_{e,t}$, which is the cardinality of the set
of graphs on $n$ nodes with edge density in the interval $(e-\delta,e+\delta)$
and triangle density in the interval $(t-\delta,t+\delta)$. From the partition
function we define the Boltzmann entropy [27] as

(3) $B(e,t)=\lim_{\delta\searrow
0}\lim_{n\to\infty}\frac{1}{n^{2}}\ln\big{[}Z^{n,\delta}_{e,t}\big{]}.$

Using [6] we established [27] the variational formula

(4) $B(e,t)=\sup_{g\in\mathcal{G}_{e,t}}S(g),$

where

(5) $\mathcal{G}_{e,t}=\\{g\,|\,\varepsilon(g)=e,\tau(g)=t\\}.$

If the supremum of $S(g)$ is attained by a unique graphon
$g_{e,t}\in\mathcal{G}(e,t)$, then all but exponentially few large graphs with
the constrained edge and triangle densities are described by $g_{e,t}$. In
particular, the density of all possible subgraphs are given by integrals
involving $g_{e,t}$.

Our first major result is:

######  Theorem 1.

There is an open subset ${\mathcal{O}}$ of the $(e,t)$ plane, containing the
interval $e=\frac{1}{2}$, $0<t<\frac{1}{8}$, on which the unique
$S$-maximizing graphon is

(6) $g_{e,t}(x,y)=\begin{cases}e-(e^{3}-t)^{1/3},\ &0<x,y<\frac{1}{2}\hbox{ or
}\frac{1}{2}<x,y<1,\cr e+(e^{3}-t)^{1/3},\ &\,x<\frac{1}{2}<y\hbox{ or
}y<\frac{1}{2}<x.\end{cases}$

See Figures 1 and 2. The following is immediate by inspection.

######  Corollary 2.

$B(e,t)$ and the densities of all subgraphs are real analytic in $(e,t)$ in
${\mathcal{O}}$.

Figure 1. The open set $\mathcal{O}$ of Theorem 1 Figure 2. The piecewise-
constant optimal graphon of Theorem 1

Our second major result describes a region where the optimizing graphon is not
symmetric bipodal.

######  Theorem 3.

Let $e_{0}=(3-\sqrt{3})/6\approx 0.2113$. For any fixed edge density $e<e_{0}$
and any sufficiently small positive $\sigma$, the symmetric bipodal graphon
(6) does not maximize $S$ among graphons with triangle density
$t=e^{3}-\sigma^{3}$.

###  1.2. Background

This work is concerned with emergent features [1] of large dense simple
graphs, features that are only meaningful in the limit as the number $n$ of
vertices goes to infinity. We will concentrate on graphs with competing
constraints, specifically the prescribed densities $e$ and $t$, edges and
triangles, respectively. The emergent behavior is smoothness as a function of
$(e,t)$, of the Boltzmann entropy $B(e,t)$ and of all subgraph densities.

The study of graphs with competing constraints is an old topic in extremal
combinatorics. For graphs, the range of achievable values of the pair $(e,t)$,
and the graphs that achieve them, was completed in 2012 by Purkurko and
Razborov [23]: see Figure 3 for a distorted view of the “Razborov triangle”.

A graphon formalism was developed starting around 2006 [2, 3, 14, 15, 16] to
give a useful meaning to the asymptotic limits of dense graphs. A large
deviation principle (LDP) was added by Chatterjee and Varadhan in 2010 [6].
Using graphons we define a phase as a maximal connected open subset of the
Razborov triangle on which $B(e,t)$, and the density of every fixed subgraph
(e.g., the density of squares, pentagons, tetrahedra, $\ldots$) of a typical
graph, is an analytic function of $(e,t)$. The system is said to have a phase
transition wherever such quantities are not analytic. Usually this occurs at
the boundary of two or more phases, but sometimes there is an analytic path
from one side of a phase transition to another, as discussed in Section 7.
Note that if the optimal graphon in the variational formula (4) is not unique,
the densities of some subgraphs are not even well-defined, much less analytic;
by definition, such points of non-uniqueness can never lie within a phase.
Even when uniqueness does hold, it can be difficult to prove. On the other
hand, where there is a unique entropy-optimizing graphon $g_{e,t}$, all but
exponentially few large graphs are close to $g_{e,t}$; this facilitates the
analysis of emergent features. (Such uniqueness is known to fail in similar
models; see Section 5 in [11].)

Figure 3. The Razborov triangle, outlined in solid curves

This paper is part of a project begun in 2013 [27], following [5], to study
emergent analyticity of typical graphs with edge and triangle constraints in
the Razborov triangle. Using [6] we derived [27] the variational formula (4)
relating the Boltzmann entropy $B(e,t)$ to the graphon entropy $S(g)$. Let $G$
be a fixed subgraph, such as a square or pentagon or tetrahedron. When $S(g)$
achieves the value $B(e,t)$ at a unique graphon, all but exponentially few
graphs have the same density $t_{G}$ of $G$, so we can speak of $t_{G}$ being
a function of $(e,t)$ and ask whether that function is analytic. (Our method
was based on large deviations of $G(n,p)$ [6]; for an approach based on
$G(n,m)$ see [7].)

In 2015 we established [11] the existence of two open subsets of the Razborov
triangle, both with $t>e^{3}$, in which $B(e,t)$ and all subgraph densities
were real-analytic in $(e,t)$. To prove this we proved that the constrained
$S$-optimizing graphons were unique, and determined that they have a 2-block
(“bipodal”) [11] structure whose parameters were analytic in $(e,t)$. More
recently, we proved [21] a complementary result in the more difficult case of
undersaturated triangles ($t<e^{3}$) when $e>\frac{1}{2}$. This yielded the
satisfying result of a pair of open sets, $\mathcal{O}_{1},\mathcal{O}_{2}$,
on which the Boltzmann entropy $B(e,t)$ and all subgraph densities are
analytic, separated by the bounding curve $t=e^{3}$, on which the entropy
isn’t even differentiable [28]. See Figure 4.

Figure 4. The phase transition between $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$
was proven in [21].

Put another way, in [21] we proved the existence of two phases with
$e>\frac{1}{2}$, one just above the curve $t=e^{3}$ and one just below, with a
phase transition on the curve itself. As noted earlier, within each phase
there must be a unique $S$-optimizing graphon for each $(e,t)$. This optimal
graphon is called the “state” of the system. As discussed above, models of
dense graphs with sharp competing constraints are a natural extension of
extremal graph theory. We note there have been parallel studies within other
parts of extremal combinatorics, for instance permutations and sphere
packings; see Section 8.

One may reasonably ask how we know that the two open sets $\mathcal{O}_{1}$
and $\mathcal{O}_{2}$ actually belong to different phases; how can we rule out
the possibility that there is an analytic path between them, going around the
phase transition? Neither the $\mathcal{O}_{1}$ phase nor the
$\mathcal{O}_{2}$ phase seems to have any intrinsic property that clearly
rules out an analytic continuation between them. Such an analytic continuation
does not actually exist, since we previously showed [28] that $B(e,t)$ cannot
be differentiable at any point on the curve $t=e^{3}$ for any $0<e<1$. However
that isn’t a very satisfying explanation.

The “symmetric bipodal” phase whose existence we prove in this paper is
different. The symmetry provides an intrinsic difference between the new phase
and the $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$ phases. In Section 7 we
discuss the connection between our symmetry argument and the use of “order
parameters” in equilibrium statistical mechanics, and as a by-product we
clarify a problematic argument of Landau from the 1950s.

Another key difference between our new phase and the previously proven phases
is that proof of the symmetric bipodal phase is not limited to a small
neighborhood of the curve $t=e^{3}$. In [11], and again in [21], we studied
small perturbations of the Erdős-Rényi graph $G(n,p)$ and attempted to get the
greatest possible change in triangle count for the smallest possible entropy
cost. The results are closely related to moderate deviation estimates [20];
depending on the sizes of $n$ and $e^{3}-t$, a finite graph with triangle
density slightly less than $e^{3}$ can be viewed either as a typical $(e,t)$
graph or as a deviation of an Erdős-Rényi graph. When $e<1/2$, moderate
deviations estimates that apply when $n^{-1}\ll e^{3}-t\ll 1$ agree to leading
order with large deviations estimates.

This is reflected in the different method of proof. In Theorem 3, $\sigma$ is
not a small parameter. We can still do a power series expansion in $\sigma$,
but we have to estimate all terms, not just the first few.

##  2\. Definitions and Notation

Figure 5. The parameters of a bipodal graphon

A graphon is said to be bipodal if it is equivalent to a graphon with the
block structure shown in Figure 5. It is symmetric bipodal if $c=1/2$ and
$a=b$. To avoid questions about graphons being equivalent under measure-
preserving transformations of $[0,1]$, we restate the definition using
arbitrary measurable subsets $I_{1}$ and $I_{2}$ of $[0,1]$, rather than
intervals $[0,c]$ and $(c,1]$. A graphon is bipodal if there exist
complementary measurable subsets $I_{1}$ and $I_{2}$ such that $g(x,y)$ is
constant on $I_{1}\times I_{1}$, constant on $I_{2}\times I_{2}$, and constant
on $I_{1}\times I_{2}\cup I_{2}\times I_{1}$. A graphon is symmetric bipodal
if there exist complementary subsets $I_{1}$ and $I_{2}$, each of measure 1/2,
and a positive number $\sigma<e$, such that the graphon is

(7) $g(x,y)=\begin{cases}e-\sigma&(x,y)\in I_{1}\times I_{1}\cup I_{2}\times
I_{2},\cr e+\sigma&(x,y)\in I_{1}\times I_{2}\cup I_{2}\times
I_{1},\end{cases}$

The edge density, triangle density and entropy of a symmetric bipodal graphon
are

(8) $\varepsilon(g)=e,\qquad\tau(g)=e^{3}-\sigma^{3},\qquad
S(g)=\frac{1}{2}(H(e+\sigma)+H(e-\sigma)).$

Of course, this only makes sense if $\sigma\leq\min(e,1-e)$. Another
characterization of a symmetric bipodal graphon is that it is a rank-1
perturbation of a constant graphon, with

$g(x,y)=e-\sigma v_{1}(x)v_{1}(y),$

where $\int_{0}^{1}v_{1}(x)dx=0$ and $v_{1}(x)^{2}=1$ everywhere.

It was previously known that the unique optimal graphon on the open line
interval $e=1/2$, $t\in(0,1/8)$ was symmetric bipodal [28]. Our main result,
Theorem 1, extends this to an open set $\mathcal{O}$ containing the line
interval. It is convenient for our proofs to reformulate Theorem 1 as

######  Theorem 4.

For fixed $\sigma\in\left(0,\frac{1}{2}\right)$ and for all sufficiently small
$\delta$ (of either sign), the unique $S$-maximizing graphon with edge density
$e=\frac{1}{2}+\delta$ and triangle density $t=e^{3}-\sigma^{3}$ is symmetric
bipodal. Furthermore, the size of the allowed interval of $\delta$’s varies
continuously with $\sigma$.

######  Corollary 5.

The Boltzmann entropy $B(e,t)$ and the densities of all subgraphs are real
analytic functions of $(e,t)$ in the open set thus defined.

We expect that the region where the optimal graphon is symmetric bipodal is
not limited to the small open set described in Theorems 1 and 4. There is
considerable numerical evidence that this region, called the A(2,0) phase in
[13], is much bigger than that. However, there are provable limits to its
extent. Theorem 3 says that it does not extend to the curve $t=e^{3}$ when
$e<e_{0}\approx 0.2113$. Theorem 1 from [21], which we restate here, says that
it does not extend to the curve $t=e^{3}$ when $e>1/2$. It is an open question
whether the phase extends to the curve $t=e^{3}$ when $e_{0}<e<1/2$.

######  Theorem 6.

(Theorem 1 from [21]) There is an open subset ${\mathcal{O}}_{1}$ in the
planar set of achievable parameters $(e,t)$, whose upper boundary is the curve
$t=e^{3},\ 1/2<e<1$, such that at $(e,t)$ in ${\mathcal{O}}_{1}$ there is a
unique entropy-optimizing graphon $g_{e,t}$. This graphon is bipodal and for
fixed $(e,t)$, the values of $a,b,c,d$ can be approximated to arbitrary
accuracy via an explicit iterative scheme. These parameters can also be
expressed via asymptotic power series in $\sigma=(e^{3}-t)^{1/3}$ whose
leading terms are:

(9) $\displaystyle a$ $\displaystyle=$ $\displaystyle
1-e-\sigma+O(\sigma^{2})$ (10) $\displaystyle b$ $\displaystyle=$
$\displaystyle e-\frac{\sigma^{2}}{2e-1}+O(\sigma^{3})$ (11) $\displaystyle c$
$\displaystyle=$
$\displaystyle\frac{\sigma}{2e-1}-\frac{2\sigma^{2}}{2e-1}+O(\sigma^{3})$ (12)
$\displaystyle d$ $\displaystyle=$ $\displaystyle
e+\sigma+\frac{\sigma^{2}}{eH^{\prime}(e)}\left(H^{\prime}(e)-\left(e-\frac{1}{2}\right)H^{\prime\prime}(e)\right)+O(\sigma^{3}).$

######  Corollary 7.

$B(e,t)$ and the densities of all subgraphs are real analytic in $(e,t)$ in
the open set $\mathcal{O}_{1}$.

This corollary was proven in the last paragraph of the proof of Theorem 1 in
[21], although not included in the statement of the theorem.

The bulk of this paper is devoted to proving Theorem 4, which is tantamount to
proving Theorem 1. To explain the steps, we need some more notation. We
diagonalize $g(x,y)-e$, viewed as an integral operator, and write

(13) $g(x,y)=e+\sum_{j=1}^{\infty}\lambda_{j}v_{j}(x)v_{j}(y),$

where $|\lambda_{1}|\geq|\lambda_{2}|\geq\cdots$ and the functions
$v_{1},v_{2},\cdots$ are orthonormal in $L^{2}([0,1])$. Let

(14) $g_{1}(x,y)=\lambda_{1}v_{1}(x)v_{1}(y),\qquad
g_{2}(x,y)=\sum_{j=2}^{\infty}\lambda_{j}v_{j}(x)v_{j}(y).$

Our goal is to show that $g_{2}=0$ and that $v_{1}(x)=\pm 1$, taking each
value on a set of measure 1/2. We do this in stages:

  * •

In Section 3, we prove a priori entropy bounds on any graphon having the given
values of $(e,t)$. We show that the symmetric bipodal graphon comes within
$O(\delta^{2})$ of saturating those bounds. This implies that any entropy-
maximizing graphon must be $L^{2}$-close to a symmetric bipodal graphon.
Specifically, $g_{2}$ must be $L^{2}$-small and $v_{1}$ must be $L^{2}$-close
to the desired step function.

  * •

In Section 4 we show that $g_{2}$ is pointwise small and that $v_{1}(x)^{2}$
is pointwise close to 1. More precisely, the $L^{\infty}$ norms of $g_{2}$ and
$v_{1}^{2}-1$ must go to zero as $\delta\to 0$.

  * •

In Section 5 we expand the entropy $S(g)$ using a convergent Taylor series for
$H(u)$ around $u=\frac{1}{2}$. Using the fact that $g_{2}$ is pointwise small,
we express the difference between $S(g)$ and the entropy of a symmetric
bipodal graphon as a quadratic function of the $L^{2}$ norm of $g_{2}$, the
$L^{2}$-norm of $v_{1}(x)^{2}-1$ and the integral $\int_{0}^{1}v_{1}(x)dx$,
plus higher-order corrections. We show that the quadratic function is
negative-definite, implying that $g_{2}$ must be zero, $v_{1}(x)^{2}$ must be
1, and $\int_{0}^{1}v_{1}(x)dx$ must be zero. In other words, our graphon must
be symmetric bipodal.

  * •

In Section 6 we turn our attention to Theorem 3. We construct a family of
tripodal graphons and we express the entropy of both this tripodal graphon and
the symmetric bipodal graphon as power series in $\sigma$. When $e<e_{0}$, we
can choose the parameters of the tripodal graphon such that the tripodal
graphon has more entropy at order $\sigma^{2}$ than the symmetric bipodal
graphon. This does not prove that the optimal graphon is tripodal! However, it
does proves that, for $\sigma$ sufficiently small, the symmetric bipodal
graphon is not optimal.

We use big-O and little-o notation throughout. When we say that a certain
quantity is $O(\delta^{n})$, we mean that there exist positive numbers $C$ and
$\delta_{0}$ (which may depend on $\sigma$) such that our quantity is bounded
by $C|\delta|^{n}$ whenever $|\delta|<\delta_{0}$. When we say that a quantity
is $o(\delta^{n})$, we mean that there exists a constant $\delta_{0}$ and
function $f(\delta)$, going to zero as $\delta\to 0$, such that the quantity
is bounded by $f(\delta)|\delta^{n}|$ when $|\delta|<\delta_{0}$.

##  3\. A priori estimates

We begin with an upper bound on entropy.

######  Theorem 8.

If $g$ is a graphon with edge density $e=\frac{1}{2}+\delta$ and triangle
density $e^{3}-\sigma^{3}$, with $\sigma>0$, then

(15) $S(g)\leq H\left(\frac{1}{2}+\sqrt{\delta^{2}+\sigma^{2}}\right).$

###### Proof.

Let $g$ be our arbitrary graphon, which we expand as in equations (13) and
(14). For $i=1,2$, let $d_{i}(x)=\int_{0}^{1}g_{i}(x,y)dy$. A direct
computation of the triangle density gives

(16) $\displaystyle\tau(g)$ $\displaystyle=$ $\displaystyle\iiint
g(x,y)g(y,z)g(z,x)\,dx\,dy\,dz$ (17) $\displaystyle=$ $\displaystyle
e^{3}+\sum_{j=1}^{\infty}\lambda_{j}^{3}+3e\int_{0}^{1}(d_{1}(x)^{2}+d_{2}(x)^{2})dx$
(18) $\displaystyle\sum_{j}\lambda_{j}^{3}$ $\displaystyle=$
$\displaystyle-(\sigma^{3}+3e\int_{0}^{1}(d_{1}(x)^{2}+d_{2}(x)^{2})dx).$

The squared $L^{2}$ norm of $g_{1}+g_{2}$ is

$\sum_{j}\lambda_{j}^{2}\geq\left|\sum_{j}\lambda_{j}^{3}\right|^{2/3}\geq\sigma^{2},$

with equality if and only if $\lambda_{1}=-\sigma$,
$\lambda_{2}=\lambda_{3}=\cdots=0$, and $d_{1}(x)=0$ for all $x$.

Next we maximize the entropy for a fixed $\|g_{1}+g_{2}\|_{2}^{2}$. We use an
absolutely convergent power series for

(19) $H(u)=-(u\ln(u)+(1-u)\ln(1-u)),$

namely

(20)
$H(u)=\sum_{n=0}^{\infty}\frac{H^{(n)}(\frac{1}{2})}{n!}\left(u-\frac{1}{2}\right)^{n}.$

The terms with $n$ odd are identically zero, while the terms with $n$ nonzero
and even are negative. As a result,

(21)
$S(g)=H\left(\frac{1}{2}\right)+\sum_{k=1}^{\infty}\frac{H^{(2k)}(\frac{1}{2})}{(2k)!}\mu_{2k},$

where

(22) $\mu_{2k}=\iint\left(\delta+g_{1}(x,y)+g_{2}(x,y)\right)^{2k}\,dx\,dy.$

The second moment depends only on the size of $g_{1}$ and $g_{2}$. Since
$\iint g_{1}(x,y)+g_{2}(x,y)\,dx\,dy=0$, there are no cross terms between
$\delta$ and $g_{1}+g_{2}$, leaving us with

$\mu_{2}=\delta^{2}+\|g_{1}+g_{2}\|_{2}^{2}=\delta^{2}+\sum_{j=1}^{\infty}\lambda_{j}^{2}.$

Maximizing $S(g)$ is equivalent to minimizing all of the higher moments
$\mu_{2k}$ with $k>1$. This happens when $(\delta+g_{1}(x,y)+g_{2}(x,y))^{2}$
is constant, equaling $\mu_{2}$. In that case, $g$ is everywhere equal to
$\frac{1}{2}\pm\sqrt{\mu_{2}}$ and

(23)
$S(g)=H\left(\frac{1}{2}+\sqrt{\delta^{2}+\|g_{1}+g_{2}\|_{2}^{2}}\right).$

Since $\|g_{1}+g_{2}\|_{2}^{2}\geq\sigma^{2}$, and since $H(u)$ is a
decreasing function of $u$ for $u>1/2$, we conclude that

$S(g)\leq H\left(\frac{1}{2}+\sqrt{\delta^{2}+\sigma^{2}}\right).$

∎

######  Corollary 9.

If $g$ is an entropy-maximizing graphon, then $\int_{0}^{1}v_{1}(x)\,dx$ is
$O(\delta)$, while $\|g_{2}\|_{2}^{2}$, $\int_{0}^{1}d_{2}(x)^{2}\,dx$ and
$\int_{0}^{1}(v_{1}(x)^{2}-1)^{2}\,dx$ are $O(\delta^{2})$.

###### Proof.

The symmetric bipodal graphon has entropy

$\displaystyle\frac{1}{2}\left[H(e+\sigma)+H(e-\sigma)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left[H\left(\frac{1}{2}+\delta+\sigma\right)+H\left(\frac{1}{2}+\delta-\sigma\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left[H\left(\frac{1}{2}+\sigma+\delta\right)+H\left(\frac{1}{2}+\sigma-\delta\right)\right]$
$\displaystyle=$ $\displaystyle
H\left(\frac{1}{2}+\sigma\right)+\frac{\delta^{2}}{2}H^{\prime\prime}\left(\frac{1}{2}+\sigma\right)+O(\delta^{4}).$

By contrast, the upper bound (15) is

$H\left(\frac{1}{2}+\sigma\right)+\frac{\delta^{2}}{2\sigma}H^{\prime}\left(\frac{1}{2}+\sigma\right)+O(\delta^{4}).$

Since the symmetric bipodal graphon comes within $O(\delta^{2})$ of achieving
the upper bound (15), the entropy-maximizing graphon must also come within
$O(\delta^{2})$ of that bound. In particular, $\|g_{1}+g_{2}\|_{2}^{2}$ must
be within $O(\delta^{2})$ of $\sigma^{2}$ and the fourth moment $\mu_{4}$ can
be no more than $O(\delta^{2})$ greater than
$(\delta^{2}+\sigma^{2})^{2}=\sigma^{4}+O(\delta^{2})$.

Now

$\|g_{1}+g_{2}\|_{2}^{2}=\sum_{j}\lambda_{j}^{2}\geq\left|\sum_{j}\lambda_{j}^{3}\right|^{2/3}=\left(\sigma^{3}+3e\int_{0}^{1}d_{1}(x)^{2}+d_{2}(x)^{2}dx\right)^{2/3}.$

This can only be within $O(\delta^{2})$ of $\sigma^{2}$ if
$\int_{0}^{1}d_{1}(x)^{2}dx$ and $\int_{0}^{1}d_{2}(x)^{2}dx$ are both
$O(\delta^{2})$. However,
$\int_{0}^{1}d_{1}(x)^{2}dx=\lambda_{1}^{2}\left(\int_{0}^{1}v_{1}(x)dx\right)^{2}$
and $\lambda_{1}\approx-\sigma$, so $\int_{0}^{1}v_{1}(x)dx$ must be
$O(\delta)$.

We now turn to $\|g_{2}\|_{2}^{2}=\sum_{j=2}^{\infty}\lambda_{j}^{2}$. Since

$\lambda_{1}^{3}=-(\sigma^{3}+3e\int_{0}^{1}d_{1}(x)^{2}+d_{2}(x)^{2}\,dx-\sum_{j=2}^{\infty}\lambda_{j}^{3}),$

and since $|\sum_{j=2}^{\infty}\lambda_{j}^{3}|\leq\|g_{2}\|_{2}^{3}$,
$\lambda_{1}\leq-\sigma+O(\|g_{2}\|_{2}^{3})$. But then

$\sum_{j=1}^{\infty}\lambda_{j}^{2}\geq\sigma^{2}+\|g_{2}\|_{2}^{2}+O(\|g_{2}\|_{2}^{3}).$

Since this must be within $O(\delta^{2})$ of $\sigma^{2}$, we must have
$\|g_{2}\|_{2}^{2}=O(\delta^{2})$.

Finally, we consider the fourth moment $\mu_{4}$. The leading contribution is

$\lambda_{1}^{4}\left(\int_{0}^{1}v_{1}(x)^{4}dx\right)^{2}=\lambda_{1}^{4}\left(1+\int_{0}^{1}(v_{1}(x)^{2}-1)^{2}dx\right)^{2}.$

For this to be within $O(\delta^{2})$ of $\sigma^{4}$,
$\int_{0}^{1}(v_{1}(x)^{2}-1)^{2}dx$ must be $O(\delta^{2})$. ∎

##  4\. Pointwise estimates

The upshot of Section 3 is that $g$ must be $L^{2}$-close to a symmetric
bipodal graphon, with $\lambda_{1}$ being close to $-\sigma$, with the sum of
the other $\lambda_{j}^{2}$ being small, and with $v_{1}(x)$ being close to 1
on a set of measure approximately 1/2 and close to $-1$ on a set of measure
approximately 1/2. In this section we upgrade those $L^{2}$ estimates into
pointwise estimates:

######  Proposition 10.

If $g$ is an entropy-maximizing graphon, then $\|g_{2}(x,y)\|_{\infty}$ is
$o(1)$.

######  Proposition 11.

If $g$ is an entropy-maximizing graphon, then $\|v_{1}(x)^{2}-1\|_{\infty}$ is
$o(1)$.

We prove Propositions 10 and 11 with a series of lemmas. We begin by showing
that $g_{1}$ and $g_{2}$ are pointwise bounded.

######  Lemma 12.

Let $g$ be an entropy-maximizing graphon. For all $x,y\in[0,1]$, the following
bounds apply:

$|v_{1}(x)|\leq|\lambda_{1}|^{-1},\qquad|g_{1}(x,y)|\leq|\lambda_{1}|^{-1},\qquad|g_{2}(x,y)|\leq
1+|\lambda_{1}|^{-1}.$

###### Proof.

We use the fact that

$0\leq e+g_{1}(x,y)+g_{2}(x,y)\leq 1$

for all $(x,y)$. The only way for $g_{2}(x,y)$ be be big and positive (resp.
negative) is for $g_{1}(x,y)$ to be big and negative (resp. positive). This
can only occur if $|v_{1}(x)|$ is large for some $x$.

Suppose that there is a point $x_{0}$ with $v_{1}(x_{0})>1/|\lambda_{1}|$. Let
$I_{+}$ be the set of $x$ for which
$v_{1}(x)>0.9|\lambda_{1}v_{1}(x_{0})|^{-1}$ and let $I_{-}$ be the set of $x$
for which $v_{1}(x)<-0.9|\lambda_{1}v_{1}(x_{0})|^{-1}$. We already know that
the set of points with $v_{1}(x)$ close to $\pm 1$ each have measure close to
1/2, since $\int_{0}^{1}(v_{1}(x)^{2}-1)dx=O(\delta^{2})$ and
$\int_{0}^{1}v_{1}(x)dx=O(\delta)$, so $I_{+}$ and $I_{-}$ also each have
measure close to 1/2.

Since $\lambda_{1}$ is negative, $g_{1}(x,y)$ is less than or equal to -0.9
for all $y\in I_{+}$ and is greater than or equal to 0.9 for all $y\in I_{-}$.
Since $e$ is close to 1/2, $e+g_{1}(x_{0},y)$ is close to or less than -1.4
when $y\in I_{+}$ (and in particular is less than -1.3) and is close to or
greater than 1.4 (and in particular is greater than 1.3) when $y\in I_{-}$. As
a result, $g_{1}(x_{0},y)$ has magnitude at least 0.3, and sign opposite to
that of $g_{2}(x_{0},y)$, for all $y\in I_{+}\cup II_{-}$. This means that
$g_{1}(x_{0},y)g_{2}(x_{0},y)<-0.27$ for all $y\in I_{+}\cup I_{-}$.

When $y\not\in I_{-}\cup I_{+}$, $|g_{2}(x_{0},y)|\leq 0.9<1$, so
$|g_{2}(x_{0},y)|<2$, so $g_{1}(x_{0},y)g_{2}(x_{0},y)<2$. Since $I_{+}\cup
I_{-}$ is a set of measure $m\approx 1$,

$\int_{0}^{1}g_{1}(x_{0},y)g_{2}(x_{0},y)dy\leq-0.27m+2(1-m)<0.$

However,

$\int_{0}^{1}g_{1}(x_{0},y)g_{2}(x_{0},y)\,dy=\sum_{j=2}^{\infty}\lambda_{1}\lambda_{j}v_{1}(x_{0})v_{j}(x_{0})\int_{0}^{1}v_{1}(y)v_{j}(y)\,dy=0,$

by the orthogonality of the functions $v_{j}(y)$ in $L^{2}([0,1])$. This is a
contradiction, so $x_{0}$ does not exist.

The same argument, with signs reversed, rules out the possibility that
$v_{1}(x)$ is ever less than $-1/|\lambda_{1}|$. Since $|v_{1}(x)|$ is bounded
by $|\lambda_{1}|^{-1}$, $|g_{1}(x,y)|=|\lambda_{1}v_{1}(x)v_{1}(y)|$ is also
bounded by $|\lambda_{1}|^{-1}$. Finally, we have that

$-e-g_{1}(x,y)\leq g_{2}(x,y)\leq 1-e-g_{1}(x,y).$

Since $e$ and $1-e$ are both less than 1, this implies that
$|g_{2}(x,y)|<|g_{1}(x,y)|+1\leq|\lambda_{1}|^{-1}+1$. ∎

Lemma 12 is stated in terms of $\lambda_{1}$, which of course depends on the
graphon $g$. However, $\lambda_{1}=-\sigma+o(1)$, so for small $\delta$ we can
replace our bounds involving $\lambda_{1}$ with uniform bounds in terms of
$\sigma$, at the cost of replacing the constant 1 with a slightly smaller
number. For instance,

$|v_{1}(x)|<1.1\sigma^{-1},\qquad|g_{1}(x,y)|<1.1\sigma^{-1},\qquad|g_{2}(x,y)|\leq
1+1.1\sigma^{-1}$

whenever $\delta$ is sufficiently small. In practice, we do not need the
specific bounds of Lemma 12. All we really need is for $v_{1}(x)$,
$g_{1}(x,y)$ and $g_{2}(x,y)$ to be bounded.

We next turn to showing that $g_{2}(x,y)$ is not only bounded but small. Since
$\|g_{2}\|_{2}^{2}$ is $O(\delta^{2})$, the set of points where $|g_{2}(x,y)|$
is not small (say, smaller than a fixed $\epsilon$) has measure
$O(\delta^{2})$. We now establish a similar result for vertical strips.

######  Lemma 13.

Let $g$ be an entropy-maximizing graphon. For any $\epsilon>0$ and any
$x\in[0,1]$, the set of $y$-values for which $|g_{2}(x,y)|>\epsilon$ has
measure $o(1)$.

###### Proof.

Let $G(x,y)=\int_{0}^{1}g(x,z)g(z,y)\,dz$. As as operator, this is the square
of $g$. Expanding that square using $g(x,y)=e+g_{1}(x,y)+g_{2}(x,y)$, we
$G_{1}$ be the portion of $G$ that comes from $e+g_{1}$, and let $G_{2}$ be
the additional contributions that involve $g_{2}$.

(24) $\displaystyle G_{1}(x,y)$ $\displaystyle=$
$\displaystyle\int_{0}^{1}(e+g_{1}(x,z))(e+g_{1}(y,z))dz$ (25)
$\displaystyle=$ $\displaystyle
e^{2}+\lambda_{1}^{2}v_{1}(x)v_{1}(y)+e\left(\int_{0}^{1}v_{1}(z)dz\right)(v_{1}(x)+v_{1}(y)).$
(26) $\displaystyle=$ $\displaystyle e^{2}+\lambda_{1}g_{1}(x,y)+O(\delta),$
(27) $\displaystyle=$
$\displaystyle\lambda_{1}(e+g_{1}(x,y))+e^{2}-\lambda_{1}e+O(\delta),$

since $\int_{0}^{1}v_{1}(z)\,dz=O(\delta)$ and $v_{1}(x)$ and $v_{1}(y)$ are
bounded.

We next turn to $G_{2}$. Since $\int_{0}^{1}v_{1}(z)g_{2}(y,z)\,dz=0$, there
is no contribution from the product of $g_{1}$ and $g_{2}$. We only have
$eg_{2}$ and $g_{2}^{2}$ terms, specifically

$G_{2}(x,y)=e(d_{2}(x)+d_{2}(y))+\int_{0}^{1}g_{2}(x,z)g_{2}(y,z)dz.$

The function $d_{2}(y)$ has small $L^{2}$-norm, and so must be $o(1)$ except
on a set of small measure. (Since $x$ is fixed, we cannot similarly argue that
$d_{2}(x)$ is small.) Finally, since $g_{2}$ is bounded and has small $L^{2}$
norm, the integral $\int_{0}^{1}g_{2}(x,z)g_{2}(y,z)dz$ for fixed $x$ is small
except for a set of $y$’s that has small measure. The result is an estimate

$G_{2}(x,y)=ed_{2}(x)+o(1)$

that is true for $y$ in the complement of a set of measure $o(1)$, where that
small set may depend on $x$.

Combining this with our estimate of $G_{1}$, we have

(28) $G(x,y)=(e^{2}-\lambda_{1}e)+\lambda_{1}g_{1}(x,y)+ed_{2}(x)+o(1)$

for all but a small set of $y$’s.

Since $g$ is assumed to maximize entropy subject to constraints on
$\varepsilon(g)$ and $\tau(g)$, the functional derivative of $S(g)$ must be a
linear combination of the functional derivatives of $\varepsilon(g)$ and
$\tau(g)$. This yields the pointwise equations

(29) $H^{\prime}(g(x,y))=\Lambda_{e}+\Lambda_{t}G(x,y),$

where $\Lambda_{e}$ and $\Lambda_{t}$ are Lagrange multipliers.

For all but a small set of $y$’s, equation (29) takes the form

(30) $H^{\prime}(e+g_{1}(x,y)+g_{2}(x,y))=\mu+\nu(e+g_{1}(x,y))+\rho
d_{2}(x)+o(1),$

where

$\mu=\Lambda_{e}+\Lambda_{t}(e^{2}-\lambda_{1}e),\qquad\nu=\lambda_{1}\Lambda_{t},\qquad\rho=e\Lambda_{t}.$

For most values of $(x,y)$, $e+g_{1}(x,y)$ is close to $e\pm\sigma$ and
$g_{2}(x,y)$ and $d_{2}(x)$ are small. This fixes $\Lambda_{e}$ and
$\Lambda_{t}$, and therefore $\mu$, $\nu$, and $\rho$, to within a small
error. Since $e=\frac{1}{2}+\delta$ and
$H^{\prime}(\frac{1}{2}-\sigma)=-H^{\prime}(\frac{1}{2}+\sigma)$, we obtain

(31) $\displaystyle H^{\prime}\left(\frac{1}{2}+\sigma\right)$
$\displaystyle=$
$\displaystyle\Lambda_{e}+\Lambda_{t}\left(\frac{1}{4}-\sigma^{2}\right)+o(1)$
(33) $\displaystyle-H^{\prime}\left(\frac{1}{2}+\sigma\right)$
$\displaystyle=$
$\displaystyle\Lambda_{e}+\Lambda_{t}\left(\frac{1}{4}+\sigma^{2}\right)+o(1),$

with solution

(34)
$\displaystyle\Lambda_{e}\approx-\frac{1}{4\sigma^{2}}H^{\prime}\left(\frac{1}{2}+\sigma\right),$
$\displaystyle\displaystyle{\Lambda_{t}\approx\frac{1}{\sigma^{2}}H^{\prime}\left(\frac{1}{2}+\sigma\right),}$
(36)
$\displaystyle\mu\approx-\frac{1}{2\sigma}H^{\prime}\left(\frac{1}{2}+\sigma\right),$
$\displaystyle\displaystyle{\nu\approx\frac{1}{\sigma}H^{\prime}\left(\frac{1}{2}+\sigma\right),}$
$\displaystyle\rho\approx-\frac{1}{2\sigma^{2}}H^{\prime}\left(\frac{1}{2}+\sigma\right),$

where all of the approximations are “$+o(1)$” as $\delta\to 0$.

From the explicit form of $H^{\prime}(g)=\ln(1-g)-\ln(g)$, we see that there
are only three roots to the equation $H^{\prime}(g)=\mu+\nu g$, which are
located near $g=e\pm\sigma$ and $g=e$. Our immediate goal is to show that
$v_{1}(x)$ only takes values close to 0 and $\pm 1$, which implies that
$g_{1}(x,y)$ is only close to $e$ and $e\pm\sigma$.

Since $\int v_{1}(x)dx$ and $\int(v_{1}(x)^{2}-1)^{2}dx$ are small, the
function $v_{1}$ must be close to 1 on an interval (call it $I_{1}$) of
measure close to 1/2, must be close to $-1$ on an interval $I_{2}$ of measure
close to $1/2$, may be close to 0 on a third interval $I_{3}$ of small
measure, and may take on other values on a fourth interval $I_{4}$ of small
measure.

Let $x$ be an arbitrary point in $[0,1]$, and let $y_{1}$ and $y_{2}$ be
generic points in $I_{1}$ and $I_{2}$. Equation (30) then determines
$a=g_{2}(x,y_{1})$ and $b=g_{2}(x,y_{2})$ in terms of $d_{2}(x)$. What’s more,
$g_{2}$ takes values close to $a$ on all of $\\{x\\}\times I_{1}$ (excepting
those values of $y$ where equation (30) doesn’t apply), and takes values close
to $b$ on all of $\\{x\\}\times I_{2}$. We then compute

$\int_{0}^{1}g_{2}(x,y)v_{1}(y)dy\approx(a-b)/2.$

However, this integral must be zero, since $v_{1}(y)$ is orthogonal to all of
the functions $v_{i}(y)$ that make up $g_{2}(x,y)$. We conclude that $a\approx
b$.

If $b\approx a$, then $d_{2}(x)=\int_{0}^{1}g_{2}(x,y)dy$ also equals $a$ and
our equations at $(x,y_{2})$ and $(x,y_{1})$ become

(37) $\displaystyle H^{\prime}\left(\frac{1}{2}+\sigma v_{1}(x)+a\right)$
$\displaystyle\approx$ $\displaystyle\mu+\nu\left(\frac{1}{2}+\sigma
v_{1}(x)\right)+\rho a$ (38) $\displaystyle H^{\prime}\left(\frac{1}{2}-\sigma
v_{1}(x)+a\right)$ $\displaystyle\approx$
$\displaystyle\mu+\nu\left(\frac{1}{2}-\sigma v_{1}(x)\right)+\rho a,$

Adding these equations, and using the fact that $H^{\prime}(\frac{1}{2}-\sigma
v_{1}(x)+a)=-H^{\prime}(\frac{1}{2}+\sigma v_{1}-a)$, we get

(39) $H^{\prime}\left(\frac{1}{2}+\sigma
v_{1}(x)+a\right)-H^{\prime}\left(\frac{1}{2}+\sigma v_{1}(x)-a\right)\approx
2\mu+\nu+2\rho
a\approx-\frac{a}{\sigma^{2}}H^{\prime}\left(\frac{1}{2}+\sigma\right).$

By the mean value theorem, the left hand side of equation (39) is
$2aH^{\prime\prime}(u)$ for some $u$ between $\frac{1}{2}+\sigma v_{1}(x)-a$
and $\frac{1}{2}+\sigma v_{1}(x)+a$. Regardless of the value of $u$, this is a
negative multiple of $a$. However, the right hand side is a positive multiple
of $a$, since $H^{\prime}(\frac{1}{2}+\sigma)<0$. Since a negative multiple of
$a$ equals a positive multiple, $a$ must be (approximately) zero.

In particular, $g_{2}(x,y)\approx 0$ for all $y$ such that equation (30)
applies. That is, for fixed $x$, $g_{2}(x,y)$ is close to zero except on a set
of $y$’s of small measure. ∎

###### Proof of Proposition 10.

By Lemma 12, $g_{2}(x,y)$ is bounded. By Lemma 13, for each $x$, $g_{2}(x,y)$
is small for all but a small set of $y$’s. Combining these results, we see
that the degree function $d_{2}(x)$ is everywhere small, as is the integral
$\int_{0}^{1}g_{2}(x,z)g_{2}(y,z)\,dz$. That is, $G_{2}(x,y)$ is pointwise
small. But then equation (30) applies everywhere, so $g_{2}(x,y)$ is small
everywhere. ∎

###### Proof of Proposition 11.

In the notation of the proof of Lemma 13, we must show that the intervals
$I_{3}$ and $I_{4}$ are empty, implying that $v_{1}(x)$ is everywhere close to
$\pm 1$.

Since $G_{2}(x,y)$ is small for all $(x,y)$, we must have

$H^{\prime}\left(\frac{1}{2}+\sigma
v_{1}(x)\right)=\mu+\nu\left(\frac{1}{2}+\sigma v_{1}(x)\right)$

for all $y\in I_{2}$. However, the only solutions to this equation are
(approximately) $\sigma v_{1}(x)=\pm\sigma$ or 0, implying that
$v_{1}(x)\approx\pm 1$ or 0. In other words, $x\in I_{1}\cup I_{2}\cup I_{3}$
and $I_{4}$ is empty.

Showing that $I_{3}$ is empty requires a completely different argument, since
equation (29) is indeed satisfied when $x\in I_{3}$. However, equation (29)
only defines stationary points with respect to pointwise small changes in
$g(x,y)$. We also have to consider infinitesimal changes in the boundary
between $I_{1}$, $I_{2}$ and $I_{3}$.

So suppose that we increase the size of $I_{1}$ by an amount $\epsilon$ at the
expense of $I_{3}$. That is, we change the value of $v_{1}(x)$ from near 0 to
near 1 on a set of small measure $\epsilon$. To first order in $\epsilon$, the
change in entropy is $2\epsilon(H(\frac{1}{2}+\sigma)-H(\frac{1}{2}))$, since
we are changing $g(x,y)$ from near zero to near $\frac{1}{2}\pm\sigma$ on a
set of measure $2\epsilon+O(\epsilon^{2})$, and since
$H(\frac{1}{2}-\sigma)=H(\frac{1}{2}+\sigma)$. The change in edge density is
$-2\epsilon\lambda_{1}\int_{0}^{1}v_{1}(y)dy=O(\delta\epsilon)$. To leading
order, the change in the triangle density is $3\lambda_{1}^{3}\epsilon$, since
the $\lambda_{1}^{3}$ contribution to $\tau(g)$ is actually
$\lambda_{1}^{3}(\int_{0}^{1}v_{1}(x)^{2}dx)^{3}$, which changes from
$\lambda_{1}^{3}$ to
$\lambda_{1}^{3}(1+\epsilon)^{3}\approx\lambda_{1}^{3}(1+3\epsilon)$.

The variational equations $dS=\Lambda_{e}d\varepsilon+\Lambda_{t}d\tau/3$ then
become

(40)
$2\left[H\left(\frac{1}{2}+\sigma\right)-H\left(\frac{1}{2}\right)\right]=\lambda_{1}^{3}\Lambda_{t}=\sigma
H^{\prime}\left(\frac{1}{2}+\sigma\right).$

We expand both sides of equation (40) as power series in $\sigma$. The left-
hand side is

$2\sum_{k=1}^{\infty}\frac{H^{(2k)}(1/2)}{(2k)!}\sigma^{2k}.$

The right-hand side is

$\sum_{k=1}^{\infty}\frac{H^{(2k)}(1/2)}{(2k-1)!}\sigma^{2k}.$

The coefficients agree when $k=1$, but are strictly greater for the right-hand
side when $k>1$. Since all terms are strictly negative (insofar as all even
derivatives of $H$ are negative-definite), the right-hand side strictly
smaller than the left-hand side.

Since varying the size of $I_{3}$ does not satisfy the variational equation
(40), we cannot be in the interior of our parameter space. Rather, the measure
of $I_{3}$ must be zero. ∎

##  5\. Cost-benefit analysis

In Sections 3 and 4 we showed that $g_{2}(x,y)$ is pointwise small, as is
$v_{1}(x)^{2}-1$. In this section we show that they are zero, completing the
proof of Theorem 1. The key measures of how far they are from being zero are

(41)
$\alpha^{2}=\sum_{i=2}^{\infty}\lambda_{i}^{2},\qquad\beta^{2}=\int_{0}^{1}(v_{1}(x)^{2}-1)^{2}\,dx,\quad\hbox{
and }\quad\gamma=\int_{0}^{1}v_{1}(x)\,dx.$

By Corollary 9, $\alpha$, $\beta$ and $\gamma$ are all $O(\delta)$. The
symmetric bipodal graphon is characterized by $\alpha=\beta=\gamma=0$.

We use the expansion (21) and compare the moments $\mu_{2k}$ to those of the
symmetric bipodal graphon. We will estimate costs (terms that increase
$\mu_{2k}$) and benefits (terms that decrease $\mu_{2k}$). We will show that
having $\alpha$ or $\beta$ or $\gamma$ nonzero comes with costs that go as
$\alpha^{2}$, $\beta^{2}$, and $\gamma^{2}$, while the benefits are
$o(\alpha^{2}+\beta^{2}+\gamma^{2})$. When $\delta$ is sufficiently small, the
costs exceed the benefits, so the symmetric bipodal graphon has more entropy
than any graphon that isn’t symmetric bipodal.

We first establish the costs. Our triangle density is

$e^{3}-\sigma^{3}=t=e^{3}+3e\int_{0}^{1}\left(d_{1}(x)^{2}+d_{2}(x)^{2}\right)\,dx+\lambda_{1}^{3}+\sum_{j=2}^{\infty}\lambda_{j}^{3}.$

Now

$\int_{0}^{1}d_{1}^{2}(x)dx=\lambda_{1}^{2}\left(\int_{0}^{1}v_{1}(x)\,dx\right)^{2}=\lambda_{1}^{2}\gamma^{2},$

while $\int_{0}^{1}d_{2}(x)^{2}\,dx>0$ and

$\left|\sum_{j=2}^{\infty}\lambda_{j}^{3}\right|\leq\left(\sum_{j=2}^{\infty}\lambda_{j}^{2}\right)^{3/2}=\alpha^{3}.$

This implies that

$\lambda_{1}^{3}\leq-\sigma^{3}-3e\sigma^{2}\gamma^{2}+O(\alpha^{3}),$

so

$\lambda_{1}^{2}\geq\sigma^{2}+2e\sigma\gamma^{2}+O((\alpha,\beta,\gamma)^{3})$

and

$\mu_{2}=\lambda_{1}^{2}+\alpha^{2}\geq\sigma^{2}+\alpha^{2}+2e\sigma\gamma^{2}+o(\alpha^{2}+\beta^{2}+\gamma^{2}).$

That is, there are $\alpha^{2}$ and $\gamma^{2}$ costs associated with
$\mu_{2}$.

We next look at $\mu_{4}$. This contains a term

$\iint
g_{1}(x,y)^{4}\,dx\,dy=\lambda_{1}^{4}\left(\int_{0}^{1}v_{1}(x)^{4}dx\right)^{2}=\lambda_{1}^{4}(1+\beta^{2})^{2}\geq\sigma^{4}(1+2\beta^{2}).$

That is, there is a cost proportional to $\beta^{2}$. Having established costs
proportional to $\alpha^{2}$, $\beta^{2}$, and $\gamma^{2}$, we just have to
show that the benefits of having $\alpha,\beta,\gamma$ nonzero are smaller.

We are looking at even moments

$\mu_{2k}=\iint(\delta+g_{1}+g_{2})^{2k}\,dx\,dy.$

We expand out the power, getting terms proportional to a power of $\delta$
times a power of $g_{1}$ times a power of $g_{2}$. We make repeated use of the
following trick:

$u^{2m}=1+u^{2m}-1=1+(u^{2}-1)p_{m}(u),$

where

$p_{m}(u)=1+u^{2}+u^{4}+\cdots+u^{2m-1}.$

This means that

(42) $\displaystyle g_{1}(x,y)^{2m}$ $\displaystyle=$
$\displaystyle\lambda_{1}^{2m}\left[1+\left(v_{1}(x)^{2}-1\right)p_{m}(v_{1}(x))\right]\left[1+\left(v_{1}(y)^{2}-1\right)p_{m}(v_{1}(y))\right]$
(44) $\displaystyle=$
$\displaystyle\lambda_{1}^{2m}\Big{[}1+\left(v_{1}(x)^{2}-1\right)p_{m}(v_{1}(x))+\left(v_{1}(y)^{2}-1\right)p_{m}(v_{1}(y))$
$\displaystyle\qquad+\left(v_{1}(x)^{2}-1\right)\left(v_{1}(y)^{2}-1\right)p_{m}(v_{1}(x))p_{m}(v_{1}(y))\Big{]}$

and

(47) $\displaystyle g_{1}(x,y)^{2m+1}$ $\displaystyle=$
$\displaystyle\lambda_{1}^{2m+1}\Big{[}v_{1}(y)\left(v_{1}(x)+\left(v_{1}(x)^{3}-v_{1}(x)\right)p_{m}(v_{1}(x))\right)$
$\displaystyle\qquad+v_{1}(x)\left(v_{1}(y)^{3}-v_{1}(y)\right)p_{m}(v_{1}(y))$
$\displaystyle\qquad+\left(v_{1}(x)^{2}-1\right)\left(v_{1}(y)^{2}-1\right)v_{1}(x)v_{1}(y)p_{m}(v_{1}(x))p_{m}(v_{1}(y))\Big{]}.$

We divide the terms obtained by expanding $\iint(\delta+g_{1}+g_{2})^{2k}$
into several classes.

  1. (1)

Terms with three or more powers of $g_{2}$. Since $g_{2}$ is pointwise small
and $g_{1}$ is bounded, these are bounded by small multiples of $\iint
g_{2}^{2}=\alpha^{2}$. In other words, they are $o(\alpha^{2})$.

  2. (2)

Terms with two powers of $g_{2}$, an even number of powers of $\delta$ and an
even number of powers of $g_{1}$. These are manifestly positive and represent
costs, not benefits. Aside from the
$\iint\delta^{0}g_{1}^{0}g_{2}^{2}=\alpha^{2}$ contribution to $\mu_{2}$ that
we already considered, we do not keep track of these.

  3. (3)

Terms with two powers of $g_{2}$, an odd number of powers of $\delta$ and an
odd number of powers of $g_{1}$. The integrand is a positive power of $\delta$
times a bounded quantity times $g_{2}(x,y)^{2}$, making the integral
$O(\delta\alpha^{2})$.

  4. (4)

Terms with one power of $g_{2}$, an odd power of $\delta$ and an even power of
$g_{1}$. We expand these using equation (42) and consider each piece
separately. First, we compute

$\iint g_{2}(x,y)dx\,dy=-\iint
g_{1}(x,y)dx\,dy=-\lambda_{1}\left(\int_{0}^{1}v_{1}(x)dx\right)^{2}=-\lambda_{1}\gamma^{2}.$

Next, the $L^{2}$ norm of $v_{1}(x)^{2}-1$ is $\beta$ and the $L^{2}$ norm of
$g_{2}$ is $\alpha$, so

$\iint(v_{1}(x)^{2}-1)p_{m}(v_{1}(x))g_{2}\,dx\,dy=O(\alpha\beta).$

The $(v_{1}(y)^{2}-1)$ piece is similar, while the
$(v_{1}(x)^{2}-1)(v_{1}(y)^{2}-1)$ piece is $O(\alpha\beta^{2})$. Thus $\iint
g_{1}^{odd}\,g_{2}\,dx\,dy=O(\alpha\beta)+O(\gamma^{2})$, so
$\iint\delta^{odd}\,g_{1}^{odd}\,g_{2}\,dx\,dy=O(\delta\alpha\beta)+O(\delta\gamma^{2})=o(\alpha^{2}+\beta^{2}+\gamma^{2})$.

  5. (5)

Terms with one power of $g_{2}$, an even power of $\delta$ and an odd power of
$g_{1}$. We expand these using equation (47), noting that the first line in
(47) has a single factor of $v_{1}(y)$ and the second line has a single factor
of $v_{1}(x)$. However,

$\int_{0}^{1}v_{1}(y)g_{2}(x,y)\,dy=\int_{0}^{1}v_{1}(x)g_{2}(x,y)\,dx=0,$

where $x$ is arbitrary in the first integral and $y$ is arbitrary in the
second. Thus the first two lines contribute nothing and $\iint
g_{1}(x,y)^{2m+1}g_{2}(x,y)\,dx\,dy$ is equal to

$\lambda_{1}^{2m+1}\iint\Big{(}v_{1}(x)^{2}-1\Big{)}\Big{(}v_{1}(y)^{2}-1\Big{)}\Big{(}v_{1}(x)v_{1}(y)p_{m}(v_{1}(x))p_{m}(v_{1}(y)\Big{)}g_{2}(x,y)\,dx\,dy.$

The factor $\Big{(}v_{1}(x)^{2}-1\Big{)}\Big{(}v_{1}(y)^{2}-1\Big{)}$ has
$L^{2}$ norm $\beta^{2}$, the factor $g_{2}(x,y)$ has $L^{2}$ norm $\alpha$,
and the factor $v_{1}(x)v_{1}(y)p_{m}(v_{1}(x))v_{1}(y)p_{m}(v_{1}(y))$ is
bounded, so the integral is
$O(\alpha\beta^{2})=o(\alpha^{2}+\beta^{2}+\gamma^{2})$.

  6. (6)

Terms with no powers of $g_{2}$, an even number of powers of $\delta$ and an
even number of powers of $g_{1}$. These are all positive and are at least as
big as the corresponding terms for the symmetric bipodal graphon. We have
already taken into account the costs associated with $\mu_{2}$ and $\mu_{4}$.
There are additional costs associated with higher moments, but they are not
needed for this proof.

  7. (7)

Finally, there are terms with no powers of $g_{2}$, an odd number of powers of
$\delta$ and an odd number of powers of $g_{1}$. Note that

$\iint g_{1}(x,y)^{2m+1}\,dx\,dy=\lambda_{1}^{2m+1}\nu_{2m+1}^{2},$

where

$\displaystyle\nu_{2m+1}$ $\displaystyle=$
$\displaystyle\int_{0}^{1}v_{1}(x)^{2m+1}dx$ $\displaystyle=$
$\displaystyle\int_{0}^{1}v_{1}(x)\,dx+\int_{0}^{1}\left(v_{1}(x)^{2}-1\right)v_{1}(x)p_{m}(v_{1}(x))\,dx$
$\displaystyle=$ $\displaystyle\gamma+O(\beta),$

since $v_{1}(x)^{2}-1$ has $L^{2}$-norm $\beta$ and $v_{1}(x)p_{m}(v_{1}(x))$
is bounded. Squaring $\nu_{2m+1}$ and multiplying by an odd power of $\delta$
gives $O(\delta\gamma^{2})+O(\delta\beta^{2})+O(\delta\beta\gamma)$, which is
$o(\alpha^{2}+\beta^{2}+\gamma^{2})$.

Putting everything together, we have identified costs proportional to
$\alpha^{2}$, $\beta^{2}$ and $\gamma^{2}$. Other costs only add to that
total, so the total cost is at least a constant times
$\alpha^{2}+\beta^{2}+\gamma^{2}$. All of the potential benefits are smaller,
either involving three or more powers of $\alpha$, $\beta$ and $\gamma$, or
$\delta$ times a quadratic function of $\alpha$, $\beta$ and $\gamma$, or the
sup norm of $g_{2}$ times $\alpha^{2}$. When $\delta$ is sufficiently small,
the costs outweigh the benefits, so the optimal graphon is symmetric bipodal.

##  6\. The extent of the symmetric bipodal phase

We have proven that the entropy-maximizing graphon is unique and symmetric
bipodal on a region containing the interval $e=1/2$, $0<t<1/8$. It is natural
to ask how far this symmetric bipodal phase extends. There is considerable
evidence that this phase contains much of the region $e\leq 1/2$, $t<e^{3}$.

  * •

The unique entropy-maximizing graphon when $e<1/2$ and $t=0$ is known to be
symmetric bipodal, with $\sigma=e$ [27]. The entropy is $\frac{1}{2}H(2e)$.

  * •

When $e<1/2$ and $t<e^{3}$, the symmetric bipodal graphon has entropy strictly
higher than any other graphon of the form
$g(x,y)=e+\lambda_{1}v_{1}(x)v_{1}(y)$. This is Proposition 14, proven below.

  * •

When $e<1/2$ and $t$ sufficiently close to but below $e^{3}$, the symmetric
bipodal graphon has entropy strictly higher than any other bipodal graphon.
This is Proposition 16, proven below.

  * •

Numerical investigations of the region $e<1/2$, $t<1/8$ [24] did not turn up
any regions where the symmetric bipodal graphon was not optimal. That is not a
proof that such regions don’t exist, of course, but it does suggest that such
regions are likely to be small.

Despite this evidence, Theorem 3 says that there is a (possibly very small)
open subset of the region $e<1/2$, $t<1/8$ on which the symmetric bipodal
graphon is not optimal. In this section we state and prove Propositions 14 and
16 and then prove Theorem 3.

######  Proposition 14.

Suppose that $e<1/2$ and that $g$ is a graphon of the form

$g(x,y)=e+\lambda_{1}v_{1}(x)v_{1}(y),$

with edge density $e$ and triangle density $t=e^{3}-\sigma^{3}<e^{3}$. Then
$S(g)$ is bounded above by $\frac{1}{2}\left(H(e+\sigma)+H(e-\sigma)\right)$,
with equality if and only if $g$ is symmetric bipodal.

###### Proof.

First note that $\int_{0}^{1}v_{1}(x)\,dx=0$, since the overall edge density
is exactly $e$. The triangle density is then $e^{3}+\lambda_{1}^{3}$, so
$\lambda_{1}=-\sigma$. Since $0\leq g(x,y)$, $v_{1}(x)$ is bounded in
magnitude by $\sqrt{e/\sigma}$ and $\lambda_{1}v_{1}(x)v_{2}(x)$ is bounded in
magnitude by $e$. This implies that the power series

$H(g(x,y))=\sum_{j=0}^{\infty}\frac{H^{(j)}(e)}{j!}(\lambda_{1}v_{1}(x)v_{1}(y))^{j}$

converges absolutely. Integrating over $x$ and $y$ then gives

$S(g)=\sum_{j=1}^{\infty}(-\sigma)^{j}\frac{H^{(j)}(e)}{j!}\left(\int_{0}^{1}v_{1}(x)^{j}\,dx\right)^{2}.$

Since $e<1/2$, all the odd derivatives of $H$ are positive at $e$, while all
the even derivatives are negative. Multiplying by $(-\sigma)^{j}$, all of the
terms with $j>0$ are negative. We maximize the entropy by minimizing
$\int_{0}^{1}v_{1}(x)^{j}\,dx$ for $j$ even and by having
$\int_{0}^{1}v_{1}(x)^{j}\,dx=0$ for $j$ odd. The second moment
$\int_{0}^{1}v_{1}(x)^{2}\,dx$ is always equal to 1. The fourth and higher
even moments are minimized when (and only when!) $v_{1}(x)^{2}$ is constant
and equal to 1. Since $\int_{0}^{1}v_{1}(x)\,dx=0$, this means that $v_{1}(x)$
is $+1$ on a set of measure 1/2 and $-1$ on a set of measure 1/2, which makes
all of the odd integrals zero, as desired. In other words, the symmetric
bipodal graphon is the unique entropy maximizer among graphons of this form. ∎

Before turning to what happens just below the line $t=e^{3}$, we establish
constraints on the form of any entropy-maximizing bipodal graphon with
$t<e^{3}$. We use the parameters $(a,b,c,d)$ of Figure 5 to describe bipodal
graphons. Without loss of generality we can assume that $a\leq b$, since
otherwise we could just swap $c$ and $1-c$ while swapping $a$ and $b$.

######  Proposition 15.

Suppose that $t=e^{3}-\sigma^{3}<e^{3}$ and that a graphon $g$ maximizes
entropy among all bipodal graphons with edge density $e$ and triangle density
$t$. (We do not assume that $g$ maximizes entropy among all graphons, just
that it is the best bipodal graphon.) Then either $a=b$ and $c=1/2$ (a
symmetric bipodal graphon) or $a<b<d$ and $c<1/2$.

###### Proof.

In this setting, the variational equations (29) become

(48) $\displaystyle H^{\prime}(a)$ $\displaystyle=$
$\displaystyle\Lambda_{e}+\Lambda_{t}(ca^{2}+(1-c)d^{2}),$ (49) $\displaystyle
H^{\prime}(b)$ $\displaystyle=$
$\displaystyle\Lambda_{e}+\Lambda_{t}(cd^{2}+(1-c)b^{2}),$ (50) $\displaystyle
H^{\prime}(d)$ $\displaystyle=$
$\displaystyle\Lambda_{e}+\Lambda_{t}(cad+(1-c)bd).$

Subtracting the second equation from the first gives

$H^{\prime}(a)-H^{\prime}(b)=\Lambda_{t}(c(a^{2}-d^{2})+(1-c)(d^{2}-b^{2})).$

If $a=b$, then the left hand side is zero and the right hand side is a nonzero
multiple of $(1-2c)(a^{2}-d^{2})$, implying that either $c=1/2$ or $a=d$. But
if $a=b=d$, then the triangle density is exactly $e^{3}$, which is a
contradiction. Thus $a=b$ implies that the graphon must by symmetric bipodal.

We now turn to the possibility that $a<b$. The left hand side is then
positive, since $H^{\prime}$ is a decreasing function. Since
$\Lambda_{t}=\frac{1}{3}\frac{\partial S}{\partial t}$ is positive, we must
have

$c(a^{2}-d^{2})+(1-c)(d^{2}-b^{2})>0.$

This either requires $d<a$, in which case $c>1/2$ (since
$a^{2}-d^{2}<b^{2}-d^{2}$) or $d>b$, in which case $c<1/2$.

Let $\lambda_{1}$ and $\lambda_{2}$ be the two nonzero eigenvalues of $g$. The
trace of $g$ is $\lambda_{1}+\lambda_{2}=ca+(1-c)b$, while the trace of $G$ is
$\lambda_{1}^{2}+\lambda_{2}^{2}=c^{2}a^{2}+(1-c)^{2}b^{2}+2c(1-c)d^{2}$. From
this we can compute

$\lambda_{1}\lambda_{2}=\frac{1}{2}((\lambda_{1}+\lambda_{2})^{2}-(\lambda_{1}^{2}+\lambda_{2}^{2}))=c(1-c)(ab-d^{2}).$

If $d$ were less than $a$ and $b$, this would be positive, meaning that both
eigenvalues would be positive. Moreover, one of the two eigenvalues is at
least $e$, so the triangle density, which is
$\lambda_{1}^{3}+\lambda_{2}^{3}$, would be greater than $e^{3}$. This rules
out the possibility that $d<a$, and we conclude that $a<b<d$ and $c<1/2$. ∎

When $e>1/2$ and $t$ is slightly less than $e^{3}$, the optimal graphon has
been proven to take this form, with $a\approx 1-e$, $b$ slightly less than
$e$, and $d$ slightly greater than $e$, and with $c$ small. The situation is
different when $e<\frac{1}{2}$.

######  Proposition 16.

Suppose that $e<1/2$ and that $g$ is a bipodal graphon with edge density $e$
and triangle density $t=e^{3}-\sigma^{3}<e^{3}$. Then, for $\sigma$
sufficiently small, $S(g)$ is bounded above by
$\frac{1}{2}\left(H(e+\sigma)+H(e-\sigma)\right)$, with equality if and only
if $g$ is symmetric bipodal.

###### Proof.

Let

$\Delta a:=a-e,\qquad\Delta b:=b-e,\qquad\Delta d:=d-e$

and let

(51) $\eta:=\frac{c}{1-c}\Delta a+\Delta
d,\qquad\alpha:=2c\eta-\frac{c}{1-c}\Delta a.$

The leading term is $\alpha$111This is not the same as the $\alpha$ in the
proof of Theorem 1. There are only so many Greek letters in the alphabet.,
while $\eta$ measures the extent to which the degree function fails to be
constant. We can then express all of our quantities in terms of $\alpha$,
$\eta$ and $c$.

(52) $\displaystyle\Delta a$ $\displaystyle=$
$\displaystyle-\frac{1-c}{c}\alpha+e(1-c)\eta,$ (54) $\displaystyle\Delta b$
$\displaystyle=$ $\displaystyle-\frac{c}{1-c}\alpha-2c\eta,$ (56)
$\displaystyle\Delta d$ $\displaystyle=$ $\displaystyle\alpha+(1-2c)\eta.$

In terms of these parameters, the triangle density works out to be

(57) $e^{3}-\sigma^{3}=\tau(g)=e^{3}+3(e-\alpha)c(1-c)\eta^{2}-\alpha^{3}.$

Since the triangle density is less than $e^{3}$, $\eta^{2}$ must be
$O(\alpha^{3})$. That is, $\eta$ is much smaller than $\alpha$.

We now compute the entropy

$S(g)=\sum_{k=0}^{\infty}\frac{H^{(k)}(e)}{k!}\mu_{k},$

where

$\mu_{k}=\iint(g(x,y)-e)^{k}\,dx\,dy=c^{2}(\Delta a)^{k}+(1-c)^{2}(\Delta
b)^{k}+2c(1-c)(\Delta d)^{k}.$

Since $e<1/2$, the odd derivatives of $H$ at $e$ are positive, while the even
derivatives are negative, so we want to minimize the even moments and maximize
the odd moments. The symmetric bipodal graphon (uniquely) minimizes the even
moments and has all the odd moments equal to zero. For an asymmetric bipodal
graphon to do as well, it must have some positive odd moments.

The moment $\mu_{k}$ is a $k$-th order homogeneous polynomial in $\alpha$ and
$\eta$ with coefficients that depend on $c$. Since $\eta=O(\alpha^{3/2})$,

$\mu_{k}=\left(2c(1-c)+(-1)^{k}\frac{(1-c)^{k}}{c^{k-2}}+(-1)^{k}\frac{c^{k}}{(1-c)^{k-2}}\right)\alpha^{k}+O(\alpha^{k+\frac{1}{2}}).$

The coefficient of $\alpha^{k}$ is zero when $k=1$, is 1 when $k=2$, is
negative when $k$ is an odd number greater than 1, and is greater than 1 when
$k$ is an even number greater than 2. In other words, all moments with $k>2$
are worse, to leading order, than the moments of the symmetric bipodal
graphon.

There is one more point we must account for. For $k$ odd,
$\left(2c(1-c)-\frac{(1-c)^{k}}{c^{k-2}}-\frac{c^{k}}{(1-c)^{k-2}}\right)$
goes to zero as $(1-2c)^{2}$ as $c\to 1/2$. We must rule out the possibility
that other contributions to $\mu_{k}$ might become greater than the
$\alpha^{k}$ term as $c$ approaches 1/2.

This requires estimates on $\eta$. From the formula for the triangle density,
we have that

$\alpha\approx\sigma+\frac{ec(1-c)\eta^{2}}{\sigma^{2}},$

and hence that

$\mu_{2}=\alpha^{2}+2c(1-c)\eta^{2}\approx\sigma^{2}+\frac{2ec(1-c)}{\sigma}\eta^{2}.$

That is, there is a cost proportional to $\eta^{2}/\sigma$ that does not
vanish as $c\to 1/2$. Meanwhile, all contributions to moments involving odd
powers of $\eta$ are proportional to $(1-2c)$. This is because the graphon is
invariant under the transformation $\eta\to-\eta$, $c\to 1-c$,
$a\leftrightarrow b$. The leading such contribution comes from $\mu_{3}$ and
goes as $(1-2c)\alpha^{2}\eta\approx(1-2c)\sigma^{2}\eta$ times a polynomial
in $c$ that does not vanish at $c=1/2$. Setting the derivative of the entropy
with respect to $\eta$ equal to zero tells us that $\eta=O(\sigma^{3}(1-2c))$.
All contributions from odd powers of $\eta$ are thus
$O(\sigma^{5}(1-2c)^{2})$, and so are dominated by the $\alpha^{3}$
contribution to $\mu_{3}$, while all contributions from even powers of $\eta$
are dominated by the $\mu^{2}/\sigma$ contribution to $\mu_{2}$.

∎

Thanks to Propositions 14 and 16, any graphon that does better than symmetric
bipodal in the region just below $t=e^{3}$ with $e<1/2$ must be at least
tripodal (or perhaps not even multipodal at all) and the difference between
that graphon and a constant graphon must have rank at least two. That is
exactly what we construct in the proof of Theorem 3.

###### Proof of Theorem 3.

We consider values of $e$ and $t=e^{3}-\sigma^{3}$ where $e<e_{0}$ and
$\sigma$ is sufficiently small. The number $e_{0}$ is defined by the equation

(58)
$3H^{\prime\prime\prime}(e_{0})^{2}=H^{\prime\prime}(e_{0})H^{\prime\prime\prime\prime}(e_{0}),$

which simplifies to $6e_{0}^{2}-6e_{0}+1=0$, or $e_{0}=(3-\sqrt{3})/6\approx
0.2113$. When $e<e_{0}$, $3H^{\prime\prime\prime}(e)^{2}$ is greater than
$H^{\prime\prime}(e)H^{\prime\prime\prime\prime}(e)$. In fact, as $e\to 0$,
$3H^{\prime\prime\prime}(e)^{2}$ goes as $3e^{-4}$, while
$H^{\prime\prime}(e)H^{\prime\prime\prime\prime}(e)$ goes as $2e^{-4}$.
However, as $e$ approaches $1/2$, $3H^{\prime\prime\prime}(e)^{2}$ goes to
zero while $H^{\prime\prime}(e)H^{\prime\prime\prime\prime}(e)$ does not.

Let $A>B>0$ and let

(59)
$F(A,B)=\frac{H(e+A+B)+H(e-A+B)-2H(e)-2BH^{\prime}(e)}{(A^{3}-B^{3})^{2/3}}.$

We will eventually choose $A$ and $B$ to maximize $F(A,B)$. Pick a small
number $c$ and divide the interval $[0,1]$ into three pieces:

$I_{1}=[0,c/2],\qquad I_{2}=(c/2,c],\qquad I_{3}=(c,1].$

Consider the graphon

(60) $g(x,y)=\begin{cases}e-A+B(1-c)&(x,y)\in I_{1}\times I_{1}\cup
I_{2}\times I_{2}\cr e+A+B(1-c)&(x,y)\in I_{1}\times I_{2}\cup I_{2}\times
I_{1}\cr e-cB&(x,y)\in[(I_{1}\cup I_{2})\times
I_{3}]\cup[I_{3}\times(I_{1}\cup I_{2})]\cr e+\frac{c^{2}}{1-c}B&(x,y)\in
I_{3}\times I_{3}.\end{cases}$

Equivalently, $g(x,y)=e-cAv_{1}(x)v_{1}(y)+cBv_{2}(x)v_{2}(y)$, where

$v_{1}(x)=\begin{cases}c^{-1/2}&x\in I_{1},\cr-c^{-1/2}&x\in I_{2},\cr 0&x\in
I_{3},\end{cases}\qquad v_{2}(x)=\begin{cases}\sqrt{(1-c)/c}&x\in I_{1}\cup
I_{2},\cr-\sqrt{c/(1-c)}&x\in I_{3}.\end{cases}$

This graphon has edge density $\varepsilon(g)=e$ and triangle density

$\tau(g)=e^{3}-c^{3}A^{3}+c^{3}B^{3}.$

Setting the triangle density equal to $e^{3}-\sigma^{3}$ gives

$c=\sigma(A^{3}-B^{3})^{-1/3}.$

We now estimate the entropy

(62) $\displaystyle S(g)$ $\displaystyle=$
$\displaystyle\frac{c^{2}}{2}H\big{(}e-A+(1-c)B\big{)}+\frac{c^{2}}{2}H\big{(}e+A+(1-c)B\big{)}$
$\displaystyle+2c(1-c)H\big{(}e-cB\big{)}+(1-c)^{2}H\left(e+\frac{c^{2}}{1-c}B\right)$

to order $c^{2}$, or equivalently to order $\sigma^{2}$. The first two terms
already are $O(c^{2})$, so we can simply replace $e\pm A+(1-c)B$ with $e\pm
A+B$. For the remaining terms, we can use a linear approximation for $H(u)$.
The result is

(63) $\displaystyle S(g)$ $\displaystyle=$ $\displaystyle
H(e)+\frac{c^{2}}{2}\left[H(e-A+B)+H(e+A+B)-2H(e)-2BH^{\prime}(e)\right]+O(c^{3})$
(65) $\displaystyle=$ $\displaystyle
H(e)+\frac{1}{2}F(A,B)\sigma^{2}+O(\sigma^{3}).$

For comparison, the symmetric bipodal graphon has entropy

$H(e)+\frac{1}{2}H^{\prime\prime}(e)\sigma^{2}+O(\sigma^{4}).$

If $F(A,B)>H^{\prime\prime}(e)$, and if $\sigma$ is sufficiently small, then
the tripodal graphon has more entropy than the symmetric bipodal graphon.

What remains is showing that we can get $F(A,B)>H^{\prime\prime}(e)$ when
$e<e_{0}$. Let $A$ be a small positive number and let

$B=-\frac{H^{\prime\prime\prime}(e)}{2H^{\prime\prime}(e)}A^{2}.$

Since $H^{\prime\prime\prime}(e)>0>H^{\prime\prime}(e)$, $B$ is positive.
Since $A^{3}-B^{3}=A^{3}+O(A^{6})$, $(A^{3}-B^{3})^{2/3}=A^{2}+O(A^{5})$. We
compute the numerator of $F(A,B)$ to order $A^{4}$ by doing a 4-th order
Taylor series expansion of $H(e-A+B)$ and $H(e+A+B)$ around $e$ and keeping
terms proportional to $A^{2}$, $A^{4}$, $B$, $B^{2}$, and $A^{2}B$. (The
expression is even in $A$, so we only get even powers of $A$.) The result is

(66) $\displaystyle F(A,B)$ $\displaystyle=$
$\displaystyle\frac{(A^{2}+B^{2})H^{\prime\prime}(e)+A^{2}BH^{\prime\prime\prime}(e)+\frac{1}{12}A^{4}H^{\prime\prime\prime\prime}(e)+O(A^{6})}{(A^{3}-B^{3})^{2/3}}$
(67) $\displaystyle=$
$\displaystyle\frac{A^{2}H^{\prime\prime}(e)+A^{4}\left(\frac{H^{\prime\prime\prime\prime}(e)}{12}-\frac{(H^{\prime\prime\prime}(e))^{2}}{4H^{\prime\prime}(e)}\right)+O(A^{6})}{A^{2}+O(A^{5})}$
(68) $\displaystyle=$ $\displaystyle
H^{\prime\prime}(e)+\left(\frac{H^{\prime\prime\prime\prime}(e)}{12}-\frac{(H^{\prime\prime\prime}(e))^{2}}{4H^{\prime\prime}(e)}\right)A^{2}+O(A^{3}).$

Since $e<e_{0}$, the coefficient of $A^{2}$ is positive, so
$F(A,B)>H^{\prime\prime}(e)$ when $A$ is small. ∎

##  7\. Symmetry as an order parameter

Question: Considering Figure 3 and the two open subsets $\mathcal{O}$ and
$\mathcal{O}_{1}$ there defined by Figure 1 and Figure 4, could $\mathcal{O}$
and $\mathcal{O}_{1}$ be part of the same phase?

Although there is no barrier between $\mathcal{O}$ and $\mathcal{O}_{1}$ like
the curve $t=e^{3}$ between $\mathcal{O}_{2}$ and $\mathcal{O}_{1}$, the
answer must be “no”, thanks to the following symmetry argument. On
$\mathcal{O}$, the entropy-maximizing graphon has constant degree function
$d(x)=\int_{0}^{1}g(x,y)\,dy=e$. The density $T_{2}$ of 2-stars is given by
the integral $\int_{0}^{1}d(x)^{2}\,dx$, so $Q=T_{2}-e^{2}$ is identically
zero on $\mathcal{O}$. If $\mathcal{O}$ and $\mathcal{O}_{1}$ were part of the
same phase and we had any analytic curve $c(s)$ running between them, then $Q$
would have to be zero on the first part of the curve and then by analyticity
it would have to be zero on the entire curve. However, it is easy to check
that $Q$ is not zero on all of $\mathcal{O}_{1}$, insofar as the degree
function for the graphon of Theorem 6 is not constant. Instead, $Q$ is a
nonzero multiple of $\sigma^{5}$ plus $O(\sigma^{6})$. This contradiction
proves our assertion. ∎

This argument has a very similar flavor to an argument that is common in
statistical physics. There, if you can find an “order parameter” [1, 29], a
physical quantity which is identically zero on an open subset of the parameter
space and nonzero in another, then it cannot be analytic along any path from
the first region to the second, so the open subsets cannot be parts of the
same phase. Finding such an order parameter can be very difficult, but once
found it can be very useful as we now show.

To appreciate the subtleties associated with some phase transitions in real
materials, consider water in various common states. First consider gaseous
water (steam) at temperature $T_{1}$ just above $100^{\circ}$ Celsius and
atmospheric pressure $P$, and liquid water at temperature $T_{2}$ just below
$100^{\circ}$ Celsius and again pressure $P$. The mass density is much lower
in that gaseous state than in that liquid state, so in any reasonable sense
there is a sharp transition in state corresponding to the (arbitrarily) small
change in temperature. Now consider the pair of states: liquid water at
temperature $T_{3}$ just above $0^{\circ}$ Celsius and atmospheric pressure
$P$ and solid water (ice) at temperature $T_{4}$ just below $0^{\circ}$
Celsius and again pressure $P$. Again the mass density is different between
these two states (ice floats on water) so again in any reasonable sense there
is a sharp transition in state corresponding to the (arbitrarily) small change
in temperature.

There is a big difference between these two transitions. Consider a different
way of changing the state from that gaseous state to its ‘neighboring’ liquid
state. It is expermentally possible, by slowly accessing high temperatures and
high pressures to use a different path between these two states without making
any sharp change in state! (One says there is a ‘critical’ point in the
gas/liquid transition.) But again experimentally, there is NO critical point
in the liquid/solid transition; however you vary temperature and pressure to
move slowly between a state of liquid water and a state of solid ice you must
go through a sharp transition. Percy Bridgman received the Nobel prize in 1946
for his extensive experiments on high pressure, one result of which was to
demonstrate that there is no critical point on the transition between fluid
and solid in any known material. It is an old problem to try to understand why
this should be the case. Consider the following quote in [31, page 11]

  * The most outstanding unsolved problem of equilibrium statistical mechanics is the problem of the phase transitions. Why do all substances occur in at least three phases, the solid, liquid, and vapor phase which can coexist in the triple point? Why is there, again for all substances, a critical point for the vapor-liquid equilibrium, while apparently there is no critical point for the fluid-solid transition. Note that since these are general phenomena, they must have a general explanation; the precise details of the molecular structure and of the intermolecular forces should not matter.

As described in [1, page 19], Lev Landau tried to use symmetry as an order
parameter to solve this problem:

  * It was Landau (1958) who, long ago, first pointed out the vital importance of symmetry in phase transitions. This, the First Theorem of solid-state physics, can be stated very simply: it is impossible to change symmetry gradually. A given symmetry element is either there or it is not; there is no way for it to grow imperceptibly. This means, for instance, that there can be no critical point for the melting curve as there is for the boiling point: it will never be possible to go continuously through some high-pressure phase from liquid to solid.

While appealing, Landau’s argument is not universally accepted; see [22, page
122]. Part of the problem is that there is no known model in equilibrium
statistical mechanics which can be proven to exhibit both fluid and solid
phases [4, 31]. Even if such phases were proven to exist, it isn’t at all
clear how to define an appropriate order parameter.

Yet that is exactly what we have done in the context of random graphs at the
beginning of this section: we contrasted the subset $\mathcal{O}$, part of a
“symmetric” phase in which the order parameter $Q$ vanishes identically, with
part of a phase in which $Q$ is not zero.

Of course this is not a solution of the classic problem of proving a solid-
fluid phase transition in a reasonable statistical mechanics model; we are
working with random graphs, not with configurations of atoms. But that’s
actually the point! Graph models are a wonderful laboratory for developing,
with full mathematical rigor, techniques that are simply too hard in
statistical physics, a laboratory where important structural questions can be
successfully solved.

##  8\. Summary

This paper is part of a series [27, 28, 24, 25, 26, 11, 12, 13, 10, 13, 26,
19, 21] studying combinatorial systems (graphs, permutations, sphere packing)
under competing constraints, as an extension of extremal combinatorics but
concentrating on nonextreme states of the systems, that is, states under
nonextreme constraints. We study asymptotically large systems and for graphs
and permutations we use a large deviation principle (LDP) to analyze “typical”
(i.e. exponentially most) constrained states. (We do not know an LDP for
sphere packing but analyze such systems using the hard sphere model [18] in
equilibrium statistical mechanics.) In this paper we sharpened our notion of
phase by the use of analyticity; see Section 7.

Our goal in studying typical nonextremely-constrained states in these
combinatorial systems is to analyze emergent smoothness response to
infinitesimal change in the constraints, and of the combinatorial systems we
have considered we have found dense graphs the most amenable to development.

By design our graph modelling has many features in common with that of the
equilibrium statistical mechanics of particles with short range forces, but
has a significant difference: there is no “distance” between edges, so each
edge has the same influence on any other edge. In statistical mechanics,
models with this feature of the influence of particles on one another are
called “mean-field”, and although not part of the mathematical formalism [29],
mean-field models such as Curie-Weiss and van der Waals [30] are used to study
phase transitions where more physical models prove too difficult. The random
graph model we have been discussing has, in this sense, more in common with
mean-field models of statistical mechanics, and, as seen by our success in
proving the existence of phases and phase transitions, may be able to provide
a mathematical formalism for studying the asymptotics of graphs and other
combinatorial objects which will be as fruitful mathematically as statistical
mechanics has been.

We conclude with the following open problems in this edge/triangle model.

  1. (1)

What is the actual structure of the optimal graphon when $e<e_{0}$ and $t$ is
slightly below $e^{3}$? Does it resemble the example given in Section 6, or is
its structure still wilder? How does the behavior of this graphon as
$\sigma\to 0$ compare to the moderate deviations results for $G(n,m)$ in [20]?

  2. (2)

Is there a succession of phases as $e\to 0$ and $t$ remains close to $e^{3}$,
with tripodal graphons giving way to 4-podal, 5-podal, and so on?

  3. (3)

When $e_{0}<e<1/2$ and $t$ is slightly less than $e^{3}$, is the optimal
graphon symmetric bipodal, or is it something else?

  4. (4)

When $e<1/2$ and $t=0$, the optimal graphon is symmetric bipodal. What if
$e<1/2$ and $t$ is slightly positive?

  5. (5)

Proposition 16 is stated for $t$ close to $e^{3}$. However, the only step in
the proof that uses $t\approx e^{3}$ is the estimate that $\eta$ is much
smaller than $\alpha$. Can the result be extended to the entire region
$e<1/2$, $t<e^{3}$?

  6. (6)

In [12] it is proven that there are two open sets with supersatured triangles,
$t>e^{3}$, which extend to phases. One of these is bounded below by the curve
$t=e^{3},e<1/2$, while the other is bounded by $t=e^{3},e>1/2$. Are these
actually parts of the same phase, or are they distinct?

  7. (7)

In Section 4 of [13], numerical evidence is given of phase transitions in the
edge/triangle model along curves where the entropy-optimizing graphon is not
unique. It would be of interest to prove this. In principle, it may also be
possible to have regions of positive area on which the optimizing graphon is
not unique, which would be a challenge to interpret.

## References

  * [1] P.W. Anderson, Basic Notions of Condensed Matter Physics, Benjamin/Cummings, Menlo Park, 1984.
  * [2] C. Borgs, J. Chayes and L. Lovász, Moments of two-variable functions and the uniqueness of graph limits, Geom. Funct. Anal. 19 (2010) 1597-1619.
  * [3] C. Borgs, J. Chayes, L. Lovász, V.T. Sós and K. Vesztergombi, Convergent graph sequences I: subgraph frequencies, metric properties, and testing, Adv. Math. 219 (2008) 1801-1851.
  * [4] S. G. Brush, Statistical Physics and the Atomic Theory of Matter, from Boyle and Newton to Landau and Onsager, Princeton University Press, Princeton, 1983, 277.
  * [5] S. Chatterjee and P. Diaconis, Estimating and understanding exponential random graph models, Ann. Statist. 41 (2013) 2428-2461; arXiv:1102.2650 (2011).
  * [6] S. Chatterjee and S. R. S. Varadhan, The large deviation principle for the Erdős-Rényi random graph, Eur. J. Comb., 32 (2011) 1000-1017; arXiv:1008.1946 (2010)
  * [7] A. Dembo and E. Lubetzky, A large deviation principle for the Erdős-Rényi uniform random graph, Electron. Commun. Probab. 23 (2018) 1-13.
  * [8] R. Ellis, Entropy, Large Deviations, and Statistical Mechanics, Springer-Verlag, Berlin, 2006.
  * [9] R. Israel, Convexity in the Theory of Lattice Gases, Princeton University Press, Princeton, 1979.
  * [10] R. Kenyon, D. Král’, C. Radin, P. Winkler, Permutations with fixed pattern densities, Random Structures Algorithms, 56 (2020) 220-250.
  * [11] R. Kenyon, C. Radin, K. Ren, and L. Sadun, Multipodal structures and phase transitions in large constrained graphs, J. Stat. Phys. 168(2017) 233-258.
  * [12] R. Kenyon, C. Radin, K. Ren and L. Sadun, Bipodal structure in oversaturated random graphs, Int. Math. Res. Notices 2018(2016) 1009-1044.
  * [13] R. Kenyon, C. Radin, K. Ren and L. Sadun, The phases of large networks with edge and triangle constraints, J. Phys. A: Math. Theor. 50 (2017) 435001.
  * [14] L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 98 (2006) 933-957.
  * [15] L. Lovász and B. Szegedy, Szemerédi’s lemma for the analyst, GAFA 17 (2007) 252-270.
  * [16] L. Lovász and B. Szegedy, Finitely forcible graphons, J. Combin. Theory Ser. B 101 (2011) 269-301.
  * [17] L. Lovász, Large Networks and Graph Limits, American Mathematical Society, Providence, 2012.
  * [18] H. Löwen, Fun with hard spheres, pages 295-331 in Statistical physics and spatial statistics : the art of analyzing and modeling spatial structures and pattern formation, ed. K.R. Mecke and D. Stoyen, Lecture notes in physics No. 554, Springer-Verlag, Berlin, 2000.
  * [19] J. Neeman, C. Radin and L. Sadun, Phase transitions in finite random networks, J Stat Phys 181 (2020) 305-328.
  * [20] J. Neeman, C. Radin and L. Sadun, Moderate deviations in triangle count, Random Struct. Algorithms (2023), 1-42, https://doi.org/10.1002/rsa.21147, arXiv:2101.08249 (2021)
  * [21] J. Neeman, C. Radin and L. Sadun, Typical large graphs with given edge and triangle densities, Probab. Theory Relat. Fields (2023), https://doi.org/10.1007/s00440-023-01187-8, arXiv:2110.14052 (2021)
  * [22] A. Pippard, The Elements of Classical Thermodynamics, Cambridge University Press, Cambridge, 1979.
  * [23] O. Pikhurko and A. Razborov, Asymptotic structure of graphs with the minimum number of triangles, Combin. Probab. Comput. 26 (2017) 138 - 160; arXiv:1204.2846 (2012)
  * [24] C. Radin, K. Ren and L. Sadun, The asymptotics of large constrained graphs, J. Phys. A: Math. Theor. 47 (2014) 175001.
  * [25] C. Radin, K. Ren and L. Sadun, A symmetry breaking transition in the edge/triangle network model, Ann. Inst. H. Poincaré D 5 (2018) 251-286.
  * [26] C. Radin, K. Ren and L. Sadun, Surface effects in dense random graphs with sharp edge constraint, arXiv:1709.01036v2 (2017)
  * [27] C. Radin and L. Sadun, Phase transitions in a complex network, J. Phys. A: Math. Theor. 46 (2013) 305002; arXiv:1301.1256 (2013)
  * [28] C. Radin and L. Sadun, Singularities in the entropy of asymptotically large simple graphs, J. Stat. Phys. 158 (2015) 853-865.
  * [29] D. Ruelle, Statistical Mechanics; Rigorous Results (Benjamin, New York, 1969.
  * [30] C.J. Thompson, Mathematical Statistical Mechanics (Princeton University Press, Princeton, 1972.
  * [31] G.E. Uhlenbeck, in Fundamental Problems in Statistical Mechanics II, edited by E. G. D. Cohen, Wiley, New York, 1968.