# Ordered and colored subgraph density problems

Emily Cairncross Department of Mathematics, Statistics and Computer Science,
University of Illinois, Chicago, IL 60607. Email<EMAIL_ADDRESS>Research
partially supported by NSF Award DMS-1952767. Dhruv Mubayi Department of
Mathematics, Statistics and Computer Science, University of Illinois, Chicago,
IL 60607. Email<EMAIL_ADDRESS>Research partially supported by NSF Awards
DMS-1952767 and DMS-2153576, and by a Simons Fellowship.

###### Abstract

We consider three extremal problems about the number of copies of a fixed
graph in another larger graph. First, we correct an error in a result of
Reiher and Wagner [13] and prove that the number of $k$-edge stars in a graph
with density $x\in[0,1]$ is asymptotically maximized by a clique and isolated
vertices or its complement. Next, among ordered $n$-vertex graphs with $m$
edges, we determine the maximum and minimum number of copies of a $k$-edge
star whose nonleaf vertex is minimum among all vertices of the star. Finally,
for $s\geq 2$, we define a particular 3-edge-colored complete graph $F$ on
$2s$ vertices with colors blue, green and red, and determine, for each
$(x_{b},x_{g})$ with $x_{b}+x_{g}\leq 1$ and $x_{b},x_{g}\geq 0$, the maximum
density of $F$ in a large graph whose blue, green and red edge sets have
densities $x_{b},x_{g}$ and $1-x_{b}-x_{g}$, respectively. These are the first
nontrivial examples of colored graphs for which such complete results are
proved.

##  1 Introduction

The density of a graph $G$ with $n$ vertices and $m$ edges is
$\varrho(G):=m/\binom{n}{2}$. For a graph $F$ with $k\leq n$ vertices, let
$N(F,G)$ be the number of subgraphs of $G$ that are isomorphic to $F$. We are
interested in the minimum and maximum values of $N(F,G)$ over graphs $G$ with
a given value of $\varrho(G)$ as $n$ grows. We note that
$N(F,G)\leq(n)_{k}/|{\operatorname{Aut}}(F)|$ where ${\operatorname{Aut}}(F)$
is the automorphism group of $G$. Define the density of $F$ in $G$ to be

$\varrho(F,G):=\frac{N(F,G)\cdot|{\operatorname{Aut}}(F)|}{(n)_{k}}\in[0,1].$

The classical Kruskal-Katona theorem [5, 6] implies that the maximum density
of $K_{s}$ in a graph of density $x$ is achieved by a clique and isolated
vertices. The minimum density of $K_{s}$ in a graph with density $x$ was
determined by Razborov [11] for $s=3$, by Nikiforov [10] for $s=4$, and by
Reiher [12] for all $s\geq 4$; this is achieved by complete multipartite
graphs. Let $S_{k}$ denote the $k$-edge star. Ahlswede and Katona [1]
determined the maximum number of $S_{2}$’s in a graph with density $x$. Reiher
and Wagner [13] claim to prove that the asymptotic maximum value of
$N(S_{k},G)$ when $G$ has density $x$, is achieved by a clique and isolated
vertices or its complement. We correct an error in their proof. We also
consider this problem in the setting of ordered graphs and prove the first
nontrivial results on $S_{k}$ whose vertices have a particular order.

Finally, we consider similar questions in the induced setting. For $G$ with
$n$ vertices and $F$ with $k$ vertices, let $N_{\operatorname{ind}}(F,G)$ be
the number of induced subgraphs of $G$ that are isomorphic to $F$. In other
words, $N_{\operatorname{ind}}(F,G)$ is the number of $S\subset V(G)$ such
that $G[S]\cong F$. Let
$\varrho_{\operatorname{ind}}(F,G)=N_{\operatorname{ind}}(F,G)/\binom{n}{k}$
be the induced density of $F$ in $G$. In [7], the authors consider the region
of possible asymptotic values of $\varrho_{\operatorname{ind}}(F,G)$ for
graphs $G$ of fixed density. By coloring edges in $G$ and $F$ red, and
coloring edges in their complements blue, it is apparent that counting induced
subgraphs is the same as counting copies of a two-edge-colored clique in a
(larger) two-edge-colored clique. This leads us to consider the maximum
asymptotic density of $q$-edge-colored cliques in (larger) $q$-edge-colored
cliques with given color densities. For $q=3$, we prove the first nontrivial
result in this setting.

In Section 2, we state our results. They are proved in Sections 3, 4, and 5.

##  2 Statements of results

###  2.1 Stars

Clearly $N(S_{k},G)=\sum_{v\in V(G)}\binom{d(v)}{k}$ and
$\varrho(S_{k},G)=N(S_{k},G)\cdot k!/(n)_{k+1}.$ For $x\in[0,1]$, let
$I(S_{k},x)$ be the supremum of $\lim_{n\to\infty}\varrho(S_{k},G_{n})$ over
all sequences of graphs $(G_{n})_{n=1}^{\infty}$ with
$|V(G_{n})|\rightarrow\infty$, $\varrho(G_{n})\rightarrow x$ and for which
$\lim_{n\to\infty}\varrho(S_{k},G_{n})$ exists. For each $\gamma\in[0,1]$, let
$\eta=1-\sqrt{1-\gamma}$. Then $\gamma^{(k+1)/2}$ and $\eta+(1-\eta)\eta^{k}$
are the asymptotic $S_{k}$-densities in a clique with isolated vertices and
the complement of a clique with isolated vertices, both with density $\gamma$.
Consequently,

$I(S_{k},\gamma)\geq\max\\{\gamma^{(k+1)/2},~{}\eta+(1-\eta)\eta^{k}\\}.$

Reiher and Wagner [13] proved matching upper bounds on $I(S_{k},\gamma)$.
Their results are stated (and proved) using the language of graphons, which
are limit object of graphs. Formally, a graphon $W$ is a symmetric, measurable
function $W:[0,1]^{2}\to[0,1]$ (see Lovász [8] for background on graphons).
For a graphon $W$, let $d_{W}(x)=\int_{0}^{1}W(x,y)~{}dy$ be the degree of $x$
in $W$, let $t(|,W)=\int_{[0,1]^{2}}W(x,y)~{}dxdy$ be the density of $W$, and
let

$t(S_{k},W)=\int_{0}^{1}d_{W}^{k}(x)~{}dx$

be the homomorphism density of $S_{k}$ in $W$.

######  Theorem 2.1 (Reiher-Wagner [13]).

Let $W$ be a graphon and let $k$ be a positive integer. Set $\gamma=t(|,W)$
and $\eta=1-\sqrt{1-\gamma}$. Then

$t(S_{k},W)\leq\max\\{\gamma^{(k+1)/2},~{}\eta+(1-\eta)\eta^{k}\\}.$

By the general theory of graphons, Theorem 2.1 gives the same upper bound for
$I(S_{k},\gamma)$. There appears to be an error in the proof of [13,
Proposition 3.7], which is necessary for the proof of Theorem 2.1. We correct
this error and prove Theorem 2.1 in Section 3.

###  2.2 Ordered stars

An ordered graph $G=(V,E)$ is a graph with a total order on $V$. We usually
let $V=[n]:=\\{1,\ldots,n\\}$ with the natural ordering. When $i<j$ and
$\\{i,j\\}\in E$, we often write $ij\in E$. Let $F$ be an ordered graph on
$[s]$. Let $N_{{\operatorname{ord}}}(F,G)$ be the number of
$\\{v_{1},\ldots,v_{s}\\}\subseteq[n]$ with $v_{1}<v_{2}<\cdots<v_{s}$ such
that $v_{i}v_{j}\in E(G[v_{1},\ldots,v_{s}])$ whenever $ij\in E(F)$. We
consider $N_{{\operatorname{ord}}}(F,G)$ in the case that $F$ is an
appropriate ordered $S_{k}$. The following constructions provide lower bounds.

######  Construction 2.2.

For positive integers $n$ and $m\leq\binom{n}{2}$, let $a$ be the largest
integer such that $f(n,a):=\binom{a}{2}+a(n-a)\leq m$. As $f(n,n)={n\choose
2}$, we have $0\leq a\leq n$. Set $b=m-f(n,a)$. Since $f(n,a+1)-f(n,a)=n-a-1$,
we conclude that $0\leq b<n-a-1$. Let $S_{L}(n,m)$ be the ordered graph with
vertex set $[n]$ and edge set

$\\{vw:v\in[a],w\in[n]\\}\cup\\{\\{a+1,j\\}:a+2\leq j\leq a+b+1\\}.$

In words, $S_{L}(n,m)$ comprises a complete graph on $[a]$, and in addition
has all edges between $[a]$ and $[n]\setminus[a]$ and $b$ edges between $a+1$
and the $b$ smallest vertices in $[n]\setminus[a+1]$ (see Figure 1). Let
$S_{R}(n,m)$ be defined as $S_{L}(n,m)$, but where the total order on the
vertices is reversed.

Figure 1: $S_{L}(n,m)$.

Let $S_{L}(k):=S_{L}(k+1,k)$ be the ordered left star and
$S_{R}(k):=S_{R}(k+1,k)$ the ordered right star. Note that $S_{L}(k)$ has
$a=1$ and $b=0$ (see Figure 2).

Figure 2: $S_{L}(k)$ and $S_{R}(k)$.

Our main result for ordered graphs is the following theorem.

######  Theorem 2.3.

Let $G$ be an ordered graph with vertex set $[n]$ and $m>0$ edges. Then

$N_{\operatorname{ord}}(S_{L}(k),S_{R}(n,m))\leq
N_{\operatorname{ord}}(S_{L}(k),G)\leq
N_{\operatorname{ord}}(S_{L}(k),S_{L}(n,m)).$

Theorem 2.3 implies similar results for $S_{R}(k)$. There are, up to obvious
symmetries, $\lceil(k+1)/2\rceil$ different ordered stars with $k$ edges and,
apart from $S_{L}(k)$, it remains open to prove analogous results to Theorem
2.3 for them. Indeed, obtaining sharp bounds for these stars seems nontrivial.
We address the first open case when $k=2$.

Let $M$ be the ordered graph with vertex set $[3]$ and edge set $\\{12,23\\}$.
It seems very difficult to obtain exact results for
$N_{\operatorname{ord}}(M,G)$ so we consider asymptotic growth rates. Let

$\varrho_{\operatorname{ord}}(F,G):=\frac{N_{{\operatorname{ord}}}(F,G)}{\binom{n}{s}}$

be the density of $F$ in $G$. Since the vertices are ordered, each $s$-tuple
of vertices can contribute at most one copy of $F$ so
$\varrho_{\operatorname{ord}}(F,G)\in[0,1]$. Let $(G_{n})_{n=1}^{\infty}$ be a
sequence of ordered graphs with $\lim_{n\to\infty}|V(G_{n})|=\infty$. The
sequence $(G_{n})_{n=1}^{\infty}$ is $F$-good if both
$x=\lim_{n\to\infty}\varrho(G_{n})$ and
$y=\lim_{n\to\infty}\varrho_{\operatorname{ord}}(F,G_{n})$ exist. In this
case, $(G_{n})_{n=1}^{\infty}$ realizes $(x,y)$. Define

$\displaystyle I_{{\operatorname{ord}}}(F,x)$
$\displaystyle:=\sup\\{y:(x,y)\in[0,1]\text{ is realized by some $F$-good
}(G_{n})_{n=1}^{\infty}\\},$ $\displaystyle i_{{\operatorname{ord}}}(F,x)$
$\displaystyle:=\inf\\{y:(x,y)\in[0,1]\text{ is realized by some $F$-good
}(G_{n})_{n=1}^{\infty}\\}.$

For any $x\in[0,1]$, Lovász and Simonovits [9] constructed a sequence of
$K_{3}$-good complete multipartite graphs $(G_{n})_{n=1}^{\infty}$ such that
$\lim_{n\to\infty}\varrho(G_{n})=x$. Set

$g_{3}(x):=\lim_{n\to\infty}\varrho(K_{3},G_{n}).$

Let $V_{1},\ldots,V_{k}$ be the parts of $G_{n}$ and let $G_{n}^{\prime}$ be
an ordered graph obtained from $G_{n}$ with any vertex ordering for which
$u<v$ whenever $u\in V_{i}$, $v\in V_{j}$ and $i<j$. Then
$N_{\operatorname{ord}}(M,G_{n}^{\prime})=N_{\operatorname{ord}}(K_{3},G_{n})$
and this implies that $i_{\operatorname{ord}}(M,x)\leq g_{3}(x)$. Razborov
[11] proved that $i_{\operatorname{ord}}(K_{3},x)\geq g_{3}(x)$. Note that $M$
is a subgraph of the ordered $K_{3}$, so $i_{\operatorname{ord}}(K_{3},x)\leq
i_{\operatorname{ord}}(M,x)$. Therefore,

$g_{3}(x)\leq i_{\operatorname{ord}}(K_{3},x)\leq i_{\operatorname{ord}}(M,x)$

and we conclude that
$i_{\operatorname{ord}}(M,x)=i_{\operatorname{ord}}(K_{3},x)=g_{3}(x)$.
Determining $I_{{\operatorname{ord}}}(M,x)$ appears to be more difficult.

######  Construction 2.4.

We construct a sequence of graphs $(P(n,x))_{n=1}^{\infty}$ for any
$x\in[0,1]$. For each $n$, define $P(n,x)$ to be the ordered graph on
$[n]=A\sqcup B\sqcup C$ where $|B|=\lfloor n(1-\sqrt{1-x})\rfloor$,
$||A|-|C||\leq 1$, and $a<b<c$ for all $a\in A$, $b\in B$, $c\in C$ with edge
set

$\\{ab:a\in A,b\in B\\}\cup\\{b_{1}b_{2}:b_{1},b_{2}\in B\\}\cup\\{bc:b\in
B,c\in C\\}.$

A short calculation shows that $\lim_{n\to\infty}\varrho(P(n,x))=x$ and

$\lim_{n\to\infty}\varrho_{\operatorname{ord}}(M,P(n,x))=-\frac{1}{2}\eta(\eta^{2}-3).$

######  Construction 2.5.

We construct a sequence of graphs $(Q(n,x))_{n=1}^{\infty}$ for any
$x\in[0,1]$. For each $n$, define $Q(n,x)$ to be the ordered graph on $[n]$
with edge set

$\\{ij:j-i\leq\lfloor(1-\sqrt{1-x})n\rfloor\\}.$

A short calculation shows that $\lim_{n\to\infty}\varrho(Q(n,x))=x$ and that
for $\eta=1-\sqrt{1-x}$,

$\lim_{n\to\infty}\varrho_{\operatorname{ord}}(M,Q(n,x))=\begin{cases}6\eta^{3}+6(1-2\eta)\eta^{2}&\text{
if }\eta\leq 1/2,\\\ 2\eta^{3}-6\eta^{2}+6\eta-1&\text{ if }\eta\geq
1/2.\end{cases}$

Constructions 2.4 and 2.5 show that for $\eta=1-\sqrt{1-x}$,

$I_{{\operatorname{ord}}}(M,x)\geq\max\mathopen{}\mathclose{{}\left\\{\lim_{n\to\infty}\varrho_{\operatorname{ord}}(M,P(n,x)),~{}\lim_{n\to\infty}\varrho_{\operatorname{ord}}(M,Q(n,x))}\right\\}.$

It is an interesting open problem to determine if the inequality is sharp.

######  Problem 2.6.

Is

$I_{{\operatorname{ord}}}(M,x)=\max\mathopen{}\mathclose{{}\left\\{\lim_{n\to\infty}\varrho_{\operatorname{ord}}(M,P(n,x)),~{}\lim_{n\to\infty}\varrho_{\operatorname{ord}}(M,Q(n,x))}\right\\}$

for any (possibly all) $x\in[0,1]$?

A short calculation shows that there exists $x_{0}\in[0,1]$ such that
$\lim_{n\to\infty}\varrho_{\operatorname{ord}}(M,Q(n,x))\leq\lim_{n\to\infty}\varrho_{\operatorname{ord}}(M,Q(n,x))$
iff $x<x_{0}$.

###  2.3 Colored graphs

A $q$-colored graph is a graph $G=(V,E)$ together with a coloring function
$f:E\to C$ where $|C|=q$. Fix $q\in\mathbb{Z}^{+}$ and let $G=(V,E)$ be a
$q$-colored complete graph with coloring function $f$. For $1\leq i\leq q$,
let $e_{i}(G)=|\\{e\in E:f(e)=i\\}|$ and let
$\varrho_{i}(G):=e_{i}(G)/\binom{|V|}{2}$ be the density of color $i$. Given a
$q$-colored complete graph $F$ with $|V(F)|=s$ and coloring function $g$, a
subset $X\subset V$ with $|X|=s$ is a copy of $F$ in $G$ if there is a
bijection $\sigma:V(F)\to X$ such that $g(uv)=g(\sigma(u)\sigma(v))$ for all
distinct $u,v\in V(F)$. Let $N_{q}(F,G)$ be the number of copies of $F$ in $G$
and let $\varrho_{q}(F,G):=N_{q}(F,G)/\binom{|V|}{s}$ be the density of $F$ in
$G$.

Let $(G_{n})_{n=1}^{\infty}$ be a sequence of $q$-colored complete graphs with
$|V(G_{n})|\to\infty$. The sequence $(G_{n})_{n=1}^{\infty}$ is $F$-good if
$x_{i}=\lim_{n\to\infty}\varrho_{i}(G_{n})$ exists for all $i\in[q]$ and
$y=\lim_{n\to\infty}\varrho_{q}(F,G_{n})$ exists. In this case,
$(G_{n})_{n=1}^{\infty}$ realizes $(x_{1},\ldots,x_{q-1},y)$. Note that we
only list $x_{1},\ldots,x_{q-1}$ since $x_{q}=1-(x_{1}+\cdots+x_{q-1})$.
Define

$I_{q}(F,(x_{1},\ldots,x_{q-1})):=\sup\\{y:(x_{1},\ldots,x_{q-1},y)\in[0,1]^{q}\text{
is realized by some $F$-good }(G_{n})_{n=1}^{\infty}\\}.$

For $2\leq s\leq t$, let $K_{s,t}^{\prime}$ be the $3$-colored clique on
vertex set $V=V_{1}\sqcup V_{2}$ with $|V_{1}|=s$ and $|V_{2}|=t$ with
coloring function $f$ defined by

$f(ij):=\begin{cases}\text{blue}&\text{if }i,j\in V_{1},\\\
\text{green}&\text{if }i,j\in V_{2},\\\
\text{red}&\text{otherwise},\end{cases}$

for all distinct $i,j\in[s+t]$ (see Figure 3).

Figure 3: $K_{3,4}^{\prime}$.

######  Theorem 2.7.

Let $2\leq s\leq t$ and $x_{b},x_{g},x_{r}\in[0,1]$ such that
$x_{b}+x_{g}+x_{r}=1$. When $\sqrt{x_{b}}+\sqrt{x_{g}}\leq 1$,

$I_{3}(K_{s,t}^{\prime},(x_{b},x_{g}))=x_{b}^{s/2}x_{g}^{t/2}\binom{s+t}{s}.$

When $\sqrt{x_{b}}+\sqrt{x_{g}}>1$,

$I_{3}(K_{s,s}^{\prime},(x_{b},x_{g}))=\mathopen{}\mathclose{{}\left(\frac{x_{r}}{2}}\right)^{s}\binom{2s}{s}.$

Theorem 2.7 determines $I_{3}(K_{s,s}^{\prime},(x_{b},x_{g}))$ for all vectors
$(x_{b},x_{g})$ in the region $x_{b},x_{g}\geq 0$ and $x_{b}+x_{g}\leq 1$.
Write ${\operatorname{ind}}(K_{s,s}^{\prime})$ for the inducibility of
$K_{s,s}^{\prime}$ which is the maximum value of
$I_{3}(K_{s,s}^{\prime},(x_{b},x_{g}))$. An easy optimization shows that

${\operatorname{ind}}(K_{s,s}^{\prime})=I_{3}(K_{s,s}^{\prime},(1/4,1/4))=\mathopen{}\mathclose{{}\left(\frac{1}{4}}\right)^{s}\binom{2s}{s}.$

Note that $I_{3}(K_{s,t}^{\prime},(x_{b},x_{g}))$ is not known when
$\sqrt{x_{b}}+\sqrt{x_{g}}>1$ and $s\neq t$.

##  3 Proof of Theorem 2.1

Given a function $F:[0,1]\to\mathbb{R}$, a graphon $W$, and $\gamma\in[0,1]$,
let

$\displaystyle D(F,W)$ $\displaystyle:=\int_{0}^{1}F(d_{W}(x))~{}dx,$
$\displaystyle\operatorname{MAX}(\gamma,F)$
$\displaystyle:=\max\\{(1-\sqrt{\gamma})F(0)+\sqrt{\gamma}F(\sqrt{\gamma}),~{}(1-\eta)F(\eta)+\eta
F(1)\\}$

where $\eta=1-\sqrt{1-\gamma}$. A measurable function $F:[0,1]\to\mathbb{R}$
is good for $W$ if

$D(F,W)\leq\operatorname{MAX}(\gamma,F)$

where $\gamma=t(|,W)$ and $\eta=1-\sqrt{1-\gamma}$; $F$ is bad for $W$ if it
is not good for $W$. A collection of measurable functions is good (bad) for
$W$ if all its members are good (bad) for $W$. In [13], a set $\mathscr{C}$ of
twice differentiable convex functions $F:[0,1]\to\mathbb{R}$ satisfying
certain conditions is defined. We do not need the details of the conditions
here, so we do not state them, but we note that $\mathscr{C}$ contains the
function $F(x)=x^{k}$.

The error in [13] appears in the proof of the following proposition.

######  Proposition 3.1 (corresponds to [13, Proposition 3.7]).

$\mathscr{C}$ is good for all step graphons.

To prove this proposition, we introduce the following more refined notion of
“good.” For any $\delta>0$, say that $F\in\mathscr{C}$ is $\delta$-good for a
graphon $W$ if

$D(F,W)<\operatorname{MAX}(\gamma,F)+\delta$

for $\gamma=t(|,W)$ and $\eta=1-\sqrt{1-\gamma}$. Say that $F$ is $\delta$-bad
for $W$ if it is not $\delta$-good for $W$.

We next show that several lemmas from [13] still apply when we replace “good”
with “$\delta$-good.” The proofs are almost exact copies of those in [13], and
are given in the Appendix.

######  Lemma 3.2 (corresponds to [13, Lemma 3.2]).

If all functions in $\mathscr{C}$ are $\delta$-good for a graphon $W$, then
the same is true for the graphon $1-W$.

Given a graphon $W$ and a real number $\lambda\in[0,1]$, let $[\lambda,W]$ be
the graphon satisfying

$[\lambda,W](x,y)=\begin{cases}0&\text{ if $0\leq x<\lambda$ or $0\leq
y<\lambda$,}\\\
W\mathopen{}\mathclose{{}\left(\frac{x-\lambda}{1-\lambda},~{}\frac{y-\lambda}{1-\lambda}}\right)&\text{otherwise}.\end{cases}$

######  Lemma 3.3 (corresponds to [13, Lemma 3.5]).

If $\lambda\in[0,1]$ and the graphon $W$ has the property that all functions
in $\mathscr{C}$ are $\delta$-good for it, then the same applies to
$[\lambda,W]$.

Similarly, let $[W,\lambda]$ be the graphon satisfying

$[W,\lambda](x,y)=\begin{cases}W\mathopen{}\mathclose{{}\left(\frac{x}{1-\lambda},~{}\frac{y}{1-\lambda}}\right)&\text{
if $0\leq x\leq 1-\lambda$ and $0\leq y\leq 1-\lambda$,}\\\
1&\text{otherwise}.\end{cases}$

The next lemma follows from the previous two lemmas and the observation that
$[W,\lambda]$ is isomorphic to $1-[\lambda,1-W]$.

######  Lemma 3.4 (corresponds to [13, Lemma 3.6]).

If all functions in $\mathscr{C}$ are $\delta$-good for the graphon $W$ and
$\lambda\in[0,1]$, then all functions in $\mathscr{C}$ are good for
$[W,\lambda]$ as well.

We now prove Proposition 3.1. Let $\mathcal{G}$ be the collection of all step
graphons and let $\mathcal{G}_{i}$ be the collection of all step graphons with
$i$ parts.

###### Proof of Proposition 3.1.

Suppose for a contradiction that there exists $W^{\prime}\in\mathcal{G}$ and
$F^{\prime}\in\mathscr{C}$ such that $F^{\prime}$ is bad for $W^{\prime}$.
This means that
$D(F^{\prime},W^{\prime})>\operatorname{MAX}(\gamma,W^{\prime})$. Then there
exists $\delta>0$ such that
$D(F^{\prime},W^{\prime})\geq\operatorname{MAX}(F^{\prime},W^{\prime})+\delta$.
In other words, $F^{\prime}$ is $\delta$-bad for $W^{\prime}$. Let

$\mathcal{S}=\mathcal{S}(\delta):=\\{(F,W)\in\mathscr{C}\times\mathcal{G}:\text{$F$
is $\delta$-bad for }W\\}.$

Note that $(F^{\prime},W^{\prime})\in\mathcal{S}$, so
$\mathcal{S}\neq\emptyset$ . Partition $\mathcal{S}$ into
$\bigcup_{i=1}^{\infty}\mathcal{S}_{i}$ where

$\mathcal{S}_{i}:=\\{(F,W)\in\mathscr{C}\times\mathcal{G}_{i}:\text{$F$ is
$\delta$-bad for $W$}\\}.$

Let $k$ be the smallest integer such that $\mathcal{S}_{k}\neq\emptyset$. From
[13, Observation 2.1] we have $k\geq 2$. Pick $F\in\mathscr{C}$ such that
$(F,W)\in\mathcal{S}_{k}$ for some $W$. Let

$\mathcal{W}:=\\{W:(F,W)\in\mathcal{S}_{k}\\}.$

Let $\mu$ be the Lebesgue measure on $\mathbb{R}$. Each $W\in\mathcal{W}$ is a
step function with respect to a partition
$\mathcal{P}=\\{P_{1},\ldots,P_{k}\\}$ of the unit interval with
$\alpha_{i}=\mu(P_{i})$ for all $i\in[k]$ and $\beta_{ij}$ the value attained
by $W$ on $P_{i}\times P_{j}$ for $i,j\in[k]$. By the choice of $k$, we deduce
$\alpha_{1},\ldots,\alpha_{k}>0$ for all $W\in\mathcal{W}$. Define

$T(W):=\sum_{i=1}^{k}\alpha_{i}(d_{W}(i))^{2}$

where

$d_{W}(i)=\int_{0}^{1}W(x,y)~{}dy=\sum_{j=1}^{k}\alpha_{j}\beta_{ij}$

for all $i\in[k]$.

######  Claim 3.5.

$T:=\sup_{W\in\mathcal{W}}T(W)=\max_{W\in\mathcal{W}}T(W)$.

###### Proof.

By the choice of $k$ and $F$, there is a sequence of step graphons
$(W_{n})_{n=1}^{\infty}$, each with $k$ parts, such that
$\lim_{n\to\infty}T(W_{n})=T$ and $F$ is $\delta$-bad for $W_{n}$ for all $n$.
Notice that each $W_{n}$ is defined by the measure of its parts
$\alpha_{n,i}\in(0,1)$ for all $i\in[k]$ and its entries
$\beta_{n,ij}\in[0,1]$ for all $i,j\in[k]$ (where $\sum\alpha_{n,i}=1$ and
$\beta_{n,ij}=\beta_{n,ji}$). Thus, each $k$-step graphon is defined by
$k+\binom{k+1}{2}$ parameters, which we can view as variables. For each of
these variables, we use the Bolzano-Weierstrass Theorem to recursively take
subsequences of $(W_{n})_{n=1}^{\infty}$ such that the given variable
converges. Call the resulting sequence $(W_{n}^{\prime})_{n=1}^{\infty}$.

For each $i,j$, let $\alpha_{i}^{\prime}:=\lim_{n\to\infty}\alpha_{n,i}$ and
$\beta_{ij}^{\prime}:=\lim_{n\to\infty}\beta_{n,ij}$. Note that we still have
$\sum\alpha_{i}^{\prime}=1$ and $\beta_{ij}^{\prime}=\beta_{ji}^{\prime}$. Let
$W^{\prime}\in\mathcal{G}_{k}$ have partition
$\mathcal{P}^{\prime}=\\{P_{1}^{\prime},\ldots,P_{k}^{\prime}\\}$ such that
$\mu(P_{i}^{\prime})=\alpha_{i}^{\prime}$ for all $i\in[k]$ and
$W^{\prime}(x,y)=\beta_{ij}^{\prime}$ whenever $x\in P_{i}^{\prime}$ and $y\in
P_{j}^{\prime}$ for all $i,j\in[k]$. Let $\gamma_{n}:=t(|,W_{n}^{\prime})$ and
$\gamma:=t(|,W^{\prime})$. We will now prove that $T(W^{\prime})=T$ and
$W^{\prime}\in\mathcal{W}$.

First, observe that

$\lim_{n\to\infty}\sum_{j=1}^{k}\alpha_{n,j}\beta_{n,ij}=\sum_{j=1}^{k}\lim_{n\to\infty}\alpha_{n,j}\beta_{n,ij}=\sum_{j=1}^{k}\alpha_{j}^{\prime}\beta_{ij}^{\prime}$

and

$\lim_{n\to\infty}\sum_{i=1}^{k}\alpha_{n,i}\mathopen{}\mathclose{{}\left(\sum_{j=1}^{k}a_{n,j}\beta_{n,ij}}\right)^{2}=\sum_{i=1}^{k}\alpha_{i}^{\prime}\lim_{n\to\infty}\mathopen{}\mathclose{{}\left(\sum_{j=1}^{k}a_{n,j}\beta_{n,ij}}\right)^{2}=\sum_{i=1}^{k}\alpha_{i}^{\prime}\mathopen{}\mathclose{{}\left(\sum_{j=1}^{k}a_{j}^{\prime}\beta_{ij}^{\prime}}\right)^{2}$

since all sums are finite and the limit of each summand exists. This gives

$T(W^{\prime})=\sum_{i=1}^{k}\alpha_{i}^{\prime}\mathopen{}\mathclose{{}\left(\sum_{j=1}^{k}a_{j}^{\prime}\beta_{ij}^{\prime}}\right)^{2}=\lim_{n\to\infty}\sum_{i=1}^{k}\alpha_{n,i}\mathopen{}\mathclose{{}\left(\sum_{j=1}^{k}a_{n,j}\beta_{n,ij}}\right)^{2}=\lim_{n\to\infty}T(W_{n})=T.$

We now show that $W^{\prime}\in\mathcal{W}$. As every $F\in\mathscr{C}$ is
twice differentiable, it is also continuous and so

$\lim_{n\to\infty}F\mathopen{}\mathclose{{}\left(\sum_{j=1}^{k}\alpha_{n,j}\beta_{n,ij}}\right)=F\mathopen{}\mathclose{{}\left(\lim_{n\to\infty}\sum_{j=1}^{k}\alpha_{n,j}\beta_{n,ij}}\right)=F\mathopen{}\mathclose{{}\left(\sum_{j=1}^{k}\alpha_{j}^{\prime}\beta_{ij}^{\prime}}\right).$

Since $F$ is continuous on the closed interval $[0,1]$, it is bounded, and we
further obtain

$\lim_{n\to\infty}\sum_{i=1}^{k}\alpha_{n,i}F\mathopen{}\mathclose{{}\left(\sum_{j=1}^{k}\alpha_{n,j}\beta_{n,ij}}\right)=\sum_{i=1}^{k}\alpha_{i}^{\prime}F\mathopen{}\mathclose{{}\left(\sum_{j=1}^{k}\alpha_{j}^{\prime}\beta_{ij}^{\prime}}\right)=D(F,W^{\prime}).$

Consequently,

$\lim_{n\to\infty}D(F,W_{n}^{\prime})=\lim_{n\to\infty}\int_{0}^{1}F(d_{W_{n}^{\prime}}(x))~{}dx=\lim_{n\to\infty}\sum_{i=1}^{k}\alpha_{n,i}F\mathopen{}\mathclose{{}\left(\sum_{j=1}^{k}\alpha_{n,j}\beta_{n,ij}}\right)=D(F,W^{\prime}).$

Next, observe that

$\lim_{n\to\infty}\int_{[0,1]^{2}}W_{n}^{\prime}(x,y)~{}dxdy=\lim_{n\to\infty}\sum_{i=1}^{k}\sum_{j=1}^{k}\alpha_{n,i}\alpha_{n,j}\beta_{n,ij}=\sum_{i=1}^{k}\sum_{j=1}^{k}\alpha_{i}^{\prime}\alpha_{j}^{\prime}\beta_{ij}^{\prime}=\int_{[0,1]^{2}}W^{\prime}(x,y)~{}dxdy$

as all sums are finite and
$\lim_{n\to\infty}\alpha_{n,i}\alpha_{n,j}\beta_{n,ij}$ exists for all
$i,j\in[k]$. Thus,

$\lim_{n\to\infty}\gamma_{n}=\lim_{n\to\infty}t(|,W_{n}^{\prime})=\lim_{n\to\infty}\int_{[0,1]^{2}}W_{n}^{\prime}(x,y)~{}dxdy=\int_{[0,1]^{2}}W^{\prime}(x,y)~{}dxdy=t(|,W^{\prime})=\gamma.$

Further, since $f(x)=\sqrt{x}$ is continuous on $[0,1]$,

$\displaystyle\lim_{n\to\infty}\operatorname{MAX}(\gamma_{n},F)$
$\displaystyle=\lim_{n\to\infty}\max\\{(1-\sqrt{\gamma_{n}})F(0)+\sqrt{\gamma_{n}}F(\sqrt{\gamma_{n}}),~{}(1-\eta_{n})F(\eta_{n})+\eta_{n}F(1)\\}$
$\displaystyle=\max\\{(1-\sqrt{\gamma})F(0)+\sqrt{\gamma}F(\sqrt{\gamma}),~{}(1-\eta)F(\eta)+\eta
F(1)\\}$ $\displaystyle=\operatorname{MAX}(\gamma,F)$

for $\eta_{n}=1-\sqrt{1-\gamma_{n}}$ and $\eta=1-\sqrt{1-\gamma}$. Finally, as
$F$ is $\delta$-bad for $W_{n}^{\prime}$,

$D(F,W^{\prime})=\lim_{n\to\infty}D(F,W_{n}^{\prime})\geq\lim_{n\to\infty}\operatorname{MAX}(\gamma_{n},F)+\delta=\operatorname{MAX}(\gamma,F)+\delta.$

This means that $F$ is $\delta$-bad for $W^{\prime}$. Therefore,
$W^{\prime}\in\mathcal{W}$ and the claim is proved. ∎

Fix $W\in\mathcal{W}$ with partition $\mathcal{P}=\\{P_{1},\ldots,P_{k}\\}$
and parameters $\alpha_{i}$ and $\beta_{ij}\in[0,1]$ for all $i,j\in[k]$ such
that $T(W)=T$. Recall that by the minimality of $k$, we know that
$\alpha_{i}\in(0,1)$. By definition of $\mathcal{W}$, $F$ is $\delta$-bad for
$W$. Set $d_{i}:=d_{W}(i)$. To obtain the necessary contradiction to complete
the proof of the proposition, we will show that $F$ is $\delta$-good for $W$,
i.e. that

$D(F,W)=\int_{0}^{1}F(d_{W}(x))~{}dx=\sum_{i=1}^{k}\alpha_{i}F(d_{i})<\operatorname{MAX}(\gamma,F)+\delta,$

for $\gamma=t(|,W)=\sum_{i=1}^{k}\alpha_{i}d_{i}$. Without loss of generality,
we may assume $d_{1}\leq d_{2}\leq\cdots\leq d_{k}$.

######  Claim 3.6 (corresponds to [13, Claim 3.8]).

If $1\leq r<s\leq k$ and $\beta_{ir}>0$, then $\beta_{is}=1$.

###### Proof of Claim 3.6.

Suppose, for contradiction, that $\beta_{ir}>0$ and $\beta_{is}<1$. Define
$Q\in\mathcal{G}_{k}$ with the same partition $\mathcal{P}$ as follows: let
$\delta_{ij}$ denote the Kronecker delta, and set, for $x\in P_{m}$ and $y\in
P_{n},$

$Q(x,y)=\begin{cases}-(1+\delta_{ir})\alpha_{s}&\text{ if
}\\{m,n\\}=\\{i,r\\},\\\ (1+\delta_{is})\alpha_{r}&\text{ if
}\\{m,n\\}=\\{i,s\\},\\\ 0&\text{ otherwise.}\end{cases}$

Let $\varepsilon\geq 0$ be maximal such that $W_{\varepsilon}=W+\varepsilon Q$
still satisfies $W_{\varepsilon}(x,y)\in[0,1]$ for all $x,y\in[0,1]$. By our
assumptions on $\beta_{ir}$ and $\beta_{is},$ we know that $\varepsilon>0$.

For all $j\in[k]$, let $d_{j}^{\prime}$ denote the value attained by
$d_{W_{\varepsilon}}(x)$ for all $x\in P_{j}$. We have

$d_{r}^{\prime}-d_{r}=-(1+\delta_{ir})\alpha_{i}\alpha_{s}\varepsilon+\delta_{ir}(1+\delta_{is})\alpha_{i}\alpha_{s}\varepsilon=-\alpha_{i}\alpha_{s}\varepsilon,$

and similarly

$d_{s}^{\prime}-d_{s}=\alpha_{i}\alpha_{r}\varepsilon.$

Further, if $i\not\in\\{r,s\\}$, then

$d_{i}^{\prime}-d_{i}=\alpha_{r}(\beta_{ir}-\alpha_{s})+\alpha_{s}(\beta_{is}+\alpha_{r})-(\alpha_{r}\beta_{ir}+\alpha_{s}\beta_{is})=0.$

Therefore $d_{j}^{\prime}=d_{j}$ for all $j\notin\\{r,s\\}$. Consequently,

$\displaystyle
T(W_{\varepsilon})-T(W)=\sum_{j=1}^{k}\alpha_{j}(d_{j}^{\prime})^{2}-\sum_{j=1}^{k}\alpha_{j}d_{j}^{2}$
$\displaystyle=\alpha_{r}(d_{r}-\alpha_{i}\alpha_{s}\varepsilon)^{2}-\alpha_{r}d_{r}^{2}+\alpha_{s}(d_{s}+\alpha_{i}\alpha_{r}\varepsilon)^{2}-\alpha_{s}d_{s}^{2}$
$\displaystyle=2\varepsilon\alpha_{i}\alpha_{r}\alpha_{s}(d_{s}-d_{r})+\varepsilon^{2}\alpha_{i}^{2}\alpha_{r}\alpha_{s}(\alpha_{r}+\alpha_{s})$
$\displaystyle\geq\varepsilon^{2}\alpha_{i}^{2}\alpha_{r}\alpha_{s}(\alpha_{r}+\alpha_{s})>0$

since $\alpha_{i},\alpha_{r},\alpha_{s},\varepsilon>0$ and $d_{s}\geq d_{r}$
by assumption. Thus $T(W_{\varepsilon})>T(W)$, and clearly
$W_{\varepsilon}\in\mathcal{G}_{k}$, so we conclude by the choice of $W$ that
$W_{\varepsilon}\not\in\mathcal{W}$. To complete the proof, we will now obtain
the contradiction $W_{\varepsilon}\in\mathcal{W}$ by showing that $F$ is
$\delta$-bad for $W_{\varepsilon}$. First, observe that

$\int_{[0,1]^{2}}Q(x,y)~{}dxdy=\alpha_{i}\alpha_{r}\alpha_{s}((1+\delta_{is})(2-\delta_{is})-(1+\delta_{ir})(2-\delta_{ir}))=0.$

This implies that $t(|,W_{\varepsilon})=t(|,W)=\gamma$. Next,

$\displaystyle D(F,W_{\varepsilon})-D(F,W)$
$\displaystyle=\int_{0}^{1}F(d_{W_{\varepsilon}}(x))~{}dx-\int_{0}^{1}F(d_{W}(x))~{}dx$
$\displaystyle=\sum_{j=1}^{k}\alpha_{j}(F(d_{j}^{\prime})-F(d_{j}))$
$\displaystyle=\alpha_{s}(F(d_{s}+\alpha_{i}\alpha_{r}\varepsilon)-F(d_{s}))+\alpha_{r}(F(d_{r}-\alpha_{i}\alpha_{s}\varepsilon)-F(d_{r}))$
$\displaystyle\geq\alpha_{i}\alpha_{r}\alpha_{s}\varepsilon(F^{\prime}(d_{s})-F^{\prime}(d_{r}))\geq
0$

by convexity of $F$ and $d_{s}\geq d_{r}$. Since $F$ is $\delta$-bad for $W$,
we obtain

$D(F,W_{\varepsilon})\geq D(F,W)\geq\operatorname{MAX}(\gamma,F)+\delta.$

This shows that $F$ is $\delta$-bad for $W_{\varepsilon}$ and completes the
proof of the claim. ∎

######  Claim 3.7 (corresponds to [13, Claim 3.9]).

$\beta_{1k}>0$.

###### Proof.

If this does not hold, then $\beta_{1k}=0$ and the previous claim implies
$\beta_{1i}=0$ for all $i\in[k-1]$. It follows that there exists
$W^{\prime}\in\mathcal{G}_{k-1}$ such that $W$ is isomorphic to
$[\alpha_{1},W^{\prime}]$. Due to the minimality of $k$ all functions in
$\mathscr{C}$ are $\delta$-good for $W^{\prime}$ and by Lemma 3.3 the same
applies to the graphon $W$, contrary to its choice. ∎

######  Claim 3.8 (corresponds to [13, Claim 3.10]).

$\beta_{1k}<1$.

###### Proof.

Suppose for contradiction that $\beta_{1k}=1$. Then $\beta_{k1}=\beta_{1k}>0$,
and Claim 3.6 implies $\beta_{ki}=1$ for all $1\leq i\leq k$. So some
$W^{\prime}\in\mathcal{G}_{k-1}$ has the property that
$[W^{\prime},\alpha_{k}]$ is isomorphic to $W$. This implies that all
functions in $\mathscr{C}$ are $\delta$-good for $W^{\prime}$ and then Lemma
3.4 implies that all functions in $\mathscr{C}$ are $\delta$-good for $W$,
contradiction. ∎

By Claims 3.7 and 3.8, we have $0<\beta_{1k}<1$. Moreover, by Claim 3.6,
$\beta_{1i}=0$ for all $i\in[k-1]$ and $\beta_{jk}=1$ for all $j$ with $2\leq
j\leq k$. Divide $P_{k}$ into two measurable subsets $Q_{k}$ and $Q_{k+1}$
satisfying $\mu(Q_{k})=(1-\beta_{1k})\alpha_{k}$ and, consequently,
$\mu(Q_{k+1})=\beta_{1k}\alpha_{k}$. Set $Q_{i}=P_{i}$ for $i\in[k-1]$ and
$\mathcal{Q}=\\{Q_{1},\ldots,Q_{k+1}\\}$. Let $W^{\prime}$ be the step graphon
with respect to $\mathcal{Q}$ defined as follows: for $x\in Q_{i}$ and $y\in
Q_{j}$,

$W^{\prime}(x,y)=\begin{cases}\beta_{ij}&\text{ if $2\leq i\leq k$ and $2\leq
j\leq k$,}\\\ 0&\text{ if $i=1$ and $j\in[k]$ or vice versa,}\\\ 1&\text{ if
$i=k+1$ or $j=k+1$.}\end{cases}$

By the last two clauses $W^{\prime}$ is isomorphic to a graphon of the form
$[[\alpha_{1}/(1-\beta_{1k}\alpha_{k}),W^{\prime\prime}],\beta_{1k}\alpha_{k}]$
for some graphon $W^{\prime\prime}$, and by the first clause
$W^{\prime\prime}\in\mathcal{G}_{k-1}$. So Lemma 3.3 and Lemma 3.4 show that
$F$ is $\delta$-good for $W^{\prime}$. Since
$t(|,W^{\prime})=t(|,W^{\prime})=\gamma$, Jensen’s inequality implies that

$D(F,W)=\sum_{i=1}^{k}\alpha_{i}F(d_{i})\leq\sum_{i=1}^{k-1}\alpha_{i}F(d_{i})+\alpha_{k}((1-\beta_{1k})F(d^{\prime})+\beta_{1k}F(d^{\prime\prime}))=D(F,W^{\prime})$

for some real numbers $d^{\prime}$ and $d^{\prime\prime}$ satisfying
$(1-\beta_{1k})d^{\prime}+\beta_{1k}d^{\prime\prime}=d_{k}$. Therefore,
$D(F,W)\leq D(F,W^{\prime})<\operatorname{MAX}(\gamma,F)+\delta$ so $F$ is
$\delta$-good for $W$, a contradiction. ∎

The proof of Theorem 2.1 follows from Proposition 3.1 exactly as in [13].

The error in [13] is in the proof of Claim 3.6. In [13], $T$ is defined as the
number of pairs $(i,j)\in[k]^{2}$ for which $\beta_{ij}\in\\{0,1\\}$ and
$W\in\mathcal{G}_{k}$ is chosen to maximize $T$. Then Claim 3.8 in [13] states
that $\beta_{ir}>0$ and $\beta_{is}<1$ together imply that $W_{\varepsilon}$
is $0$ or $1$ on at least $T+1$ of the sets $P_{i}\times P_{j}$ by
construction. However, this is not true if $\beta_{ir}=1$ and $\beta_{is}=0$.
For example, consider the graphon $W$ defined on the partition
$P_{1}=[0,2/5),P_{2}=[2/5,4/5),P_{3}=[4/5,1]$ by

$W(x,y)=\begin{cases}1&\text{ if }(x,y)\in(P_{1}\times P_{3})\cup(P_{2}\times
P_{2})\cup(P_{2}\times P_{3})\\\ 0&\text{ if }(x,y)\in(P_{1}\times
P_{1})\cup(P_{1}\times P_{2})\cup(P_{3}\times P_{3})\end{cases}$

(see Figure 4). We see that $d_{1}=1/5$, $d_{2}=3/5$, and $d_{3}=4/5$, so
$d_{1}\leq d_{2}\leq d_{3}$ is satisfied. Setting $i=3$, $r=2$, and $s=3$, we
have that $\beta_{ir}=1>0$ and $\beta_{is}=0<1$. However, all entries are
already $0$ or $1$ in $W$, so $W_{\varepsilon}$ cannot equal $0$ or $1$ on
more sets than $W$. Note that any step graphon with parts ordered by degree
such that $\beta_{ir}=1$ and $\beta_{is}=0$ for some $i$ and $r<s$ is also a
counterexample; the other entries need not equal $0$ or $1$ as in this
example.

Figure 4: A counterexample to [13], Claim 3.8 (shaded squares have $\beta$
value 1).

##  4 Proof of Theorem 2.3

Recall that we are assuming $G=([n],E)$. For a vertex $i$ in $G$, the right-
degree of $i$ is $d^{+}_{G}(i):=|\\{j>i:ij\in E\\}|$. Recall that when we
write $uv$ for an edge, we implicitly mean $u<v$. The left vertex of $vw\in E$
is $v$. A vertex $v$ has full right-degree if $E\supset\\{vw:w>v\\}$. Note
that $N_{\operatorname{ord}}(S_{L}(k),G)=\sum_{i\in
V(G)}\binom{d_{G}^{+}(i)}{k}.$

###### Proof of Theorem 2.3.

If $m=0$, the theorem is trivial, so we assume that $m>0$.

Let $G=([n],E)$ with $|E|=m>0$ such that $G$ maximizes the number of copies of
$S_{L}(k)$ among all ordered $n$ vertex $m$ edge graphs. Suppose that there
exists $i\in[n]$ such that $d^{+}_{G}(i)<d^{+}_{G}(i+1)$. Let $G_{i}$ be the
ordered graph obtained from $G$ by interchanging the positions of $i$ and
$i+1$ in the ordering of $V(G)$. We say that $G_{i}$ is obtained from $G$ by
swapping $i$ and $i+1$.

Since $i$ and $i+1$ are consecutive in the ordering of $G$, we have that
$d_{G}^{+}(j)=d_{G_{i}}^{+}(j)$ for all $j\in[n]\setminus\\{i,i+1\\}$. If
there is no edge between $i$ and $i+1$, then $d_{G}^{+}(i)=d_{G_{i}}^{+}(i)$
and $d_{G}^{+}(i+1)=d_{G_{i}}^{+}(i+1)$ as well, so
$N(S_{L}(k),G_{i})=N(S_{L}(k),G)$. If there is an edge between $i$ and $i+1$,
then $d_{G_{i}}^{+}(i)=d_{G}^{+}(i)-1$ and
$d_{G_{i}}^{+}(i+1)=d_{G}^{+}(i+1)+1$. By convexity of the binomial
coefficient and the fact that $d_{G}^{+}(i)<d_{G}^{+}(i+1)$,

$\displaystyle N_{\operatorname{ord}}(S_{L}(k),G_{i})~{}-$
$\displaystyle~{}N_{\operatorname{ord}}(S_{L}(k),G)=\sum_{j\in
V(G_{i})}\binom{d_{G_{i}}^{+}(j)}{k}-\sum_{j\in V(G)}\binom{d_{G}^{+}(j)}{k}$
$\displaystyle=\mathopen{}\mathclose{{}\left(\binom{d_{G_{i}}^{+}(i)}{k}+\binom{d_{G_{i}}^{+}(i+1)}{k}}\right)-\mathopen{}\mathclose{{}\left(\binom{d_{G}^{+}(i)}{k}+\binom{d_{G}^{+}(i+1)}{k}}\right)$
$\displaystyle=\mathopen{}\mathclose{{}\left(\binom{d_{G}^{+}(i)-1}{k}+\binom{d_{G}^{+}(i+1)+1}{k}}\right)-\mathopen{}\mathclose{{}\left(\binom{d_{G}^{+}(i)}{k}+\binom{d_{G}^{+}(i+1)}{k}}\right)>0.$

This contradicts our choice of $G$, so there is no $i\in[n]$ such that
$d_{G}^{+}(i)<d_{G}^{+}(i+1)$ and $\\{i,i+1\\}\in E$. We repeatedly swap
consecutive pairs of vertices $v<w$ if the right degree of $v$ is less than
the right degree of $w$ in the current graph until no such pairs $v,w$ exist.
Call the resulting graph $G^{\prime}$. Then $d^{+}_{G^{\prime}}(v)\geq
d^{+}_{G^{\prime}}(w)$ for all $v<w$ and
$N_{\operatorname{ord}}(S_{L}(k),G^{\prime})=N_{\operatorname{ord}}(S_{L}(k),G)$.

Let $v:=\min\\{i\in[n]:d_{G^{\prime}}^{+}(i)<n-i\\}$ and choose $w\in[n]$ such
that $vw\not\in E(G^{\prime})$. Let
$x:=\max\\{i\in[n]:d^{+}_{G^{\prime}}(i)>0\\}$. We will show that $v=x$ or
$x+1$. Note that if $v=1$, then $x\geq 1=v$; if $v\geq 2$, then the choice of
$v$ implies that $d^{+}_{G^{\prime}}(v-1)=n-v+1>0$, so $x\geq v-1$. Thus
$v\leq x+1$ and it remains to show that $v\geq x$. Fix $y\in[n]$ such that
$xy\in E(G^{\prime})$.

Suppose, for contradiction, that $v<x$. Let $H=([n],E(G^{\prime})\cup
vw\setminus xy)$. Then $d^{+}_{H}(v)=d^{+}_{G^{\prime}}(v)+1$ and
$d^{+}_{H}(x)=d^{+}_{G^{\prime}}(x)-1$. By convexity of the binomial
coefficient and the fact that $d_{G^{\prime}}^{+}(v)\geq
d_{G^{\prime}}^{+}(x)$,

$N_{\operatorname{ord}}(S_{L}(k),H)>N_{\operatorname{ord}}(S_{L}(k),G^{\prime})=N_{\operatorname{ord}}(S_{L}(k),G).$

This contradicts our choice of $G$, so it must be the case that $v=x$ or
$x+1$. This means that

$E(G^{\prime})=\\{ij:i\in[v-1],j\in[n]\\}\cup A$

for some $A\subset\\{vj:j\in\\{v+1,v+2,\ldots,n\\}\\}$ with $|A|=b$ for some
$0\leq b<n-v$. Since $d^{+}_{G^{\prime}}(v)=b$ and $d^{+}_{G^{\prime}}(w)=0$
for $w>v$,

$N_{\operatorname{ord}}(S_{L}(k),G)=N_{\operatorname{ord}}(S_{L}(k),G^{\prime})=N_{\operatorname{ord}}(S_{L}(k),S_{L}(n,m))$

as required.

Let $G=([n],E)$ with $|E|=m$ such that $G$ minimizes the number of copies of
$S_{L}(k)$ among all ordered $n$ vertex $m$ edge graphs. Suppose further that
there are some $i,j\in V(G)$ with $i<j$ such that $d^{+}_{G}(j)<n-j$ and
$d^{+}_{G}(i)>d^{+}_{G}(j)$. Then choose $v\in[n]$ such that $j<v$ and
$jv\notin E$. As $d^{+}_{G}(i)>d^{+}_{G}(j)\geq 0$, we also choose $w\in[n]$
such that $i<w$ and $iw\in E$. Let $H=([n],E\cup jv\setminus iw)$. Then
$d^{+}_{H}(i)=d^{+}_{G}(i)-1$ and $d^{+}_{H}(j)=d^{+}_{G}(j)+1$. By convexity
of the binomial coefficient,

$N_{\operatorname{ord}}(S_{L}(k),H)\leq N_{\operatorname{ord}}(S_{L}(k),G),$

where equality holds exactly when $d_{G}^{+}(i)=d_{G}^{+}(j)+1$. By our
assumption on $G$, we must have
$N_{\operatorname{ord}}(S_{L}(k),H)=N_{\operatorname{ord}}(S_{L}(k),G)$. We
repeatedly remove an edge $xu$ and add an edge $yz$ for $x<y$ satisfying
$d^{+}(y)<n-y$ and $d^{+}(x)>d^{+}(x)$ until no such pairs $x,y$ exist. Call
the resulting graph $G^{\prime}$ and note that $G^{\prime}$ has $m$ edges.
Then
$N_{\operatorname{ord}}(S_{L}(k),G^{\prime})=N_{\operatorname{ord}}(S_{L}(k),G)$
and

$\text{for all $i<j$ in $G^{\prime}$, either $d^{+}_{G^{\prime}}(j)=n-j$ or
$d^{+}_{G^{\prime}}(i)\leq d^{+}_{G^{\prime}}(j)$}\qquad(*).$

We note here that the right degree sequence of $S_{R}(n,m)$ is given by

$0,1,\ldots,a-1,\underbrace{a,\ldots,a}_{n-a-b},\underbrace{a+1,\ldots,a+1}_{b}.$
(1)

Our plan is to show that the right degree sequence of $G^{\prime}$ is the same
as (1). This will allow us to conclude that
$N_{\operatorname{ord}}(S_{L}(k),G^{\prime})=N_{\operatorname{ord}}(S_{L}(k),S_{R}(n,m))$.

Set $v:=\min\\{j\in[n]:d^{+}_{G^{\prime}}(j)=n-j\\}$. Then
$d^{+}_{G^{\prime}}(i)\leq d^{+}_{G^{\prime}}(j)$ for all $i<j\leq v-1$ by
$(*)$. Furthermore, if there exists $i\geq v$ such that
$d^{+}_{G^{\prime}}(i)<n-i$, then we can find consecutive vertices $x,y$ such
that $v\leq x<y$, $d^{+}_{G^{\prime}}(y)<n-y$ and $d^{+}_{G^{\prime}}(x)=n-x$.
But this is impossible as ($*$) implies that $d^{+}_{G^{\prime}}(y)\geq
d^{+}_{G^{\prime}}(x)=n-x>n-y$. Consequently, $d^{+}_{G^{\prime}}(i)=n-i$ for
all $i\in\\{v,v+1,\ldots,n\\}$.

If $v=n$, then $d^{+}_{G^{\prime}}(n-1)=0$ and $d^{+}_{G^{\prime}}(i)\leq
d^{+}_{G^{\prime}}(n-1)=0$ for all $i\in[n-1]$, so $|E(G^{\prime})|=0$. This
contradicts $m>0$, so we must have $v<n$. If $d^{+}_{G^{\prime}}(i)\geq n-v+1$
for some $i\in[v-1]$, then since $i\leq v-1$, we have
$d^{+}_{G^{\prime}}(v-1)\geq d^{+}_{G^{\prime}}(i)\geq n-v+1=n-(v-1)$. This
implies that $d^{+}_{G^{\prime}}(v-1)=n-(v-1)$, contradicting the choice of
$v$. Therefore $v<n$ and $d^{+}_{G^{\prime}}(i)\leq n-v$ for all $i\in[v-1]$.

Next, suppose that $d^{+}_{G^{\prime}}(1)<n-v-1$. Note that
$d^{+}_{G^{\prime}}(v)=n-v>n-v-1>d^{+}_{G^{\prime}}(1)$ implies that
$d^{+}_{G^{\prime}}(v)\geq d^{+}_{G^{\prime}}(1)+2$. Choose
$x\in[n]\setminus\\{1\\}$ such that $1x\notin E(G^{\prime})$ and
$y\in\\{v+1,\ldots,n\\}$ such that $vy\in E(G^{\prime})$. Let
$H^{\prime}=([n],E(G^{\prime})\cup 1x\setminus vy)$. Then
$d^{+}_{H^{\prime}}(1)=d^{+}_{G^{\prime}}(1)-1$ and
$d^{+}_{H^{\prime}}(v)=d^{+}_{G^{\prime}}(v)+1$. By convexity of binomial
coefficients and the fact that $d^{+}_{G^{\prime}}(v)\geq
d^{+}_{G^{\prime}}(1)+2$,

$N_{\operatorname{ord}}(S_{L}(k),H^{\prime})<N_{\operatorname{ord}}(S_{L}(k),G^{\prime})=N_{\operatorname{ord}}(S_{L}(k),G).$

This contradicts the choice of $G$, so $n-v-1\leq d^{+}_{G^{\prime}}(1)\leq
n-v$.

Since the right-degrees of vertices $x$ are nondecreasing for $1\leq x\leq v$,
there is some $0<b_{0}\leq v$ such that $d^{+}_{G^{\prime}}(i)=n-v-1$ for all
$i\in[v-b_{0}]$, $d^{+}_{G^{\prime}}(i)=n-v$ for the remaining $b_{0}$
vertices $v-b+1\leq i\leq v$; we have already observed that
$d^{+}_{G^{\prime}}(i)=n-i$ for all $i>v$. Thus the right degree sequence of
$G^{\prime}$ is given by

$0,1,\ldots,n-v-2,\underbrace{n-v-1,\ldots,n-v-1}_{v+1-b_{0}},\underbrace{n-v,\ldots,n-v}_{b_{0}}.$
(2)

If $b_{0}=v$, set $b=0$ and $a=n-v$. Otherwise, set $b=b_{0}$ and $a=n-v-1$.
In either case, the degree sequence of $S_{R}(n,m)$ in (1) is the same as that
of $G^{\prime}$ in (2) and therefore

$N_{\operatorname{ord}}(S_{L}(k),G)=N_{\operatorname{ord}}(S_{L}(k),G^{\prime})=N_{\operatorname{ord}}(S_{L}(k),S_{R}(n,m))$

as required. ∎

##  5 Proof of Theorem 2.7

Let $(G_{n})_{n=1}^{\infty}$ be a sequence of graphs with
$\lim_{n\to\infty}|V(G_{n})|=\infty$. The sequence $(G_{n})_{n=1}^{\infty}$ is
$F$-good if both $x=\lim_{n\to\infty}\varrho(G_{n})$ and
$y=\lim_{n\to\infty}\varrho_{\operatorname{ind}}(F,G_{n})$ exist. In this
case, we say that $(G_{n})_{n=1}^{\infty}$ realizes $(x,y)$. Define

$I_{{\operatorname{ind}}}(F,x):=\sup\\{y:(x,y)\in[0,1]\text{ is realized by
some $F$-good }(G_{n})_{n=1}^{\infty}\\}.$

The following two results will be needed to give upper bounds.

######  Theorem 5.1 (Kruskal-Katona [5, 6]).

Let $r\geq 2$ be an integer. Then for every $x\in[0,1]$ we have
$I_{\operatorname{ind}}(K_{r},x)\leq x^{r/2}$.

######  Theorem 5.2 (Liu, Mubayi, Reiher [7]).

Let $s\geq 2$ be an integer. Then for every $x\in[0,1]$ we have
$I_{\operatorname{ind}}(K_{s,s},x)\leq\binom{2s}{s}x^{s}/2^{s}$.

###### Proof of Theorem 2.7.

We address the two cases separately.

Case 1: $\sqrt{x_{b}}+\sqrt{x_{g}}\leq 1$.

We first prove the upper bound. Suppose that $(G_{n})_{n=1}^{\infty}$ be a
$K_{s,t}^{\prime}$-good sequence that realizes
$((x_{b},x_{g}),I_{3}(K_{s,t}^{\prime},(x_{b},x_{g})))$ and let $f_{n}$ be the
coloring function for $G_{n}$. Let $K_{s}^{\prime}=([s],\binom{s}{2})$ with
coloring function $f_{b}\equiv\text{blue}$. Similarly, let
$K_{t}^{\prime}=([t],\binom{t}{2})$ have coloring function
$f_{g}\equiv\text{green}$. Since $K_{s,t}^{\prime}$ contains exactly one copy
of $K_{s}^{\prime}$ and one copy of $K_{t}^{\prime}$,

$N_{3}(K_{s,t}^{\prime},G_{n})\leq
N_{3}(K_{s}^{\prime},G_{n})N_{3}(K_{t}^{\prime},G_{n}).$ (3)

By deleting edges that are not colored blue and applying Theorem 5.1, we
obtain

$\lim_{n\to\infty}\frac{N_{3}(K_{s}^{\prime},G_{n})}{\binom{|V(G_{n})|}{s}}\leq
I_{3}(K_{s}^{\prime},(x_{b},x_{g}))\leq
I_{\operatorname{ind}}(K_{s},x_{b})\leq x_{b}^{s/2}.$

Similarly, by deleting edges not colored green, we obtain

$\lim_{n\to\infty}\frac{N_{3}(K_{t}^{\prime},G_{n})}{\binom{|V(G_{n})|}{t}}\leq
I_{3}(K_{t}^{\prime},(x_{b},x_{g}))\leq
I_{\operatorname{ind}}(K_{t},x_{g})\leq x_{g}^{t/2}.$

Together with (3), we get

$I_{3}(K_{s,t}^{\prime},(x_{b},x_{g}))\leq\lim_{n\to\infty}\frac{x_{b}^{s/2}\binom{|V(G_{n})|}{s}\cdot
x_{g}^{t/2}\binom{|V(G_{n})|}{t}}{\binom{|V(G_{n})|}{s+t}}=x_{b}^{s/2}x_{g}^{t/2}\binom{s+t}{s}.$

We now prove the lower bound. As $\lfloor n\sqrt{x_{b}}\rfloor+\lfloor
n\sqrt{x_{g}}\rfloor\leq n\sqrt{x_{b}}+n\sqrt{x_{g}}\leq n,$ there exist
disjoint subsets $A_{n}$ and $B_{n}$ of $[n]$ with $|A_{n}|=\lfloor
n\sqrt{x_{b}}\rfloor$ and $|B_{n}|=\lfloor n\sqrt{x_{g}}\rfloor$ for all $n$.
For each $n\geq 1$, let $G_{n}=([n],\binom{[n]}{2})$ have coloring function
$f_{n}$ defined by

$f_{n}(ij)=\begin{cases}\text{blue}&\text{ if }i,j\in A_{n},\\\
\text{green}&\text{ if }i,j\in B_{n},\\\ \text{red}&\text{
otherwise.}\end{cases}$

Figure 5: Construction maximizing $K_{s,t}^{\prime}$-density when
$\sqrt{x_{b}}+\sqrt{x_{g}}\leq 1$.

Clearly, $\lim_{n\to\infty}\varrho_{\text{blue}}(G_{n})=x_{b}$ and
$\lim_{n\to\infty}\varrho_{\text{green}}(G_{n})=x_{g}$. If $A$ is a copy of
$K_{s}^{\prime}$ in $G_{n}$ and $B$ is a copy of $K_{t}^{\prime}$ in $G_{n}$,
then $A\cup B$ is a copy of $K_{s,t}^{\prime}$ in $G_{n}$, as
$f_{n}(ij)=\text{red}$ for all $i\in A_{n}$, $j\in B_{n}$. Thus,
$(G_{n})_{n=1}^{\infty}$ realizes $(x_{b},x_{g},y)$ where

$y=\lim_{n\to\infty}\varrho_{3}(K_{s,t}^{\prime},G_{n})=\lim_{n\to\infty}\frac{\binom{\lfloor
n\sqrt{x_{b}}\rfloor}{s}\cdot\binom{\lfloor
n\sqrt{x_{g}}\rfloor}{t}}{\binom{n}{s+t}}=\lim_{n\to\infty}\frac{(s+t)!n^{s}x_{b}^{s/2}n^{t}x_{g}^{t/2}}{n^{s+t}s!t!}=x_{b}^{s/2}x_{g}^{t/2}\binom{s+t}{s}.$

Consequently, $I_{3}(K_{s,t}^{\prime},(x_{b},x_{g}))\geq
x_{b}^{s/2}x_{g}^{t/2}\binom{s+t}{s}$.

Case 2: $\sqrt{x_{b}}+\sqrt{x_{g}}>1$.

We first prove the upper bound. Set $x_{r}:=1-x_{b}-x_{g}$. Let
$(G_{n})_{n=1}^{\infty}$ be a $K_{s,s}^{\prime}$-good sequence that realizes
$((x_{b},x_{g}),I_{3}(K_{s,s}^{\prime},(x_{b},x_{g})))$. Every copy of
$K_{s,s}^{\prime}$ contains a red copy of $K_{s,s}$. Consequently, Theorem 5.2
implies that

$I_{3}(K_{s,s}^{\prime},(x_{b},x_{g}))=\lim_{n\to\infty}\frac{N_{3}(K_{s,s}^{\prime},G_{n})}{\binom{|V(G_{n})|}{2s}}\leq
I_{\operatorname{ind}}(K_{s,s},x_{r})\leq\mathopen{}\mathclose{{}\left(\frac{x_{r}}{2}}\right)^{s}\binom{2s}{s}.$

We now prove the lower bound. Note that

$\lfloor n\sqrt{x_{b}}\rfloor+\mathopen{}\mathclose{{}\left\lfloor
n\frac{x_{r}}{2\sqrt{x_{b}}}}\right\rfloor\leq\frac{2x_{b}+x_{r}}{2\sqrt{x_{b}}}n=\frac{1+x_{b}-x_{g}}{2\sqrt{x_{b}}}n<\frac{2\sqrt{x_{b}}}{2\sqrt{x_{b}}}n=n$

since $\sqrt{x_{b}}+\sqrt{x_{g}}>1$ implies $x_{g}>1-2\sqrt{x_{b}}+x_{b}$. For
each $n$, let $A_{n}\sqcup B_{n}\subseteq[n]$ where $|A_{n}|=\lfloor
n\sqrt{x_{b}}\rfloor$ and $|B_{n}|=\lfloor nx_{r}/(2\sqrt{x_{b}})\rfloor$ and
let $G_{n}=([n],\binom{[n]}{2})$ have coloring function $f_{n}$ defined by

$f_{n}(ij)=\begin{cases}\text{blue}&\text{ if }i,j\in A_{n},\\\
\text{red}&\text{ if }i\in A_{n},j\in B_{n}\text{ or }j\in A_{n},i\in
B_{n},\\\ \text{green}&\text{ otherwise.}\end{cases}$

Figure 6: Construction maximizing $K_{s,s}^{\prime}$-density when
$\sqrt{x_{b}}+\sqrt{x_{g}}>1$.

Now $\lim_{n\to\infty}\varrho_{\text{blue}}(G_{n})=x_{b}$, and

$\lim_{n\to\infty}\varrho_{\text{red}}(G_{n})=\lim_{n\to\infty}\frac{\lfloor
n\sqrt{x_{b}}\rfloor\cdot\lfloor
nx_{r}/2\sqrt{x_{b}}\rfloor}{\binom{n}{2}}=\frac{2x_{r}\sqrt{x_{b}}}{2\sqrt{x_{b}}}=x_{r}.$

We conclude that
$\lim_{n\to\infty}\varrho_{\text{green}}(G_{n})=1-x_{b}-x_{r}=x_{g}$. Every
pair of $s$ vertices in $A_{n}$ and $s$ vertices in $B_{n}$ induces a copy of
$K_{s,s}^{\prime}$, so $(G_{n})_{n=1}^{\infty}$ realizes $(x_{b},x_{g},y)$
where

$y=\lim_{n\to\infty}\frac{\binom{\lfloor
n\sqrt{x_{b}}\rfloor}{s}\cdot\binom{\lfloor
nx_{r}/2\sqrt{x_{b}}\rfloor}{s}}{\binom{n}{2s}}=\lim_{n\to\infty}\frac{n^{s}x_{b}^{s/2}n^{s}x_{r}^{s}x_{b}^{-s/2}}{n^{2s}2^{s}}\cdot\binom{2s}{s}=\mathopen{}\mathclose{{}\left(\frac{x_{r}}{2}}\right)^{s}\binom{2s}{s}.$

Consequently,
$I_{3}(F,(x_{b},x_{g}))\geq\mathopen{}\mathclose{{}\left(\frac{x_{r}}{2}}\right)^{s}\binom{2s}{s}$.
∎

## References

  * [1] R. Ahlswede, G. O. H. Katona, Graphs with maximal number of adjacent pairs of edges, Acta Math. Acad. Sci. Hungar. 32 (1978), no. 1-2, 97–120.
  * [2] P. Erdös, A. Hajnal, On Ramsey Like Theorems, Problems and Results, Combinatorica 7 (1972), 123–136.
  * [3] H. Huang, On the maximum induced density of directed stars and related problems, SIAM J. Discrete Math. 28 (2014), no. 1, 92–98.
  * [4] P. Hu, J. Ma, S. Norin, H. Wu, The inducibility of oriented stars, available at arXiv:2008.05430 (2020).
  * [5] G. Katona, A theorem of finite sets, Theory of graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York (1968), 187–207.
  * [6] J. B. Kruskal, The number of simplices in a complex, Mathematical optimization techniques, UNiv. of California Press, Berkeley, Calif. (1963), 251–278.
  * [7] X. Liu, D. Mubayi, C. Reiher, The feasible region of induced graphs, J. Combin. Theory Ser. B 158 (2023), 105–135.
  * [8] L. Lovász, Large Networks and Graph Limits, American Mathematical Society Colloquium Presentations  60 (2012).
  * [9] L. Lovász, M. Simonovits, On the number of complete subgraphs of a graph II Birkhäuser Verlag, (1983), 459–495.
  * [10] V. Nikiforov, The number of cliques in graphs of given order and size, Trans. Amer. Math. Soc. 363 (2011), no. 3, 1599–1618.
  * [11] A. A. Razborov, On the minimal density of triangles in graphs, Combin. Probab. Comput. 17 (2008), no. 4, 603–618.
  * [12] C. Reiher, The clique density theorem, Ann. of Math. 184 (2016), no. 3, 683–707.
  * [13] C. Reiher, S. Wagner, Maximum star densities, Studia Sci. Math. Hungar. 55 (2017), no. 2, 238–259.
  * [14] Y. Zhao, Hypergraph Limits: A Regularity Approach, Random Structures Algorithms 47 (2015), 205–226.

## Appendix

###### Proof of Lemma 3.2.

Let $F\in\mathscr{C}$ be the function that we want to prove $\delta$-good for
$1-W$. Using the fact that $G:[0,1]\to\mathbb{R}$ given by $x\mapsto F(1-x)$
from [13, Lemma 3.1(ii)] is $\delta$-good for $W$ we find that

$\gamma=t(|,1-W)=1-t(|,W)\text{ and }\eta=1-\sqrt{1-\gamma}$

satisfy

$\displaystyle\int_{0}^{1}$ $\displaystyle
F(d_{1-W}(x))=\int_{0}^{1}G(d_{W}(x))$
$\displaystyle<\max\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(1-\sqrt{1-\gamma}}\right)G(0)+\sqrt{1-\gamma}G\mathopen{}\mathclose{{}\left(\sqrt{1-\gamma}}\right),~{}\sqrt{\gamma}G(1-\sqrt{\gamma})+(1-\sqrt{\gamma})G(1)}\right\\}+\delta$
$\displaystyle=\max\\{(1-\eta)F(\eta)+\eta
F(1),~{}(1-\sqrt{\gamma})F(0)+\sqrt{\gamma}F(\sqrt{\gamma})\\}+\delta$

as desired. ∎

###### Proof of Lemma 3.3.

Let $F\in\mathscr{C}$ be any function that we want to prove $\delta$-good for
$[\lambda,W]$. By [13, Lemma 3.1(iii)], the function $H:[0,1]\to\mathbb{R}$
given by $H(x)=F((1-\lambda))$ for all $x\in[0,1]$ is in $\mathscr{C}$. Thus
it is $\delta$-good for $W$, which tells us that

$\int_{0}^{1}H(d_{W}(x))~{}dx<\max\\{(1-\sqrt{\gamma})H(0)+\sqrt{\gamma}H(\sqrt{\gamma}),(1-\eta)H(\eta)+\eta
H(1)\\}+\delta,$

where $\gamma=t(|,W)$ and $\eta=1-\sqrt{1-\gamma}$. Since

$\displaystyle\int_{0}^{1}F(d_{[\lambda,W]}(x))~{}dx$ $\displaystyle=\lambda
F(0)+\int_{\lambda}^{1}F\mathopen{}\mathclose{{}\left((1-\lambda)d_{W}\mathopen{}\mathclose{{}\left(\frac{x-\lambda}{1-\lambda}}\right)}\right)~{}dx$
$\displaystyle=\lambda F(0)+(1-\lambda)\int_{0}^{1}H(d_{W}(x))~{}dx,$

it follows that either

$\displaystyle\int_{0}^{1}F(d_{[\lambda,W]}(x))~{}dx$ $\displaystyle<\lambda
F(0)+(1-\lambda)((1-\sqrt{\gamma})F(0)+\sqrt{\gamma}F((1-\lambda)\sqrt{\gamma})+\delta)$
$\displaystyle=\lambda
F(0)+(1-\lambda)(1-\sqrt{\gamma})F(0)+(1-\lambda)\sqrt{\gamma}F((1-\lambda)\sqrt{\gamma})+(1-\lambda)\delta$
$\displaystyle\leq\lambda
F(0)+(1-\lambda)(1-\sqrt{\gamma})F(0)+(1-\lambda)\sqrt{\gamma}F((1-\lambda)\sqrt{\gamma})+\delta,$

or

$\displaystyle\int_{0}^{1}F(d_{[\lambda,W]}(x))~{}dx$ $\displaystyle<\lambda
F(0)+(1-\lambda)((1-\eta)F((1-\lambda)\eta)+\eta F(1-\lambda)+\delta)$
$\displaystyle=\lambda
F(0)+(1-\lambda)(1-\eta)F((1-\lambda)\eta)+(1-\lambda)\eta
F(1-\lambda)+(1-\lambda)\delta$ $\displaystyle\leq\lambda
F(0)+(1-\lambda)(1-\eta)F((1-\lambda)\eta)+(1-\lambda)\eta
F(1-\lambda)+\delta.$

In the former case the right side simplifies to

$\mathopen{}\mathclose{{}\left(1-\sqrt{\gamma^{\prime}}}\right)F(0)+\sqrt{\gamma^{\prime}}F\mathopen{}\mathclose{{}\left(\sqrt{\gamma^{\prime}}}\right)+\delta,$

where $\gamma^{\prime}=(1-\lambda)^{2}\gamma=t(|,[\lambda,W])$, meaning that
$F$ is, in particular, $\delta$-good for $[\lambda,W]$.

So we may assume that the second alternative occurs. Setting $x=\lambda$,
$y=(1-\lambda)\eta$, and $z=(1-\lambda)(1-\eta)$ we thus get

$\int_{0}^{1}F(d_{[\lambda,W]}(x))~{}dx<xF(0)+zF(y)+yF(y+1)+\delta.$

Since
$y^{2}+2yz=(1-\lambda)^{2}(2\eta-\eta^{2})=(1-\lambda)^{2}\gamma=\gamma^{\prime}$,
it follows in view of [13, Lemma 3.3] that

$\int_{0}^{1}F(d_{[\lambda,W]}(x))~{}dx<\max\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(1-\sqrt{\gamma^{\prime}}}\right)F(0)+\sqrt{\gamma^{\prime}}F\mathopen{}\mathclose{{}\left(\sqrt{\gamma^{\prime}}}\right),~{}(1-\eta^{\prime})F(\eta^{\prime})+\eta^{\prime}F(1)}\right\\}+\delta,$

where $\eta^{\prime}=1-\sqrt{1-\gamma^{\prime}}$. This tells us that $F$ is
indeed $\delta$-good for $[\lambda,W]$. ∎