șs țt

# Distinct degrees and homogeneous sets

Eoin Long School of Mathematics, University of Birmingham, UK. Email:
<EMAIL_ADDRESS>Laurentiu Ploscaru School of Mathematics, University of
Birmingham, UK. Email<EMAIL_ADDRESS>
The second author is grateful for support through an EPSRC DTP studentship.

(13 April 2022)

###### Abstract

In this paper we investigate the extremal relationship between two well-
studied graph parameters: the order of the largest homogeneous set in a graph
$G$ and the maximal number of distinct degrees appearing in an induced
subgraph of $G$, denoted respectively by $\hom(G)$ and $f(G)$.

Our main theorem improves estimates due to several earlier researchers and
shows that if $G$ is an $n$-vertex graph with $\hom(G)\geq n^{1/2}$ then
$f(G)\geq\big{(}{n}/{\hom(G)}\big{)}^{1-o(1)}$. The bound here is sharp up to
the $o(1)$-term, and asymptotically solves a conjecture of Narayanan and
Tomon. In particular, this implies that $\max\\{\hom(G),f(G)\\}\geq
n^{1/2-o(1)}$ for any $n$-vertex graph $G$, which is also sharp.

The above relationship between $\hom(G)$ and $f(G)$ breaks down in the regime
where $\hom(G)<n^{1/2}$. Our second result provides a sharp bound for distinct
degrees in biased random graphs, i.e. on $f\big{(}G(n,p)\big{)}$. We believe
that the behaviour here determines the extremal relationship between $\hom(G)$
and $f(G)$ in this second regime.

Our approach to lower bounding $f(G)$ proceeds via a translation into an
(almost) equivalent probabilistic problem, and it can be shown to be effective
for arbitrary graphs. It may be of independent interest.

##  1 Introduction

The focus of this paper is on the extremal relationship between the order of
the largest homogeneous set in a graph $G$ and the maximal number of distinct
degrees which appear in some induced subgraph of $G$. More precisely, let
$\hom(G)$ denote the _homogeneous number_ of a graph $G$, given by:

$\displaystyle\hom(G)$ $\displaystyle:=\max\big{\\{}|U|:U\subset V(G)\mbox{
with }G[U]\mbox{ a complete or empty graph}\big{\\}}.$

We also let $f(G)$ denote the _distinct degree number of_ $G$, given by:

$\displaystyle f(G)$ $\displaystyle:=\max\big{\\{}k\in{\mathbb{N}}:G[S]\mbox{
has }k\mbox{ distinct degrees for some }S\subset V(G)\big{\\}}.$

These quantities have been well-studied in the literature. Indeed, $\hom(G)$
arises as a key parameter in a variety of settings, including extremal graph
theory, graph Ramsey theory and perfect graph theory (see for example [6],
[18], [11], [29]). On the other hand, a wide range of results aim to study the
possible degree distributions of (induced) subgraphs of a graph, for example
[24], [1], [28], [31], [17], [20], and $f(G)$ arises very naturally in this
context.

Erdős, Faudree and Sós were the first to investigate the relationship between
$\hom(G)$ and $f(G)$, focusing in particular on the Ramsey setting, where
$\hom(G)$ is (essentially) minimal. Recall that Ramsey’s theorem [30], [15]
guarantees that every $n$-vertex graph $G$ satisfies the relation
$\hom(G)=\Omega(\log n)$. Erdős [14] showed, in what is one of the earliest
instances of the probabilistic method [4], that there are $n$-vertex graphs
$G$ with $\hom(G)=\Theta(\log n)$ and so the logarithmic order is sharp here.
However, the existence of all such graphs $G$ has only been demonstrated
indirectly via some random process and it is a major open problem to give
explicit examples of such graphs (see [5], [23]). Motivated by this, a large
body of research has developed concerning the structure of Ramsey graphs [16],
[27], [32], [22], [21],[25], aiming to show that they must behave similarly to
appropriate random graphs.

In this context, Erdős, Faudree and Sós [13] noticed that the random graph
$G(n,1/2)$ has $f(G(n,1/2))=\Omega(n^{1/2})$ with high probability. They
conjectured this property must be shared by Ramsey graphs: if $G$ is an
$n$-vertex graph with $\hom(G)=O(\log n)$ then $f(G)=\Omega(n^{1/2})$. Bukh
and Sudakov confirmed this conjecture in [9] with an elegant and influential
argument. Furthermore, they noted that there still appeared to be some
flexibility here:

  * (a)

Although $f(G(n,1/2))=\Omega(n^{1/2})$ forms a natural lower bound, they
observed that it did not have a matching upper bound, as they proved that
$f(G(n,1/2))=O(n^{2/3})$ whp.

  * (b)

They conjectured that $\hom(G)=n^{o(1)}$ already implies that $f(G)\geq
n^{1/2-o(1)}$.

It was later shown by Conlon, Morris, Samotij and Saxton [10], thus matching
the upper bound given in (a), that in fact $f(G(n,1/2))=\Omega(n^{2/3})$ whp.
Recently, Jenssen, Keevash, Long and Yepremyan [19] proved that the same lower
bound applies in the Ramsey context, giving a tight bound for the original
Ramsey question of Erdős, Faudree and Sós.

In [26], Narayanan and Tomon solved the conjecture from (b) above, proving
that actually $f(G)=\Omega\big{(}(n/\hom(G))^{1/2}\big{)}$ for all $n$-vertex
graphs $G$. They also provided an interesting construction, which suggested a
tight bound between the following parameters: if $k\leq n^{1/2}$ then the
$n$-vertex $k$-partite Turán graph $T$ (see e.g.[6]) satisfies both
$\hom(T)=n/k$ and $f(T)=k$. Narayanan and Tomon conjectured that a similar
dependence must hold in general: if $G$ is an $n$-vertex graph satisfying
$\hom(G)\geq n^{1/2}$ then $f(G)=\Omega(n/\hom(G))$. Supporting their
conjecture, the authors proved that indeed $f(G)=\Omega(n/\hom(G))$ when
$\hom(G)=\Omega(n/\log n)$. Jenssen et al. [19] improved this bound to
$\hom(G)\geq n^{9/10}$, noting that there were significant obstacles to
obtaining $\hom(G)\geq n^{1/2}$.

Our main result here confirms the Narayanan$-$Tomon conjecture up to a
logarithmic loss.

######  Theorem 1.1.

Let $m\geq n^{1/2}$. Then every $n$-vertex graph $G$ with $\hom(G)\leq m$
satisfies:

$f(G)=\Omega\bigg{(}\frac{n/m}{\log^{7/2}(n/m)}\bigg{)}.$

As an immediate corollary of Theorem 1.1 we obtain the following result, which
strengthens the bounds of Bukh and Sudakov [9] and of Narayanan and Tomon
[26].

######  Corollary 1.2.

Every $n$-vertex graph $G$ satisfies $\max\big{\\{}\hom(G),f(G)\big{\\}}\geq
n^{1/2-o(1)}$.

Again, note that the $n^{1/2}$-partite Turán graph on $n$ vertices shows that
this bound is essentially sharp. However, as discussed below, there is a large
and varied collection of graphs which are close to extremal value here.

Our second result focuses on the regime where $\hom(G)<n^{1/2}$. The Turán
construction given above begins to break down here, and in fact the above
relationship between the parameters no longer holds; e.g. by our discussion
above $\hom(G(n,1/2))\cdot f(G(n,1/2))=\Theta(n^{2/3}\log n)\ll n$ whp.
Motivated by this, we prove sharp bounds on $f(G(n,p))$ for general values of
$p$, extending the results of Bukh and Sudakov [9] and of Conlon, Morris,
Samotij and Saxton [10].

######  Theorem 1.3.

Let $n\in{\mathbb{N}}$ and let $p:=p(n)\in[0,1/2]$. Then whp the random graph
$G(n,p)$ satisfies the following:

  * _(i)_

$f\big{(}G(n,p)\big{)}=\Theta\left(\sqrt[3]{pn^{2}}\right)$ for
$p\in[n^{-1/2},1/2]$;

  * _(ii)_

$f\big{(}G(n,p)\big{)}=\Theta\big{(}\Delta(G(n,p))\big{)}$ for $p\leq
n^{-1/2}$.

_Remark._ As $f(G)=f(\overline{G})$ for any graph $G$, we see that $f(G(n,p))$
and $f(G(n,1-p))$ follow identical distributions, so Theorem 1.3 determines
the behaviour of $f(G(n,p))$ for all $p\in[0,1]$.

Together with the known estimates on the homogeneous number of sparse random
graphs, Theorem 1.3 suggests a natural extremal relationship between $\hom(G)$
and $f(G)$ when the hypothesis of Theorem 1.1 fails, i.e. when
$\hom(G)<n^{1/2}$. We further examine this relationship in the concluding
remarks in Section 7.

Our proofs to both Theorem 1.1 and Theorem 1.3 build upon earlier approaches
from [9] and [19], but there are many extra challenges in this regime, which
require several key new ingredients and ideas. For instance, although Turán
graphs represent an example of $n$-vertex graphs $G$ with $\hom(G)=n^{1/2}$
and $f(G)=\Theta(n^{1/2})$, there are several very different looking graphs
which exhibit (essentially) the same behaviour, including the random graph
$G(n,n^{-1/2})$.

One interesting class of examples was given by Narayanan and Tomon, which we
call ‘iterated Turán graphs’: take $b<n^{1/2}$ vertex disjoint sets
$V_{1},\ldots,V_{b}$ of size $n/b$, and on each set $V_{i}$ put a copy of the
complement of the $n^{1/2}$-partite $n/b$-vertex Turán graph, and join all
pairs lying in distinct $V_{i}$ and $V_{j}$ by an edge. It can be checked that
such a graph $G$ has $n$-vertices, that $\hom(G)=n^{1/2}$ and that
$f(G)=n^{1/2}$ (any set $V_{i}$ contains at most $n^{1/2}/b$ vertices with
distinct degrees). Noting that the degree in each such graph is
$n-n/b+n^{1/2}/b$, we see these graphs are non-isomorphic for different values
of $b$, and so there are many distinct extremal situations.

Standing back from this, consider (1) starting with many vertex disjoint
copies of the same graph, (2) complementing the edges of each, and (3) joining
all vertices between different classes by an edge. One can observe that,
starting with the graph on a single point and running these steps we can
obtain a Turán graph (applying the process once), and the iterated Turán graph
(applying it twice). One could furthermore iterate more times, and this leads
to graphs with very limited neighbourhood diversity (see the definition before
Lemma 4.3 below), which was a key parameter in many earlier approaches. One of
our results below (see Theorem 3.2) allows us to prove lower bounds on $f(G)$
by instead lower bounding auxilliary parameters (see Theorem 3.2) and this
connection crucially works without diversity assumptions, unlike in earlier
approaches.

The above process also highlights a more significant challenge, which arises
naturally for this problem. To find a large set $U$ of vertices with distinct
degrees in general, these iterated graphs show that sometimes we _must_ first
find sets $U_{i}$ of distinct degrees locally in smaller graphs and then
combine the results into a larger set $U=\cup U_{i}$. Combining such sets
together can work very well for iterated graphs, but even small changes to the
structure here can break the condition $-$ at an extreme, it could be that the
sets $U_{i}$ have distinct degrees in $G[V_{i}]$ for $i=1,2$ with $V_{1}$ and
$V_{2}$ disjoint, but that all vertices of $U_{1}\cup U_{2}$ have the same
degree when combined in $G[V_{1}\cup V_{2}]$. We avoid this kind of difficulty
by moving to a more general probabilistic setting, where we instead find
probability distributions with certain well-controlled small ball
probabilities.

Lastly, our approach in Sections 3 and 4 is quite applicable to the general
problem of lower bounding $f(G)$ in an arbitrary graph $-$ see Theorem 3.2 and
Lemma 3.4 below.

The paper is organised as follows. In the next section we present a number of
tools which will be required in our proof. In Section 3 we present a
probabilistic analogue of the problem of finding many distinct degrees in a
graph. In Section 4 we extend this approach to a more robust variant and
develop a variety of tools and estimates for studying the distinct degree
problem. In Section 5 we prove Theorem 1.1 as follows: we first deal with a
slightly weaker version in Section 5.1, which applies when $\hom(G)\geq
n^{3/5+o(1)}$, and then build upon this in subsection 5.2 to prove Theorem
1.1. In Section 6 we present the proof of Theorem 1.3. Finally, in Section 7
we conclude with a discussion of the case when $f(G)<n^{1/2}$.

Notation. Given a graph $G$ and $u,v\in V(G)$, we write $u\sim v$ if $u$ and
$v$ are adjacent vertices in $G$ and $u\not\sim v$ if they are not. The
neighbourhood of $u$ is given by $N_{G}(u)=\\{v\in V(G):u\sim v\\}$ and given
$S\subset V(G)$ we let $N^{S}_{G}(u):=N_{G}(u)\cap S$; we will omit the
subscript $G$ when the graph is clear from the context. We write
$d^{S}_{G}(u)=|N^{S}_{G}(u)|$.

Given a vertex $u$, we will also represent the neighbourhood of $u$ by a
vector $\textbf{u}\in\\{0,1\\}^{V(G)}$ defined such that $u_{v}=1$ if and only
if $u\sim v$. Given a set $U\subset V$ and a vector ${\bf
u}\in{\mathbb{R}}^{V}$, we will denote the projection of ${\bf u}$ onto the
coordinate set $S$ by $\operatorname{proj}_{S}({\bf{u}})$, i.e. for any $v\in
S$ we have $\operatorname{proj}_{S}({\bf{u}})_{v}={\bf u}_{v}$. Given $u,v\in
V(G)$ we write $\text{div}_{G}(u,v)$ for the symmetric difference
$N(u)\triangle N(v)$. Thus $|\text{div}_{G}(u,v)|$ is simply the Hamming
distance between ${\bf u}$ and ${\bf v}$.

We will write $\overline{G}$ for the complement of the graph $G$. It is easy
to note that for any graph $G$ we have $\hom(G)=\hom(\overline{G})$ and
$f(G)=f(\overline{G})$ since
$\text{div}_{G}(u,v)=\text{div}_{\overline{G}}(u,v)$ for any $u,v\in V(G)$.

Given $n\in\mathbb{N}$ and $p\in(0,1)$, the Erdős$-$Rényi random graph
$G(n,p)$ is the $n$-vertex graph in which each edge is included in the graph
with probability $p$ independently of every other edge. We say that an event
that depends on $n$ occurs _with high probability_ (whp) if its probability
tends to $1$ as $n\to\infty$.

Throughout this paper we will omit floor and ceiling signs when they are not
crucial, for the sake of clarity of presentation.

##  2 Tools

In this short section we introduce some tools required for the rest of the
paper. We will use the following version of Turán’s theorem (see for example
Chapter 6 in [6]).

######  Theorem 2.1.

Let $G$ be a $n$-vertex graph with average degree $d$. Then $G$ has an
independent set of size at least $n/(d+1)$.

Secondly, we require the following ‘anticoncentration’ theorem for the
Littlewood$-$Offord problem, which is due to Erdős [12]:

######  Theorem 2.2 (Erdős–Littlewood–Offord).

Let $S$ be a set of $n$ real numbers of absolute value at least $1$. Then, for
each $\alpha\in\mathbb{R}$, there are at most $\binom{n}{\lfloor
n/2\rfloor}=\Theta(2^{n}n^{-1/2})$ subsets of $S$ whose sum of elements lie in
the interval $[\alpha,\alpha+1)$.

We now give a probabilistic interpretation of the previous theorem, which can
also be found in [19]. For the sake of completeness, we include a proof of
this result.

######  Theorem 2.3.

Fix non-zero parameters $a_{1},a_{2},\dots,a_{n}\in\mathbb{R}$ and
$p_{1},p_{2},\dots,p_{n}\in[0.1,0.9]$. Suppose that $X_{1},X_{2},\dots,X_{n}$
are independent Bernoulli random variables with $X_{i}\sim Be(p_{i})$. Then:

$\displaystyle\max_{x\in\mathbb{R}}\
\mathbb{P}\bigg{(}\displaystyle\sum_{i=1}^{n}a_{i}X_{i}=x\bigg{)}=O(n^{-1/2}).$

###### Proof.

For each $i\in[n]$ choose $w_{i},z_{i}\in[0,1]$ such that
$p_{i}=w_{i}/2+(1-w_{i})z_{i}$. Then write $X_{i}$ as
$X_{i}=W_{i}Y_{i}+(1-W_{i})Z_{i}$, where $W_{i}\sim Be(w_{i}),\ Z_{i}\sim
Be(z_{i})$ and $Y_{i}\sim Be(0.5)$ are independent random variables. We want
to make this choice so that each $w_{i}\geq 0.2$ and we can do this by letting
$z_{i}=0,w_{i}=2p_{i}$ if $p_{i}\leq 1/2$ and by letting
$z_{i}=1,w_{i}=2(1-p_{i})$ if $p_{i}>1/2$.

We now condition on any choice $\mathcal{C}$ of the $W_{i}$’s and $Z_{i}$’s.
Let $I=\\{i\in[n]:W_{i}=1\\}$ and suppose that we have $Z_{i}=z_{i}$ after the
conditioning. On one hand, if $|I|\geq n/10$ then
$\mathbb{P}\big{(}\sum_{i=1}^{n}a_{i}X_{i}=x\ |\
\mathcal{C}\big{)}=\mathbb{P}\big{(}\sum_{i\in I}a_{i}Y_{i}+\sum_{i\notin
I}a_{i}z_{i}=x\ |\ \mathcal{C}\big{)}$ becomes $\mathbb{P}\big{(}\sum_{i\in
I}a_{i}Y_{i}=x_{\mathcal{C}}\big{)}$ where $x_{\mathcal{C}}=x-\sum_{i\notin
I}z_{i}$ is a constant, which by Theorem 2.2 (eventually with a scaling
argument) is at most $O(n^{-1/2})$. On the other hand, let
$\overline{W}=(W_{1}+W_{2}+\dots+W_{n})/n$ and observe that
$|I|=n\overline{W}$. Moreover, we have $\mathbb{E}[\overline{W}]\geq 0.2$
since $w_{i}\geq 0.2$ for each $i$. Therefore we deduce $\mathbb{P}(|I|\leq
n/10)=\mathbb{P}(\overline{W}\leq
0.1)\leq\mathbb{P}(\overline{W}-\mathbb{E}[\overline{W}]\leq-0.1)\leq\mathbb{P}(|\overline{W}-\mathbb{E}[\overline{W}]|\leq-0.1)$.
So we get by Chebyshev’s Inequality that $\mathbb{P}(|I|\leq n/10)\leq
O(n^{-1})$.

The conclusion follows by combining these two results in the Law of Total
Probability. ∎

The following optimization results will be very useful along the way.

######  Lemma 2.4.

Let $b\geq a>0$ and let $0<\alpha<1$. Then the function $f:[0,a)\to\mathbb{R}$
given by $f(x):=(b+x)^{\alpha}+(a-x)^{\alpha}$ is strictly decreasing. In
particular, for all $t\in(0,a)$ we have:

$b^{\alpha}+a^{\alpha}>(b+a-t)^{\alpha}+t^{\alpha}.$

###### Proof.

Note that $f^{\prime}(x)=\alpha(b+x)^{\alpha-1}-\alpha(a-x)^{\alpha-1}<0$ on
the interval $[0,a)$ since $\alpha-1<0$ and $b+x\geq a-x>0$. This gives us the
first part, whereas the second one is just $f(0)>f(a-t)$. ∎

######  Lemma 2.5.

Let $a,b>0$. Then
$a\log_{2}a+b\log_{2}b+2\min\\{a,b\\}\leq(a+b)\log_{2}(a+b)$.

###### Proof.

We may assume that $a\leq b$. Let now $x:=a+b$ and $a:=tx$ with $0<t\leq 1/2$.
Upon dividing by $x$, the inequality we need to prove rewrites as
$2t+t\log_{2}(tx)+(1-t)\log_{2}((1-t)x)\leq\log_{2}x$, which is equivalent to
$2t+t\log_{2}t+(1-t)\log_{2}(1-t)\leq 0$ for $0<t\leq 1/2$.
The map $f:(0,\infty)\to\mathbb{R}$ given by $f(y)=y\log_{2}y$ is convex and
can be continuously extended to $f(0)=0$. Therefore the $LHS$ in our last
inequality above is convex, so we only need to check that the inequality holds
for $t=0$ and $t=1/2$, which can be easily seen. ∎

Finally, we require some classic concentration inequalities. See e.g. appendix
A in [4].

######  Theorem 2.6 (Chernoff Inequality).

Let $X$ be a random variable with binomial distribution and let
$\mu=\mathbb{E}[X]$. Then, for $0\leq\delta\leq 1$, the following inequalities
hold:

$\mathbb{P}\big{(}X\leq(1-\delta)\mu\big{)}\leq\exp\left(-{\dfrac{\delta^{2}\mu}{2}}\right).$
$\mathbb{P}\big{(}X\geq(1+\delta)\mu\big{)}\leq\exp\left(-{\dfrac{\delta^{2}\mu}{4}}\right).$

The following bound will be useful for larger deviations.

######  Theorem 2.7.

Let $n\in\mathbb{N},\ p\in[0,1],\ L>0$ an let $X\sim Bin(n,p)$ be a random
variable. Then:

$\mathbb{P}(X\geq L)\leq\binom{n}{L}p^{L}\leq\left(\frac{enp}{L}\right)^{L}.$

Lastly, we will also require Hoeffding’s inequality.

######  Theorem 2.8 (Hoeffding’s Inequality).

Let $X_{1},X_{2},\dots,X_{n}$ be independent random variables such that
$a_{i}\leq X_{i}\leq b_{i}$ for each $i\in[n]$, where
$a_{i},b_{i}\in\mathbb{R}$. Then given $t>0$, the random variable
$S_{n}=X_{1}+\dots+X_{n}$ satisfies:

$\mathbb{P}\left(|S_{n}-\mathbb{E}[S_{n}]|\geq t\right)\leq
2\emph{exp}\left(\dfrac{-2t^{2}}{\sum_{i\in[n]}(b_{i}-a_{i})^{2}}\right).$

##  3 Degrees and distributions on the continuous cube

###  3.1 Recasting the problem

Given a graph $G$ and a probability vector
$\textbf{\text@underline{p}}=(p_{v})_{v\in V(G)}\in[0.1,0.9]^{V(G)}$ we will
write $G(\textbf{\text@underline{p}})$ to denote the probability space on the
set of induced subgraphs of $G$, determined by including each vertex $v\in
V(G)$ independently with probability $p_{v}$. Equivalently, given $S\subset
V(G)$, the induced subgraph $G[S]$ is selected with probability $\prod_{v\in
S}p_{v}\prod_{v\in V(G)\setminus S}(1-p_{v})$. Abusing notation slightly111As
with the Erdős–Renyi random graph $G(n,p)$., we will usually write
$G(\textbf{\text@underline{p}})$ to denote a random graph $G[S]\sim
G(\textbf{\text@underline{p}})$.

Throughout the paper, given a vertex $u\in V(G)$, we will we write
$\textbf{u}\in\\{0,1\\}^{V(G)}$ to denote the _neighbourhood vector_ of $u$,
which is given by:

$\displaystyle({\bf u})_{v}=\begin{cases}1\quad\mbox{ if }uv\in E(G);\\\
0\quad\mbox{ otherwise}.\end{cases}$

Note that, considering the standard inner product on ${\mathbb{R}}^{V(G)}$,
given by ${\bf x}\cdot{\bf y}=\sum_{v\in V(G)}x_{v}y_{v}$, this notation leads
us to the useful representation:

$\displaystyle{\mathbb{E}}\big{[}d_{G(\textbf{\text@underline{p}})}(u)\big{]}=\bf
<EMAIL_ADDRESS>(1)

Our first lemma comes to show that two vertices whose expected degrees (under
the distribution $G(\textbf{\text@underline{p}})$) are separated are unlikely
to have the same degree in an induced subgraph selected according to
$G(\textbf{\text@underline{p}})$.

######  Lemma 3.1.

Let $G$ be a graph and let $u,v$ be distinct vertices in $G$. Suppose that
there is a probability vector $\textbf{\text@underline{p}}\in[0.1,0.9]^{V}$
such that
$\big{|}\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u)]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(v)]\big{|}\geq
D\geq 2$. Then:

$\mathbb{P}\big{(}d_{G(\textbf{\text@underline{p}})}(u)=d_{G(\textbf{\text@underline{p}})}(v)\big{)}=O\bigg{(}\frac{\sqrt{\log
D}}{D}\bigg{)}.$

###### Proof.

Set $W:=\operatorname{div}(u,v)$ and $T=|W|$; by hypothesis $T\geq 2$. Letting
$X:=d_{G(\textbf{\text@underline{p}})}(u)-d_{G(\textbf{\text@underline{p}})}(v)$,
this random variable can be written as $X=\sum_{w\in W}\pm X_{w}$ where
$X_{w}\sim\mbox{Be}(p_{w})$ are independent Bernoulli random variables. We
seek to upper bound
$\mathbb{P}\big{(}d_{G(\textbf{p})}(u)=d_{G(\textbf{p})}(v)\big{)}={\mathbb{P}}(X=0)$.

As $\big{|}\mathbb{E}[X]\big{|}\geq D$ by our hypothesis, one gets by
Hoeffding’s Inequality that:

$\displaystyle\mathbb{P}(X=0)$
$\displaystyle\leq\mathbb{P}\big{(}|X-\mathbb{E}[X]|\geq D\big{)}\leq
2\text{exp}(-D^{2}/4T),$

since $X$ is a sum of $T$ independent random variables taking values in the
interval $[-1,1]$. On the other hand, by Theorem 2.3 we get
$P(X=0)=O\left(T^{-1/2}\right)$. Thus:

$\displaystyle{\mathbb{P}}\big{(}X=0\big{)}\leq\min\big{\\{}O(T^{-1/2}),2\exp(-D^{2}/4T)\big{\\}}.$
(2)

The map $x\mapsto 1/\sqrt{x}$ is decreasing on $(0,\infty)$, whereas
$x\mapsto\text{exp}(-D^{2}/4x)$ is increasing, and their intersection point
satisfies the equation $\sqrt{x}=\text{exp}(D^{2}/4x)$, i.e. $D^{2}=2x\log x$.
This gives $x=\Theta(D^{2}/\log(D))$ and we get the conclusion by substituting
this into (2). ∎

Given a graph $G$, a probability vector
$\textbf{\text@underline{p}}\in[0,1]^{V(G)}$ and $D>0$, a set $U\subset V(G)$
is said to be _$D$ -separated in $G(\textbf{\text@underline{p}})$_ if
$|{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}(u)]-{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}(v)]|\geq
D$ for all distinct $u,v\in U$.

In analogy with $f(G)$, define:

$\displaystyle{f}_{\textbf{\text@underline{p}}}(G):=\max\big{\\{}|U|:U\subset
V(G)\mbox{ such that }U\mbox{ is 1-separated in
}G(\textbf{\text@underline{p}})\big{\\}}.$

The next result shows a lower bound for $f(G)$ follows from a lower bound for
$f_{\textbf{\text@underline{p}}}(G)$.

######  Theorem 3.2.

Given a graph $G$ and a probability vector
$\textbf{\text@underline{p}}\in[0.1,0.9]^{V(G)}$ with
$f_{\textbf{\text@underline{p}}}(G)\geq 2$, the following relation holds:

$\displaystyle
f(G)=\Omega\bigg{(}\frac{{f}_{\textbf{\text@underline{p}}}(G)}{\log^{3/2}\big{(}{f}_{\textbf{\text@underline{p}}}(G)\big{)}}\bigg{)}.$

###### Proof.

First note that $f(G)\geq 1$ for every non-empty graph $G$, therefore we may
assume that $L:=f_{\textbf{\text@underline{p}}}(G)\geq C$ for some absolute
constant $C$. As above, we will write $G[S]$ to denote a random induced
subgraph $G[S]\sim G(\textbf{\text@underline{p}})$. Let $U\subset V(G)$ be a
$1$-separated set in $G(\textbf{\text@underline{p}})$ with
$U=\\{u_{1},u_{2}\ldots,u_{L}\\}$, so that the vertices are ordered with
increasing expected degree in $G(\textbf{\text@underline{p}})$. It follows
that if $j-i\geq 2$ then
$D_{i,j}:={\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}(u_{j})]-{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}(u_{i})]\geq
j-i\geq 2$ and so we can apply Lemma 3.1 to obtain that:

$\mathbb{P}\big{(}d_{G(\textbf{\text@underline{p}})}(u_{j})=d_{G(\textbf{\text@underline{p}})}(u_{i})\big{)}\leq\frac{c\sqrt{\log(D_{i,j})}}{D_{i,j}}\leq\frac{c\sqrt{\log(j-i)}}{j-i},$

where here $c>0$ is an absolute constant. Here we used that $\sqrt{\log x}/x$
is decreasing for $x\geq 2$.

Now let us consider a random graph $H$ on
$U_{1}=\\{u_{3},u_{6},\ldots,u_{3\lfloor L/3\rfloor}\\}$, where we build an
edge between two vertices if they have the same degree in $G[S]\sim
G(\textbf{\text@underline{p}})$. The expected number of edges in $H$ is given
by:

$\displaystyle\mathbb{E}[e(H)]=\sum_{\\{u_{3i},u_{3j}\\}\subset
U_{1}}\mathbb{P}\big{(}d_{G(\textbf{\text@underline{p}})}(u_{3j})=d_{G(\textbf{\text@underline{p}})}(u_{3i})\big{)}$
$\displaystyle\leq$ $\displaystyle\sum_{\\{u_{3i},u_{3j}\\}\subset
U_{1}}\frac{c\sqrt{\log(3j-3i)}}{3(j-i)}$ $\displaystyle\leq$
$\displaystyle\dfrac{cL}{9}\sqrt{\log(L)}\cdot\bigg{(}\sum_{d=1}^{L/3}\frac{1}{d}\bigg{)}\leq\dfrac{cL}{9}\log^{3/2}(L).$

It follows by Markov that ${\mathbb{P}}\big{(}e(H)\leq
cL\log^{3/2}(L)/3\big{)}\geq 2/3$.

On the other hand, we have ${\mathbb{E}}[|S\cap U_{1}|]\geq|U_{1}|/10\geq
L/32$ and so by Chernoff’s inequality, using that $L\geq C$, we have
${\mathbb{P}}(|S\cap U_{1}|\geq L/64)\geq 2/3$.

Combining these two bounds guarantees that there exists an induced subgraph
$G[S]$ with the property that the set $U_{2}:=S\cap U_{1}$ satisfies
$|U_{2}|\geq L/64$ and $e(H[U_{2}])\leq e(H)\leq cL\log^{3/2}(L)/3$. From
Turán’s theorem we see that the subgraph $H[U_{2}]$ contains an independent
set of order
$\Omega(3|U_{2}|^{2}/cL\log^{3/2}(L)\big{)}=\Omega\big{(}L/\log^{3/2}(L)\big{)}$.
By definition of $H$ such a set necessarily has distinct degrees in $G[S]$,
thus completing the proof. ∎

###  3.2 Moving to distributions

The message we get from Theorem 3.2 is that a lower bound on $f(G)$ for _any_
graph $G$ (up to logarithmic factors) follows from a lower bound on:

$\displaystyle\widetilde{f}(G):=\max_{\textbf{\text@underline{p}}\in[0.1,0.9]^{V(G)}}f_{\textbf{\text@underline{p}}}(G).$

This second quantity can be perceived as a continuous relaxation of $f(G)\ -$
which trivially corresponds to maximizing over $\\{0,1\\}^{V(G)}$. However,
from our point of view the second solution space is considerably richer, and
in particular will allow different behaviours to be blended in a way that is
not possible with vectors from the discrete cube; for example, one can take
convex combinations of vectors in $[0,1]^{V(G)}$.

Although we would like to lower bound ${\widetilde{f}}(G)$, this quantity
turns out to be just too rigid for certain inductive steps which we want to
carry out later222See comment before Lemma 4.1 below.. Instead, we introduce a
generalised parameter, defined in terms of probability distributions on
$[0.1,0.9]^{V(G)}$, which turns out to be more robust in this respect.

Let $G$ be a graph and let ${\cal D}$ be a probability distribution on
$[0.1,0.9]^{V(G)}$. Given distinct vertices $u,v\in V(G)$ and a set $S\subset
V(G)$, we define:

$\displaystyle\operatorname{bad}_{\mathcal{D}}^{S}({u,v}):=\max_{c\in\mathbb{R}}\
\underset{\textbf{\text@underline{p}}\sim\mathcal{D}}{\mathbb{P}}\big{(}|\mathbb{E}[d_{G(\textbf{\text@underline{p}})}^{S}(u)]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}^{S}(v)]-c|\leq
1\big{)}.$ (3)

This quantity can be viewed as a small ball probability $-$ a measurement for
two vertices $u,v\in V(G)$ of how likely the expected degrees to $S$ in
$G(\textbf{\text@underline{p}})$ are to differ by an (almost) fixed amount.
Given sets $U,S\subset V(G)$, we also set:

$\operatorname{bad}_{\mathcal{\cal
D}}^{S}({U}):=\displaystyle\sum_{\\{u,v\\}\subset
U}\operatorname{bad}_{\mathcal{\cal D}}^{S}({u,v}).$

Given another set $V\subset V(G)$ we can also write:

$\operatorname{bad}_{\mathcal{\cal D}}^{S}({U,V}):=\displaystyle\sum_{(u,v)\in
U\times V}\operatorname{bad}_{\mathcal{\cal D}}^{S}({u,v}).$

We will sometimes suppress the superscript when $S=V(G)$, e.g.
$\operatorname{bad}_{\mathcal{D}}({U})=\operatorname{bad}_{\mathcal{\cal
D}}^{V(G)}({U})$. Lastly, let us remark that in (3) we do not need
$\mathcal{D}$ to be defined on all vertex coordinates of the set
$[0.1,0.9]^{V(G)}$; any vertex set $T$ with $S\subseteq T\subseteq V(G)$ is
enough so that we can define $\mathcal{D}$ on $[0.1,0.9]^{T}$, as we can see
by looking at the RHS of (3).

The following lemma shows that a lower bound on
$f_{\textbf{\text@underline{p}}}(G)$ (and on $f(G)$ by Theorem 3.2) follows by
finding a large subset $U\subset V(G)$ such that
$\operatorname{bad}_{\mathcal{D}}({U})$ is bounded in terms of $|U|$.

######  Lemma 3.3.

Let $G$ be a graph, let ${\cal D}$ be a probability distribution on
$[0.1,0.9]^{V(G)}$ and let $U\subset V(G)$ with
$\operatorname{bad}_{\mathcal{D}}({U})=\alpha\cdot|U|$. Then there is
$\textbf{\text@underline{p}}\in[0.1,0.9]^{V(G)}$ with
$f_{\textbf{\text@underline{p}}}(G)\geq|U|/(1+\alpha)$.

###### Proof.

To see this, select $\textbf{\text@underline{p}}\sim{\cal D}$ and let $Y$
denote the random set:

$Y(\textbf{\text@underline{p}}):=\big{\\{}\\{u,v\\}\subset
U:\big{|}\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u)]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(v)]\big{|}\leq
1\big{\\}}.$

Note that:

$\displaystyle\underset{\textbf{\text@underline{p}}\sim{\cal
D}}{\mathbb{E}}\big{[}|Y(\textbf{\text@underline{p}})|\big{]}$
$\displaystyle=$ $\displaystyle\sum_{\\{u,v\\}\subset
U}{\mathbb{P}}\big{(}\big{|}\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u)]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(v)]\big{|}\leq
1\big{)}$ $\displaystyle\leq$ $\displaystyle\sum_{\\{u,v\\}\subset
U}\operatorname{bad}_{\mathcal{D}}({u,v})=\operatorname{bad}_{\mathcal{D}}({U})=\alpha|U|.$

It follows that there is a choice of
$\textbf{\text@underline{p}}\in[0.1,0.9]^{V(G)}$ such that
$|Y(\textbf{\text@underline{p}})|\leq\alpha|U|$. Viewing the pairs in
$Y(\textbf{\text@underline{p}})$ as the edges of a graph $J$ on the vertex set
$U$, again by Turán’s theorem we can find an independent set in this graph
which has order $|U|/(1+\alpha)$. By definition of $J$, this gives a lower
bound on $f_{\textbf{\text@underline{p}}}(G)$, as required. ∎

From Theorem 3.2, the quantity $f(G)$ is (essentially) lower bounded by
$f_{\textbf{\text@underline{p}}}(G)$. To close this subsection, and complete
the circle, we show that that this also holds in the reverse direction. In
particular, up to logarithms the quantities $f(G)$ and ${\widetilde{f}}(G)$
are of the same order of magnitude.

######  Lemma 3.4.

Let $G$ be a graph and let $U\subset S\subset V(G)$ be vertex subsets such
that all vertices of $U$ have distinct degrees in $G[S]$. Then there is a
distribution ${\cal D}$ on $[0.1,0.9]^{V(G)}$ such that
$\operatorname{bad}_{\mathcal{D}}({U})=O\big{(}|U|\log|U|\big{)}$. In
particular, there is $\textbf{\text@underline{p}}\in[0.1,0.9]^{V(G)}$ such
that:

$f_{\textbf{\text@underline{p}}}(G)=\Omega\bigg{(}\frac{f(G)}{\log
f(G)}\bigg{)}.$

###### Proof.

To see this, let ${\bf s}\in\\{0,1\\}^{V(G)}$ denote the indicator vector of
the set $S$ and let $\bm{1}$ denote the constant $1$ vector. Let
$U:=\\{u_{1},u_{2},\ldots,u_{|U|}\\}$ and assume that $d_{G[S]}(u_{i})$ is
increasing with $i$, which by (1) gives $({\bf u}_{j}-{\bf u}_{i})\cdot{\bf
s}\geq j-i$ for all $1\leq i<j\leq|U|$.

Select $\alpha$ uniformly at random in $[-0.4,0.4]$ and consider the random
vector:

$\displaystyle\textbf{\text@underline{p}}:=\frac{1}{2}\cdot{\bf
1}+\alpha\cdot{\bf s}\in[0.1,0.9]^{V(G)}.$

Write ${\cal D}$ for the resulting probability distribution on
$[0.1,0.9]^{V(G)}$. Given p, by (1) we get:

$\displaystyle{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}(u_{j})]-{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}(u_{i})]=({\bf
u}_{j}-{\bf u}_{i})\cdot\textbf{\text@underline{p}}=\alpha\cdot\big{(}{\bf
u}_{j}-{\bf u}_{i}\big{)}\cdot{\bf s}+c^{\prime},$

for some fixed constant $c^{\prime}$. As $\big{(}{\bf u}_{j}-{\bf
u}_{i}\big{)}\cdot{\bf s}\geq j-i$ and $\alpha$ is uniformly chosen from
$[-0.4,0.4]$, it follows that
${\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}(u_{j})]-{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}(u_{i})]$
is uniformly distributed over an interval of length at least $0.8(j-i)$. By
definition (3), this then gives:

$\displaystyle\operatorname{bad}_{\mathcal{D}}({u_{i},u_{j}})\leq\frac{2}{0.8(j-i)}\leq\frac{3}{j-i}.$

It follows that
$\operatorname{bad}_{\mathcal{D}}({U})=\displaystyle\sum_{1\leq
i<j\leq|U|}\operatorname{bad}_{\mathcal{D}}({u_{i},u_{j}})\leq\displaystyle\sum_{d=1}^{|U|}\dfrac{3|U|}{d}\leq
6|U|\log|U|$, giving us the first bound. The second then follows immediately
from Lemma 3.3. ∎

##  4 Building distributions for distinct degrees

From the previous section, via Theorem 3.2 and Lemma 3.3, we know that in
order to find many distinct degrees in a graph $G$ it suffices to find a large
set $U\subset V(G)$ and a probability distribution ${\cal D}$ such that
$\operatorname{bad}_{\mathcal{D}}({U})$ is small. In this section we will
collect a number of results together, which will be used in combination to
exhibit such distributions ${\cal D}$.

From the ‘iterated’ graph examples discussed in Section 1 we saw that
occasionally we must first find distinct degree sets $U_{i}$ in graphs
$G[S_{i}]$ where $\\{S_{i}\\}_{i}$ are disjoint, and then combine these sets
together so that $\bigcup_{i}U_{i}$ will have distinct degrees in
$G[\bigcup_{i}S_{i}]$. Unfortunately, it is also not hard to see that vertices
within $U_{i}$ can easily agree in degree in the resulting union graph, even
if we move from sets $U_{i}$ to vectors $\textbf{\text@underline{p}}_{i}$ as
in Section 3.

While working with fixed sets or vectors can cause difficulties, our first
lemma shows that the setting of distributions allows more flexibility here: we
can combine distributions while maintaining ’bad’ control. This flexibility
was the key motivation for working in this more generalised setting (indicated
in subsection 3.2).

######  Lemma 4.1.

Let $G$ be a graph with vertex partition $V(G)=\bigsqcup_{i=1}^{L}V_{i}$ and
for each $i\in[L]$ let $\mathcal{D}_{i}$ be a probability distribution on
$[0,1]^{V_{i}}$. Then taking $\mathcal{D}$ to denote the product distribution
$\Pi_{i\in[L]}\mathcal{D}_{i}$ on $[0,1]^{V(G)}$, for any distinct vertices
$u,v\in V(G)$ and any set $S\subset V(G)$, one has:

$\operatorname{bad}_{\mathcal{D}}^{S}({u,v})\leq\min_{i\in[L]}\operatorname{bad}_{\mathcal{D}_{i}}^{S\cap
V_{i}}({u,v}).$

###### Proof.

To see this, take $c\in\mathbb{R}$ and define $X$ to be the random variable:

$X(\textbf{\text@underline{p}}):=\mathbb{E}[d_{G(\textbf{\text@underline{p}})}^{S}(u)]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}^{S}(v)]-c.$

It suffices to prove that $\underset{{\bf
p}\sim\mathcal{D}}{\mathbb{P}}\big{(}|X|\leq
1\big{)}\leq\operatorname{bad}_{\mathcal{D}_{i}}^{S\cap V_{i}}({u,v})$ for all
$i\in[L]$ as the result will follow from our definition of
$\operatorname{bad}_{\mathcal{D}}({u,v})$. Let $W_{i}:=V(G)\setminus V_{i}$
for each $i\in[L]$. Given $\textbf{\text@underline{p}}\in[0,1]^{V(G)}$, we
denote by $\textbf{\text@underline{p}}_{i}$ and
$\textbf{\text@underline{q}}_{i}$ its projections on $V_{i}$ and $W_{i}$,
respectively, which are mutually independent.
It is easy to see that:

$X(\textbf{\text@underline{p}})=\mathbb{E}[d_{G(\textbf{\text@underline{p}})}^{S\cap
V_{i}}(u)]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}^{S\cap
V_{i}}(v)]+\mathbb{E}[d_{G({\textbf{\text@underline{p}}})}^{S\cap
W_{i}}(u)]-\mathbb{E}[d_{G({\textbf{\text@underline{p}}})}^{S\cap
W_{i}}(v)]-c.$

Conditioned on any choice for $\textbf{\text@underline{q}}_{i}$, we see that
$\mathbb{E}[d_{G(\textbf{\text@underline{p}})}^{S\cap
W_{i}}(u)]-\mathbb{E}[d_{G({\textbf{\text@underline{p}}})}^{S\cap W_{i}}(v)]$
becomes a constant, therefore we obtain that:

$\underset{{\bf p}\sim\mathcal{D}}{\mathbb{P}}\big{(}|X|\leq 1|\
\textbf{\text@underline{q}}_{i}\big{)}=\underset{{\bf
p}_{i}\sim\mathcal{D}_{i}}{\mathbb{P}}\big{(}|\mathbb{E}[d_{G(\textbf{\text@underline{p}}_{i})}^{S\cap
V_{i}}(u)]-\mathbb{E}[d_{G(\textbf{\text@underline{p}}_{i})}^{S\cap
V_{i}}(v)]-c^{\prime}|\leq
1\big{)}\leq\operatorname{bad}_{\mathcal{D}_{i}}^{S\cap V_{i}}({u,v}),$

as $\textbf{\text@underline{p}}_{i}$ and $\textbf{\text@underline{q}}_{i}$ are
independent. It follows that $\underset{{\bf
p}\sim\mathcal{D}}{\mathbb{P}}\big{(}|X|\leq
1\big{)}\leq\operatorname{bad}_{\mathcal{D}_{i}}^{S}({u,v})$, as desired. ∎

Our second lemma gives a simple situation in which we can obtain ‘bad’
control. Let $G$ be a graph and let $S\subset V(G)$. Let ${\cal U}_{S}$ denote
the _uniformly constant distribution_ on $[0.1,0.9]^{S}$, given by selecting
$\alpha\in[0.1,0.9]$ uniformly at random and setting
$\textbf{\text@underline{p}}=\alpha{\bf 1}_{S}\in[0.1,0.9]^{S}$.

######  Lemma 4.2.

Let $G$ be a graph, $S\subset V(G)$ and $u,v\in V(G)$ such that $d^{S}(u)\geq
d^{S}(v)+D$ for some $D>0$. Suppose that ${\cal U}_{S}$ denotes the uniform
constant distribution on $[0.1,0.9]^{S}$, that ${\cal D}^{\prime}$ denotes a
distribution on $[0.1,0.9]^{V(G)\setminus S}$ and that ${\cal D}$ denotes the
product distribution ${\cal U}_{S}\times{\cal D}^{\prime}$ on
$[0.1,0.9]^{V(G)}$. Then $\operatorname{bad}_{\mathcal{D}}({u,v})\leq
3D^{-1}.$

###### Proof.

First note that by Lemma 4.1 we have
$\operatorname{bad}_{\mathcal{D}}({u,v})\leq\operatorname{bad}_{\mathcal{\cal
U}_{S}}^{S}({u,v})$ and so it suffices to upper bound this second quantity.

Taking $c\in{\mathbb{R}}$, we seek to upper bound the probability that
$|{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(u)]-{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(v)]-c|\leq
1$, where $\textbf{\text@underline{p}}\sim{\cal U}_{S}$. To analyse this, note
that:

$\displaystyle{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(u)]-{\mathbb{E}}[d_{G(\textbf{\text<EMAIL_ADDRESS>
Since $\textbf{\text@underline{p}}=\alpha{\bf 1}_{S}$ where $\alpha$ is
selected uniformly at random from [0.1,0.9], this gives:

$\displaystyle{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(u)]-{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(v)]=(\operatorname{proj}_{S}({\bf{u}})-\operatorname{proj}_{S}({\bf{v}}))\cdot\alpha{\bf
1}_{S}=\alpha\big{(}d^{S}(u)-d^{S}(v)\big{)}.$

As $\alpha$ varies uniformly over the interval $[0.1,0.9]$ and
$d^{S}(u)-d^{S}(v)\geq D$ by hypothesis, the quantity
${\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(u)]-{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(v)]$
varies uniformly over an interval of length at least $0.8D$, giving that the
probability that
$|{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(u)]-{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(v)]-c|\leq
1$ is at most $2/(0.8D)\leq 3D^{-1}$. ∎

We next seek to provide ’bad’ control for a set by blending neighbourhood
structures together $-$ the idea here has some similarities to that of [19].
Let $G$ be a graph, let $U,S\subset V(G)$, where
$U:=\\{u_{1},\ldots,u_{k}\\}$, and let $\beta\in[0,0.4]$. We now let ${\cal
B}_{\beta}(U,S)$ denote the _blended probability distribution_ on
$[0.1,0.9]^{S}$, which is defined as follows. First independently select
$\alpha_{i}\in[-\beta,\beta]$ uniformly at random for each $i\in[k]$ and set:

$\displaystyle\textbf{\text@underline{p}}^{\prime}:=\frac{1}{2}\cdot{\bf
1}+\sum_{i\in[k]}\alpha_{i}\cdot\operatorname{proj}_{S}({\bf{u}}_{i})\in\mathbb{R}^{S}.$
(4)

Having made these choices, the distribution then returns p, a truncated
version of $\textbf{\text@underline{p}}^{\prime}$, where:

$\displaystyle\textbf{\text@underline{p}}_{v}=\begin{cases}\textbf{\text@underline{p}}_{v}^{\prime}\quad\mbox{if
}\textbf{\text@underline{p}}_{v}^{\prime}\in[0.1,0.9];\\\ 0.9\quad\mbox{if
}\textbf{\text@underline{p}}_{v}^{\prime}>0.9;\\\ 0.1\quad\mbox{if
<EMAIL_ADDRESS>
Our final lemma in this section provides ’bad’ control for blended
distributions under certain well-behaved situations. Given $D>0$,
$\gamma\in[0,1]$ and sets $U$ and $S$ as above we say that:

  * •

$U$ is _$D$ -diverse to $S$_ if for all distinct $u,v\in U$ we have
$|N_{G}^{S}(u)\triangle N_{G}^{S}(v)|\geq D$.

  * •

$U$ is $\gamma$-_balanced to_ $S$ if for all $v\in S$ we have
$d_{G}^{U}(v)\leq\gamma|U|$.

Let us quickly remark that $U$ is always $1$-_balanced to_ $S$.

######  Lemma 4.3.

Let $G$ be a graph, $D>0,\ \beta\in(0,0.1),\ \gamma\in(0,1]$ and $U,S\subset
V(G)$ such that $U$ is both $D$-diverse and $\gamma$-balanced to $S$. Suppose
that ${\cal D}^{\prime}$ denotes a distribution on $[0.1,0.9]^{V(G)\setminus
S}$, that ${\cal B}_{\beta}(U,S)$ is the blended probability distribution on
$[0.1,0.9]^{S}$ and that ${\cal D}$ is the product distribution ${\cal
B}_{\beta}(U,S)\times{\cal D}^{\prime}$ on $[0.1,0.9]^{V(G)}$. Then for all
$u,v\in U$ one has:

$\operatorname{bad}_{\mathcal{D}}({u,v})\leq\dfrac{2}{\beta
D}+D\exp\left(\dfrac{-0.045}{\gamma\beta^{2}|U|}\right).$ (5)

###### Proof.

Suppose $U=\\{u_{1},u_{2},\ldots,u_{k+1}\\}$ and that for each $i\in[k+1]$,
given the vector $\textbf{\text@underline{p}}^{\prime}$ on $\mathbb{R}^{S}$
from (4), we define the random vector $\textbf{\text@underline{q}}^{i}$ on
$\mathbb{R}^{S}$ by
$\textbf{\text@underline{q}}^{i}:=\textbf{\text@underline{p}}^{\prime}-\alpha_{i}\cdot\operatorname{proj}_{S}({\bf{u}}_{i})$.
The key observation is that $\textbf{\text@underline{q}}^{i}$ is independent
of $\alpha_{i}$. We will slightly abuse notation by writing p for both a
vector in $[0.1,0.9]^{V(G)}$ and its projection
$\operatorname{proj}_{S}({\bf{\underline{p}}})$ onto the coordinate set $S$.
We can do this without much of a worry since $\mathcal{D}$ is the product
distribution ${\cal B}_{\beta}(U,S)\times{\cal D}^{\prime}$.
Fix $c\in\mathbb{R}$, $i,j\in[k+1]$ and let $E_{i,j}(c)$ denote the event
$\big{|}\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u_{i})]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u_{j})]-c\big{|}\leq
1$. According to (3), to prove the lemma it will suffice to show that:

$\mathbb{P}(E_{i,j}(c))\leq\dfrac{2}{\beta
D}+D\exp\left(\dfrac{-0.045}{\gamma\beta^{2}|U|}\right).$

To upper bound $\mathbb{P}(E_{i,j}(c))$, we might assume that
$|N^{S}(u_{i})\setminus N^{S}(u_{j})|\geq|N^{S}(u_{j})\setminus
N^{S}(u_{i})|$, so that $|N^{S}(u_{i})\setminus N^{S}(u_{j})|\geq D/2$. Pick a
subset $Y_{i,j}\subset N^{S}(u_{i})\setminus N^{S}(u_{j})$ of size $D/2$. We
call a vertex $v\in Y_{i,j}$ _naughty_ if
$\textbf{\text@underline{q}}_{v}^{i}\notin[0.2,0.8]$. We say the set $Y_{i,j}$
is _naughty_ if it contains a naughty vertex and we let $F_{i,j}$ denote this
event. By the law of total probability we get that:

$\mathbb{P}\big{(}E_{i,j}(c)\big{)}=\mathbb{P}\big{(}E_{i,j}(c)|F_{i,j}\big{)}\cdot\mathbb{P}(F_{i,j})+\mathbb{P}\big{(}E_{i,j}(c)|\overline{F_{i,j}}\big{)}\cdot\mathbb{P}(\overline{F_{i,j}})\leq\mathbb{P}(F_{i,j})+\mathbb{P}\big{(}E_{i,j}(c)|\overline{F_{i,j}}\big{)}.$

Let $v\in S$. Note that $\textbf{\text@underline{q}}_{v}^{i}$ is a sum of
$d_{G}^{U\setminus\\{u_{i}\\}}(v)$ uniform independent random variables, as
the coordinates $\textbf{u}_{i_{v}}$ are non-zero when $v\sim u_{i}$. Thus by
Hoeffding Inequality we get:

$\mathbb{P}\big{(}\textbf{\text@underline{q}}_{v}^{i}\notin[0.2,0.8]\big{)}=\mathbb{P}\big{(}|\textbf{\text@underline{q}}_{v}^{i}-1/2|>0.3\big{)}\leq
2\exp\left(\dfrac{-2\cdot
0.09}{4\beta^{2}d_{G}^{U\setminus\\{u_{i}\\}}(v)}\right)\leq
2\exp\left(\dfrac{-2\cdot 0.09}{4\beta^{2}\gamma|U|}\right),$

where the final inequality uses that $d_{G}^{U\setminus\\{u_{i}\\}}(v)\leq
d_{G}^{U}(v)\leq\gamma|U|$ as $U$ is $\gamma$-balanced to $S$. By the union
bound we get that
$\mathbb{P}(F_{i,j})\leq|Y_{i,j}|\mathbb{P}\big{(}\textbf{\text@underline{q}}_{v}^{i}\notin[0.2,0.8]\big{)}\leq
D\exp\big{(}-0.045(\gamma\beta^{2}|U|)^{-1}\big{)}$.

To compute $\mathbb{P}\big{(}E_{i,j}(c)|\overline{F_{i,j}}\big{)}$ we
condition on any choice of $\bm{\alpha}:=(\alpha_{l})_{l\neq i}$ such that
$F_{i,j}$ does not hold. Given such a choice, let us first see that
$\textbf{\text@underline{p}}_{v}^{\prime}=\textbf{\text@underline{q}}^{i}_{v}+\alpha_{i}\textbf{u}_{i_{v}}\in[0.1,0.9]$
for all $v\in Y_{i,j}$ since $|\alpha_{i}|<0.1$. So none of the
$Y_{i,j}$-coordinates of $\textbf{\text@underline{p}}^{\prime}$ will get
truncated and recall that $\alpha_{i}$ is independent of $F_{i,j}$. Given a
choice of $\bm{\alpha}$, consider now the following expression as a map of
$\alpha_{i}$:

$\displaystyle
f_{c}(\alpha_{i}):=\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u_{i})]-\mathbb{E}[d_{G(\textbf{\text<EMAIL_ADDRESS>(6)

Having conditioned on $\bm{\alpha}$ above, note that the event $E_{i,j}(c)$
holds only if $f(\alpha_{i})$ lies in an interval of length $2$. However, as
$\alpha_{i}$ increases, the contribution from each coordinate of p to the
inner product on the right hand side of (6) is non-decreasing. Furthermore,
the contribution of all of the $Y_{i,j}$-coordinates is exactly $\alpha_{i}$,
since none of these coordinates were truncated from
$\textbf{\text@underline{p}}^{\prime}$ as we have conditioned on
$\overline{F_{i,j}}$. It follows that for $\varepsilon>0$:

$f(\alpha_{i}+\varepsilon)-f(\alpha_{i})=\displaystyle\sum_{v\in
V(G)}\big{(}(u_{i})_{v}-(u_{j})_{v}\big{)}(u_{i})_{v}\cdot
g_{\varepsilon,v}\geq\varepsilon|Y_{i,j}|=\varepsilon D/2,$

where $g_{\varepsilon,v}\geq 0$ for all $v\in V(G)$ and
$g_{\varepsilon,v}=\varepsilon$ for $v\in Y_{i,j}$. Therefore, conditioned on
$\bm{\alpha}$ as above, if $E_{i,j}(c)$ occurs then $\alpha_{i}$ lies in an
interval of length $4/D$. This happens with probability at most
$2\beta^{-1}D^{-1}$ and the result in (5) quickly follows from the law of
total probability. ∎

Before we end this section, we define a simple but convenient distribution.
Given a graph $G$ and a set $S\subset V(G)$, let ${\cal T}_{S}$ denote the
_trivial $S$-induced probability distribution_, which is simply the
distribution on $[0.1,0.9]^{S}$ which selects the vector
$\textbf{\text@underline{p}}_{0}=\frac{1}{2}\cdot{\bf 1}_{S}$ with probability
$1$.

##  5 The Narayanan–Tomon conjecture

In this section we will prove Theorem 1.1, our approximate version of the
Narayanan–Tomon conjecture. From Theorem 3.2 and Lemma 3.3 it will suffice to
prove the following theorem.

######  Theorem 5.1.

Let $n\in{\mathbb{N}}$ and $k\geq 1$ with $n\geq 20000k^{2}$ and suppose that
$G$ be an $n$-vertex graph with $\hom(G)\leq n/25k$. Then there is a set
$U\subset V(G)$ and a probability distribution ${\cal D}$ on
$[0.1,0.9]^{V(G)}$ such that:

$\displaystyle|U|=\Omega\bigg{(}\frac{k}{\log_{2}^{2}(k+1)}\bigg{)}\quad\mbox{
and }\quad\operatorname{bad}_{\mathcal{D}}({U})=O\big{(}|U|\log|U|\big{)}.$

The proof will split into two regimes. The first deals with the case where
$n=\Omega(k^{5/2})$ and the more difficult second case focuses on the regime
$k^{2}\leq n=O(k^{5/2})$.

To begin, we first present a quick application of Lemma 4.3 that guarantees
‘bad’ control for a set which is $\Omega(k^{3/2})$-diverse.

######  Lemma 5.2.

Let $G$ be a $n$-vertex graph and suppose that there is a set
$U=\\{v_{1},v_{2},\ldots,v_{k+1}\\}$ of vertices of $G$ such that
$|N(v_{i})\triangle N(v_{j})|\geq k^{3/2}+k$ for all $i\neq j$ in $[k+1]$.
Then there is a probability distribution $\mathcal{D}$ on $[0.1,0.9]^{V(G)}$
such that $\operatorname{bad}_{\mathcal{D}}({U})\leq 8|U|\log_{2}|U|$.

###### Proof.

Let $S:=V(G)$ so that $|N^{S}(v_{i})\triangle
N^{S}(v_{j})|=|\text{div}(v_{i},v_{j})|\geq k^{3/2}+k$ for all $i\neq j$ in
$[k+1]$. Therefore $U$ is both $(k^{3/2}+k)$-diverse and $1$-balanced to $S$.
We let $\mathcal{D}:={\cal B}_{\beta}(U,S)$, where we set
$\beta^{-1}:=\sqrt{56(k+1)\log(k+1)}$, and apply Lemma 4.3 to obtain for all
$i\neq j$ that:

$\displaystyle\operatorname{bad}_{\mathcal{D}}({v_{i},v_{j}})$
$\displaystyle\leq
4\sqrt{14}\cdot\dfrac{\log^{1/2}(k+1)}{k}+(k^{3/2}+k)\cdot\exp\big{(}-2.52\log(k+1)\big{)}$
$\displaystyle\leq k^{-1}\big{(}4\sqrt{14}\log^{1/2}(k+1)+1\big{)}.$

As the map $f:[1,\infty)\to\mathbb{R}$ given by
$f(x):=16\log_{2}(x+1)-4\sqrt{14}\log^{1/2}(x+1)-1$ is increasing and positive
at $1$, we can now easily deduce that for all $i\neq j$ one has:

$\operatorname{bad}_{\mathcal{D}}({v_{i},v_{j}})\leq
k^{-1}\big{(}4\sqrt{14}\log^{1/2}(k+1)+1\big{)}\leq 16k^{-1}\log_{2}(k+1).$

By summing over all $i\neq j$ in $[k+1]$ we finally deduce that:

$\displaystyle\operatorname{bad}_{\mathcal{D}}({U})\leq\frac{16\log_{2}(k+1)}{k}\cdot\dbinom{k+1}{2}=8|U|\log_{2}|U|,$

as required.∎

###  5.1 The case when $n=\Omega(k^{5/2})$

The next result controls ‘bad’ under the assumption that $G$ has bounded
maximum degree.

######  Lemma 5.3.

Let $n\in{\mathbb{N}},x\in[1,\infty)$ and suppose that $G$ is an $n$-vertex
graph with $n\geq 25x\cdot\Delta(G)$ and $\hom(G)\leq n/5x$. Then there is a
probability distribution $\mathcal{D}$ on $[0.1,0.9]^{V(G)}$ and a vertex set
$U\subset V(G)$ with $|U|=\lceil x\rceil+1$ such that
$\operatorname{bad}_{\mathcal{D}}({U})\leq|U|$.

###### Proof.

Set $k=\lceil x\rceil$, noting that $x\leq k<2x$. We will first select
$U=\\{u_{1},\ldots,u_{k+1}\\}$ step by step over a series of rounds. To do so,
we are going to select a ‘control’ set $Y_{i}$ for each $u_{i}\in U$, so that
$u_{i}$ is strongly joined to $Y_{i}$, but any $u_{j}\neq u_{i}$ in $U$ with
$j>i$ is quite weakly joined to $Y_{i}$. This property will allow us to
separate the expected degrees of vertices in $U$ and build the distribution
$\mathcal{D}$.

We inductively construct vertex sets $U_{i}=\\{u_{1},u_{2},\ldots,u_{i}\\}$,
$V_{i}$ and $Y_{i}$ for $i\in[k]$ so that:

  1. (i)

the sets $U_{i}$, $\\{Y_{j}\\}_{j\leq i}$ and $V_{i}$ are all pairwise
disjoint;

  2. (ii)

$u_{i}\in V_{i-1}$ for all $i\in[2,k]$;

  3. (iii)

$d^{Y_{i}}(u_{i})=|Y_{i}|=2k$;

  4. (iv)

$d^{Y_{i}}(v)\leq k/2$ for all vertices $v\in V_{i}$;

  5. (v)

$|V_{i}|\geq n-5i\Delta(G)$.

To begin, we set $U_{0}=Y_{0}=\emptyset$ and $V_{0}:=V(G)$. Suppose now
$i\in[k]$ and that we have found $U_{i-1},V_{i-1}$ and $\\{Y_{j}\\}_{j<i}$ as
above and wish to find these sets for $i$. We look at $G_{i}:=G[V_{i-1}]$ and
see that it must have a vertex $u_{i}$ with $d_{G_{i}}(u_{i})\geq 2k$; in
particular $\Delta(G)=\Delta(G_{1})\geq 2k$. If not, then $\Delta(G_{i})\leq
2k-1$ and so by Turán’s Theorem we obtain an independent set in the subgraph
$G_{i}$ which has size at least
$|V_{i-1}|/2k\geq(n-5(i-1)\Delta(G))/(2k)>(n-5x\Delta(G))/(4x)\geq n/5x$,
contradicting the $\text{hom}(G)$ condition from our hypothesis. We now let
$U_{i}:=U_{i-1}\cup\\{u_{i}\\}$ and we pick a subset $Y_{i}\subset
N_{G_{i}}(u_{i})$ of size $2k$. We then define the set $Z_{i}:=\\{v\in
V_{i-1}:d_{G_{i}}^{Y_{i}}(v)\geq k/2\\}$ and note that $u_{i}\in Z_{i}$. We
now let $V_{i}:=V_{i-1}\setminus(Y_{i}\cup Z_{i})$. Observe that by
construction (i)-(iv) hold above, and it just remains to show (v).

As $|V_{i}|=|V_{i-1}|-|Y_{i}\cup Z_{i}|$, by induction it is enough to show
that $|Y_{j}\cup Z_{j}|\leq 5\Delta(G)$. Clearly $|Y_{i}|\leq 2k$. We bound
$|Z_{i}|$ by double counting the number of edges between $Z_{i}$ and $Y_{i}$.
From each $z\in Z_{i}$ there are at least $k/2$ edges going to $Y_{i}$, hence
$e(Y_{i},Z_{i})\geq k|Z_{i}|/2$. However, from each $y\in Y_{i}$ there are at
most $\Delta(G)$ edges going to $Z_{i}$, thus $e(Y_{i},Z_{i})\leq
2k\Delta(G)$. It follows that $|Z_{i}|\leq 4\Delta(G)$ and so $|Z_{j}\cup
Y_{j}|\leq|Z_{j}|+2k\leq 4\Delta(G)+2k\leq 5\Delta(G)$, as required.

To complete the proof of the lemma, we set $i:=k$ and take $u_{k+1}\in
V_{k}\neq\emptyset$. By using (i)-(iv) above we get disjoint sets
$U=U_{k}\cup\\{u_{k+1}\\}=\\{u_{1},\ldots,u_{k+1}\\}$ and
$\\{Y_{j}\\}_{j\in[k]}$ such that:

$\displaystyle d_{Y_{i}}(u_{i})\geq d_{Y_{i}}(u_{j})+3k/2\ \ \ \text{for all
}i<j.$ (7)

For each $i\in[k]$ we let ${\cal D}_{i}$ denote the uniformly constant
distribution on $Y_{i}$, i.e. ${\cal D}_{i}:={\cal U}_{Y_{i}}$. Taking
$Y_{0}:=V(G)\setminus(\cup_{i}Y_{i})$, we also let ${\cal D}_{0}:={\cal
T}_{Y_{0}}$ denote the trivial distribution induced by the set
$Y_{0}:=V(G)\setminus(\cup_{i}Y_{i})$ (as defined at the end of Section 4).
Lastly, we take ${\cal D}$ to be the product distribution ${\cal
D}:=\prod_{i\in[0,k]}{\cal D}_{i}$ on $[0.1,0.9]^{V(G)}$. Note that from Lemma
4.1, equation (7) and Lemma 4.2, for all $i<j$ we obtain that:

$\displaystyle\operatorname{bad}_{\mathcal{D}}({u_{i},u_{j}})\leq\operatorname{bad}_{\mathcal{D}_{i}}^{Y_{i}}({u_{i},u_{j}})\leq\frac{3}{(3k/2)}=\frac{2}{k}.$

It follows that
$\operatorname{bad}_{\mathcal{D}}({U})\leq\binom{k+1}{2}\big{(}\frac{2}{k}\big{)}=|U|$,
as desired. ∎

We are now in a position to prove Theorem 5.1 for $n=\Omega(k^{5/2})$.

######  Theorem 5.4.

Let $n\in{\mathbb{N}}$ and $x\geq 1$ with $n\geq 1000x^{5/2}$. Suppose that
$G$ is an $n$-vertex graph with $\hom(G)\leq n/20x$. Then there is a
probability distribution $\mathcal{D}$ on $[0.1,0.9]^{V(G)}$ and a vertex set
$U\subset V(G)$ with $|U|\geq x+1$ such that
$\operatorname{bad}_{\mathcal{D}}({U})\leq 8|U|\log_{2}|U|$.

###### Proof.

Let $k:=\lceil x\rceil$. We will prove the theorem by induction on $|V(G)|$.
To start with, observe that there is nothing to prove when $k\leq 4$ as we can
set $\mathcal{D}$ to be any distribution on $[0.1,0.9]^{V(G)}$ and the
requirements are trivially satisfied by any $(k+1)$-vertex set $U$, since
$\operatorname{bad}_{\mathcal{D}}({u,v})\leq 1$ for any pair $u,v$ of
vertices; such a set $U$ exists as $k+1\leq 1000x^{3/2}$. In particular, this
proves that the theorem holds for the smallest possible case, when $n=1000$
(where $x$ must equal $1$). We will proceed with the induction step and assume
that $k>4$.

Let $V_{0}$ be a largest vertex set of $G$ such that
$|\operatorname{div}(u,v)|\geq 2k^{3/2}$ for all $u,v\in V_{0}$. If
$|V_{0}|\geq k+1$ then we are done by Lemma 5.2, otherwise assume that
$V_{0}=\\{v_{1},v_{2},\ldots,v_{L}\\}$ for some $L\leq k$ and now for each
$i\in[L]$ define the set $V_{i}:=\\{v\in
V(G):|\operatorname{div}(v,v_{i})|<2k^{3/2}\\}$. Due to the maximality of
$S_{0}$ we get $V(G)=\bigcup_{i=1}^{L}V_{i}$. The proof splits into two cases:

Case I: Every $j\in[L]$ with $d_{G}(v_{j})\in[{10k^{3/2}},n-1-10k^{3/2}]$
satisfies $|V_{j}|\leq 3k$.

It is easy to see that there are at most $3k^{2}$ vertices of $G$ that do not
lie in a set $V_{j}$ of size at least $3k$. Moreover,
$d_{G}(v_{i})-2k^{3/2}<d_{G}(v)<d_{G}(v_{i})+2k^{3/2}$ for all $i\in[L]$ and
$v\in V_{i}$. Thus, at least $n-3k^{2}$ vertices $v\in V(G)$ have their degree
satisfy $d_{G}(v)\notin[12k^{3/2},n-1-12k^{3/2}]$. Therefore, for all such
vertices we have $d_{G}(v)\leq 12k^{3/2}$ or $d_{G}(v)\geq n-1-12k^{3/2}$. We
will assume that at least half of these vertices fulfill the first condition,
as otherwise we can follow an identical argument by working with the
complement $\overline{G}$ instead. Consequently, we find a set $V\subset V(G)$
of size $|V|\geq(n-3k^{2})/2\geq 450x^{5/2}$ with $\Delta(G[V])\leq
12k^{3/2}$. Thus $|V|\geq 25x\Delta(G[V])$ and
$\hom(G[V])\leq\hom(G)\leq(n-6k^{2})/10x\leq|V|/5x$, hence we can apply Lemma
5.3 to $G[V]$ to obtain a distribution ${\cal D}_{1}$ on $[0.1,0.9]^{V}$ and a
vertex set $U\subset V$ of size $\lceil x\rceil+1=k+1$ with
$\operatorname{bad}_{\mathcal{D}_{1}}({U})\leq|U|$. We also take ${\cal
D}_{0}:={\cal T}_{V(G)\setminus V}$ to be the trivial distribution induced by
$V(G)\setminus V$, and let ${\cal D}:={\cal D}_{0}\times{\cal D}_{1}$ denote
the product distribution on $[0.1,0.9]^{V(G)}$. By Lemma 4.1 we obtain
$\operatorname{bad}_{\mathcal{D}}({U})\leq\operatorname{bad}_{\mathcal{D}_{1}}^{V}({U})\leq|U|$,
as required.

Case II: There is $j\in[L]$ such that
$d_{G}(v_{j})\in[10k^{3/2},n-1-10k^{3/2}]$ and $|V_{j}|\geq 3k$.

We pick a subset $V$ of $V_{j}$ of size $3k$ such that $v_{j}\in V$. Next, we
set ${X_{1}}:=N(v_{j})\setminus V$ and ${X_{2}}=:V(G)\setminus(V\cup
N(v_{j}))$. By the choice of $v_{j}$ note that both $|{X_{1}}|,|{X_{2}}|\geq
10k^{3/2}-3k$. Our aim is to show that most vertices in ${X_{1}}$ have big
degree in $V$, whereas most vertices in ${X_{2}}$ have small degree in $V$.
This will allow us to separate the distinct degrees we get in $G[{X_{1}}]$
from those we get in $G[{X_{2}}]$. This clustering behaviour is illustrated in
the picture below.

Figure 1: The clustering behaviour of vertices according to their degree in
$V$.

To show that this split occurs, we double count the edges in $\overline{G}$
between $X_{1}$ and $V$. Recall that $X_{1}\subset N(v_{j})$ and for each
$v\in V$ we have $|\operatorname{div}(v,v_{j})|\leq 2k^{3/2}$, so each $v\in
V$ gives at most $2k^{3/2}$ edges from itself to $X_{1}$. Hence the number of
edges $e_{\hskip 0.85358pt\overline{G}}(X_{1},V)\leq(3k)(2k^{3/2})=6k^{5/2}$.
It follows that there are at most $6k^{3/2}$ vertices of $X_{1}$ that are
connected to less than $2k$ vertices in $V$. Thus, if we let $Y_{1}:=\\{u\in
X_{1}:d_{G}^{V}(u)\geq 2k\\}$ we see that
$t_{1}:=|Y_{1}|\geq|X_{1}|-6k^{3/2}\geq 4k^{3/2}-3k>10.$
Similarly, we double count the edges in $G$ between $X_{2}$ and $V$ to see
that there are at most $6k^{5/2}$ of them. It follows that at most $6k^{3/2}$
vertices of $X_{2}$ that are connected to more than $k$ vertices in $V$.
Therefore, if we let $Y_{2}:=\\{u\in{X_{2}}:d_{G}^{V}(u)\leq k\\}$, then we
can also see that $t_{2}:=|Y_{2}|\geq|X_{2}|-6k^{3/2}>4k^{3/2}-3k>10$.
Recalling that $V(G)=V\cup X_{1}\cup{X_{2}}$ is a partition, this shows that
$Z:=V(G)\setminus(Y_{1}\cup Y_{2})$ satisfies $|Z|\leq 2\cdot 6k^{3/2}+3k\leq
15k^{3/2}$.

To complete the proof, we apply the induction hypothesis to both $Y_{1}$ and
$Y_{2}$. For $i\in\\{1,2\\}$ let $x_{i}:=x(t_{i}/n)\leq x$. This gives
$\hom(G[Y_{i}])\leq\hom(G)\leq n/20x=t_{i}/20x_{i}$. Furthermore:

$\displaystyle\frac{t_{i}}{x_{i}^{5/2}}=\frac{1}{x_{i}^{3/2}}\cdot\frac{t_{i}}{x_{i}}=\frac{1}{x_{i}^{3/2}}\cdot\frac{n}{x}\geq\frac{n}{x^{5/2}}\geq
1000.$

Thus, for $i\in\\{1,2\\}$, provided $x_{i}\geq 1$ holds, we can apply the
induction hypothesis to $G[Y_{i}]$ to find a probability distribution
$\mathcal{D}_{i}$ on $[0.1,0.9]^{Y_{i}}$ and a set $U_{i}\subset Y_{i}$
satisfying $|U_{i}|\geq x_{i}+1$ and:

$\displaystyle\operatorname{bad}_{\mathcal{D}_{i}}({U_{i}})\leq|U_{i}|\cdot
f(|U_{i}|),\ \ \ \text{where }f(y):=8\log_{2}y.$ (8)

Also note that if instead $x_{i}<1$ above, then as $|Y_{i}|=t_{i}\geq 10$, we
can take any set $U_{i}\subset Y_{i}$ of order $\lceil x_{i}\rceil+1=2$ and
any distribution ${\cal D}_{i}$ on $[0.1,0.9]^{Y_{i}}$, so (8) holds in all
cases.
We can also assume that $\max\\{|U_{1}|,|U_{2}|\\}<k+1$, as otherwise taking
$U$ to simply be one of these sets proves the theorem.

We will also let ${\cal D}_{0}:={\cal U}_{V}$ denote the uniformly constant
distribution on $[0.1,0.9]^{V}$ and let ${\cal D}_{3}:={\cal T}_{Z}$ denote
the trivial $Z$-induced distribution. We now set $U:=U_{1}\cup U_{2}$ and let
${\cal D}$ denote the product distribution $\prod^{3}_{i=0}{\cal D}_{i}$ on
$[0.1,0.9]^{V}\times\prod_{i\in[2]}[0.1,0.9]^{Y_{i}}\times[0.1,0.9]^{Z}=[0.1,0.9]^{V(G)}$.

Note that $d^{V}_{G}(u)\geq 2k\geq d_{G}^{V}(v)+k$ for all $u\in Y_{1}$ and
$v\in Y_{2}$, by definition of $Y_{1}$ and $Y_{2}$. It then follows from Lemma
4.2 that for all such vertices we have:

$\displaystyle\operatorname{bad}_{\mathcal{D}_{0}}^{V}({u,v})\leq\frac{3}{k}.$
(9)

As $n\geq 1000x^{5/2}$ and $|Z|\leq 15k^{3/2}$, we can now lower bound the
size of $U$:

$\displaystyle|U|=|U_{1}|+|U_{2}|$ $\displaystyle\geq(x_{1}+1)+(x_{2}+1)\geq
x\bigg{(}\frac{t_{1}}{n}\bigg{)}+x\bigg{(}\frac{t_{2}}{n}\bigg{)}+2$
$\displaystyle\geq\frac{(n-|Z|)x}{n}+2\geq x-\frac{15x\cdot k^{3/2}}{n}+2\geq
x+1,$

which gives $|U|\geq x+1$. Finally, we are able to estimate
$\operatorname{bad}_{\mathcal{D}}({U})$ as follows:

$\displaystyle\operatorname{bad}_{\mathcal{D}}({U})$
$\displaystyle=\sum_{\\{u,v\\}\subset
U_{1}}\operatorname{bad}_{\mathcal{D}}({u,v})+\sum_{\\{u,v\\}\subset
U_{2}}\operatorname{bad}_{\mathcal{D}}({u,v})+\sum_{(u,v)\in U_{1}\times
U_{2}}\operatorname{bad}_{\mathcal{D}}({u,v})$
$\displaystyle=\operatorname{bad}_{\mathcal{D}}({U_{1}})+\operatorname{bad}_{\mathcal{D}}({U_{2}})+|U_{1}||U_{2}|\cdot\max_{(u,v)\in
U_{1}\times U_{2}}\big{\\{}\operatorname{bad}_{\mathcal{D}}({u,v})\big{\\}}$
$\displaystyle\leq\operatorname{bad}_{\mathcal{D}_{1}}({U_{1}})+\operatorname{bad}_{\mathcal{D}_{2}}({U_{2}})+|U_{1}||U_{2}|\cdot\max_{(u,v)\in
U_{1}\times
U_{2}}\big{\\{}\operatorname{bad}_{\mathcal{D}_{0}}^{V}({u,v})\big{\\}}$
$\displaystyle\leq|U_{1}|\cdot f(|U_{1}|)+|U_{2}|\cdot
f(|U_{2}|)+\frac{3}{k}\cdot|U_{1}||U_{2}|\leq|U|\cdot f(|U|).$

The final three inequalities here respectively follow from Lemma 4.1, then
from (8) and (9), and lastly from $\max\\{|U_{1}|,|U_{2}|\\}<k+1$ and Lemma
2.5. This completes the proof. ∎

###  5.2 The case when $n=O(k^{5/2})$

Before we move to the case when $n=O(k^{5/2})$, we present two results which
will allow us to move to a large induced subgraph, which is reasonably
regular. Comparable results, with a different range of parameters, were proved
by Alon, Krivelevich and Sudakov in [3] (Section 2). The next lemmas follow
their approach. We first introduce the following notion.

######  Definition 5.5.

For every $n$-vertex graph $G$, its average degree, denoted by
$\overline{d}(G)$, is given by the formula $\overline{d}(G):=n^{-1}\sum_{v\in
V(G)}d_{G}(v)$.

######  Lemma 5.6.

Every $n$-vertex graph $G$ contains an induced subgraph $H$ of order at least
$n/3$ such that $\Delta(H)\leq 2\log_{2}n\cdot\overline{d}(H)$.

###### Proof.

We set $G_{0}:=G$ and for $i=0$ to $i=\log_{2}n$ we repeat the following
algorithm: first set $n_{i}:=|V(G_{i})|,\ \Delta_{i}:=\Delta(G_{i})$ and
$d_{i}:=\overline{d}(G_{i})$. Then, if $\Delta_{i}\leq 2d_{i}\log_{2}n$ we
simply stop the process. Otherwise we repeatedly delete from $G_{i}$ all
vertices of degree at least $d_{i}\log_{2}n$ to create a new graph $G_{i+1}$.
Let $H$ be the graph we obtain after we complete the algorithm.
Observe that at $i^{\text{th}}$ iteration we delete at most
$e(G_{i})/(d_{i}\log_{2}n)=n_{i}/(2\log_{2}n)$ vertices, therefore
$n_{i+1}\geq n_{i}(1-(2\log_{2}n)^{-1})$. It follows that $|V(H)|\geq
n\cdot(1-(2\log_{2}n)^{-1})^{\log_{2}n}$. As $1-x\geq e^{-2x}$ for $0<x\leq
1/2$, we deduce that $|V(H)|\geq n/e>n/3$.
If $H$ was created because at some point $\Delta_{i}\leq 2d_{i}\log_{2}n$ then
we are done. Otherwise $H$ was obtained after $\log_{2}n$ iterations and at
each step $i$ we have $\Delta_{i+1}\leq d_{i}\log_{2}n$ and
$2d_{i}\log_{2}n\leq\Delta_{i}$. Thus we see that
$\Delta_{i+1}\leq\Delta_{i}/2$. It follows inductively that
$\Delta(H)\leq\Delta(G)\cdot 2^{-\log_{2}n}<n\cdot n^{-1}=1$. We then get that
$\Delta(H)=\overline{d}(H)=0$, which also ends the solution. ∎

######  Lemma 5.7.

Every $n$-vertex graph $G$ contains an induced subgraph $H$ that is of order
at least $n/30\log_{2}n$ with $\Delta(H)\leq 5\log_{2}n\cdot\delta(H)$.

###### Proof.

By the previous lemma we can find an induced subgraph $G_{0}$ of $G$ of order
$m\geq n/3$ such that $\Delta(G_{0})\leq 2\log_{2}n\cdot\overline{d}(G_{0})$.
We now perform the following algorithm: starting with $i=0$, let
$d_{i}:=\overline{d}(G_{i})$ and delete a vertex $v$ of $G_{i}$ if
$5d_{G_{i}}(v)<2d_{i}$. Let now $G_{i+1}$ be the resulting graph and increment
$i$. Note that at each step we remove from $G_{i}$ at most $2d_{i}/5$ edges,
which implies that $d_{i+1}|G_{i+1}|\geq
d_{i}|G_{i}|-4d_{i}/5>d_{i}(|G_{i}|-1)$, thus $(d_{i})_{i\geq 0}$ is an
increasing sequence. Therefore we stop before deleting all the vertices and we
let $H$ be the resulting graph.
We can now observe that $\Delta(H)\leq\Delta(G_{0})$ and $\delta(H)\geq
2d_{0}/5$, which immediately implies that $\Delta(H)\leq\Delta(G_{0})\leq
2d_{0}\log_{2}n\leq 5\log_{2}n\cdot\delta(H)$. We finally have to lower bound
the number $t$ of vertices that are left in $H$. When we created $H$ from
$G_{0}$ we deleted less than $2(m-t)d_{0}/5$ edges, hence
$2td_{0}\log_{2}n\geq t\Delta(H)\geq t\overline{d}(H)\geq
md_{0}-4(m-t)d_{0}/5$. By rearranging the last inequality we obtain $t\geq
m/(10\log_{2}n)\geq n/(30\log_{2}n)$ and so $H$ is the required induced
subgraph. ∎

We are interested in finding sets that have many diverse pairs of vertices as
they will give us the freedom required to select vertices with distinct
degrees. We thus make the following:

######  Definition 5.8.

Given a graph $G$ and $\varepsilon>0$, its _diversity graph_
$J_{\varepsilon}(G)$ is the graph on $V(G)$ with an edge between vertices $u$
and $v$ if $|N_{G}(u)\triangle
N_{G}(v)|\leq\varepsilon\min\\{|N_{G}(u)|,|N_{G}(v)|\\}$.

The following theorem is the main component of our proof in this case. We note
that our earlier results from Subsection 5.1 will be crucial here.

######  Theorem 5.9.

Let $G$ be a $n$-vertex graph and let $k\in\mathbb{N}$ be such that
$1000k^{5/2}\geq n\geq 8000k^{2}$, $\text{hom}(G)\leq n/12k$ and
$\Delta(G)\leq 4nk^{-1/3}$. There is a probability distribution $\mathcal{D}$
on $[0.1,0.9]^{V(G)}$ and a vertex set $U\subset V(G)$ with
$|U|=\Omega\big{(}k\log_{2}^{-2}(k+1)\big{)}$ and
$\operatorname{bad}_{\mathcal{D}}({U})\leq 8|U|\log_{2}|U|$.

###### Proof.

We first note that if $k$ is small then there is nothing to prove, so we can
assume $k>2^{40}$. Moreover, together with the hypothesis this gives:

$\displaystyle 20+4\log_{2}k\leq 2\log_{2}n\leq
20+5\log_{2}k\leq(5.5)\log_{2}k\leq k/100.$ (10)

Next, we apply Lemma 5.7 to find an induced subgraph $H$ of $G$ of order
$m\geq n\log_{2}^{-1}n/30$ with $\Delta(H)\leq 5\log_{2}n\cdot\delta(H)$. From
now on we will only work with this subgraph $H$. Notice that $\Delta(H)\geq
k\log_{2}^{-1}n/10$, as otherwise by Turán’s Theorem, combined with (10), we
find an independent set in $H$ (and so in $G$) of order at least
$m/(\Delta(H)+1)\geq n(3k+30\log_{2}n)^{-1}>n/4k$, contradicting the
hypothesis.

Take $J$ to denote the diversity graph $J:=J_{\varepsilon}(H)$, where
$\varepsilon=1/48$. We then set:

$\displaystyle S_{1}:=\bigg{\\{}v\in
V(H):d_{J}(v)\leq\frac{m}{600k}\bigg{\\}}\quad\mbox{and}\quad
S_{2}:=V(H)\setminus S_{1}.$

Our proof will split according to the sizes of $S_{1}$ and $S_{2}$.

CASE 1: $|S_{1}|\geq m/2$.

We will show that in this scenario we can take the desired set $U\subset
S_{1}$. We select a set $W\subset S_{1}$ by including every element of $S_{1}$
independently with probability $p:=8k/|S_{1}|$.
We now claim that each of the following events holds with probability at least
$3/4$:

  1. (i)

$|W|\geq 4k$ ;

  2. (ii)

$e(J[W])\leq k$ ;

  3. (iii)

$d^{W}_{H}(v)\leq 2\log_{2}n\cdot m_{\Delta}$ for all $v\in V(H)$, where
$m_{\Delta}:=\max\\{1,240\cdot\Delta(H)\cdot k/n\\}$.

To prove the claim for (i)$-$(iii) above, let us first denote by
$\mathcal{A}_{i},\mathcal{A}_{ii}$ and $\mathcal{A}_{iii}$ the events that
$|W|\leq 4k$, $e(J[W])\leq 2k$ and $d^{W}_{H}(v)\geq 2\log n\cdot m_{\Delta}$,
respectively.
Starting with (i), note that $|W|\sim Bin(|S_{1}|,p)$ with
$\mathbb{E}[|U|]=p|S_{1}|=8k$, therefore by Chernoff’s Inequality we get
$\mathbb{P}({\cal A}_{i})=\mathbb{P}\big{(}|W|\leq 4k\big{)}\leq\exp(-k)<1/4$,
proving it for (i).
For (ii) observe that $\mathbb{E}[e(J[U])]\leq p^{2}e(J[S_{1}])\leq
p^{2}|S_{1}|(m/600k)\leq 64km/600|S_{1}|\leq k/4$. From Markov’s inequality we
get ${\mathbb{P}}({\cal A}_{ii})={\mathbb{P}}(e_{J}[U]\geq k)\leq 1/4$, which
gives us (ii).
Lastly, for (iii) take $v\in V(H)$ and let $n_{v}:=d^{S_{1}}(v)$. Then note
that $d_{H}^{W}(v)\sim Bin(n_{v},p)$. Now Theorem 2.7 gives
$\mathbb{P}\big{(}d_{H}^{W}(v)\geq 2m_{v}\log_{2}n\big{)}\leq
2^{-2\log_{2}n}=n^{-2}$, where $m_{v}:=\max\\{1,240n_{v}k/n\\}$. As
$m_{\Delta}\geq m_{v}$ for all $v\in V(H)$, the union bound gives
${\mathbb{P}}({\cal A}_{iii})\leq n^{-1}<1/4$.

Combining the above bounds gives us
$\mathbb{P}(\mathcal{A}_{i})+\mathbb{P}(\mathcal{A}_{ii})+\mathbb{P}(\mathcal{A}_{iii})\leq
3/4$. Therefore, by using the union bound we can choose a set $W\subset S_{1}$
that satisfies all the conditions in (i)$-$(iii).

To continue the proof in this case, note that by (i) and (ii) we can apply
Turán’s theorem to $J[W]$ to find an independent set $U_{0}\subset W$ with
$|U_{0}|=2k+1$. However, this means that $U_{0}$ is
$\big{(}\delta(H)/48\big{)}$-diverse to $V(H)$. By (iii) the set $U_{0}$ is
$\gamma$-balanced to $V(H)$, where $\gamma:=\log_{2}n\cdot m_{\Delta}/k$.
Letting ${\cal D}:={\cal B}_{\beta}(U_{0},V(H))$ denote the blended
probability distribution on $[0.1,0.9]^{V(H)}$, by applying Lemma 4.3 with
$\beta^{-1}:=10\log_{2}n\sqrt{m_{\Delta}}$ we obtain that for all distinct
$u,v\in U_{0}$:

$\operatorname{bad}_{\mathcal{D}}({u,v})\leq\frac{960\log_{2}n\sqrt{m_{\Delta}}}{\delta(H)}+\frac{\delta(H)}{48}\exp\left(\frac{-4.5\cdot
m_{\Delta}\log_{2}^{2}n}{2m_{\Delta}\log_{2}n}\right).$

By noting that $\Delta:=\Delta(H)\leq 5\log_{2}n\cdot\delta(H)$, this can be
further reduced to:

$\operatorname{bad}_{\mathcal{D}}({u,v})\leq\frac{12\cdot(20\log_{2}n)^{2}\cdot\sqrt{m_{\Delta}}}{\Delta}+\frac{\delta(H)}{48n^{2}}.$

Our next claim is that $\Delta^{-1}\sqrt{m_{\Delta}}<28kn^{-1}\log_{2}k$.
Indeed, on the one hand, when $m_{\Delta}=1$ then
$\Delta^{-1}\sqrt{m_{\Delta}}\leq\Delta^{-1}\leq
10kn^{-1}\log_{2}n<28kn^{-1}\log_{2}k$ by (10), as required. On the other
hand, $m_{\Delta}\geq 1$ implies $\Delta^{-1}\leq 240kn^{-1}$ and so
$\Delta^{-1}\sqrt{m_{\Delta}}\leq\sqrt{240k/(n\Delta)}\leq
240kn^{-1}<28kn^{-1}\log_{2}k$, which proves the claim.
Recall that $\log_{2}n\leq 3\log_{2}k$ by (10) and that $n\geq 8000k^{2}$ and
$\delta(H)<n$. Therefore, we can deduce that for all distinct $u,v\in U_{0}$
we have:

$\displaystyle\operatorname{bad}_{\mathcal{D}}({u,v})\leq
12\cdot(60\log_{2}k)^{2}\cdot\frac{28k\log_{2}k}{n}+\frac{1}{10^{5}k^{2}}\leq\frac{10^{3}(\log_{2}k)^{3}}{k}.$

To complete the proof in this case, we choose a subset $U\subset U_{0}$ of
size $10^{-3}k\log_{2}^{-2}k\geq k^{1/4}$. It follows that
$\operatorname{bad}_{\mathcal{D}}({u,v})\leq 16|U|^{-1}\log_{2}|U|\ \
\text{for all }u,v\in U.$
By summing over all pairs of distinct vertices in $U$, it immediately follows,
as required, that:

$\operatorname{bad}_{\mathcal{D}}({U})\leq\frac{16\log_{2}|U|}{|U|}\cdot\dbinom{|U|}{2}=8|U|\log_{2}|U|.$

CASE 2: $|S_{2}|\geq m/2$.

Our first step here is to find a set $W\subset S_{2}$ and for each vertex
$w\in W$ two sets $S_{w},T_{w}\subset V(H)$ with the following properties:

  1. (i)

$|W|\geq|S_{2}|/16\Delta(H)$;

  2. (ii)

$S_{w}\subset N_{H}(w)$ and $|S_{w}|\geq|N_{H}(w)|/2$ for each $w\in W$;

  3. (iii)

$S_{w}\cap N_{H}(w^{\prime})=\emptyset$ for all distinct $w,w^{\prime}\in W$;

  4. (iv)

$T_{w}\subset N_{J}(w)$ with $|T_{w}|=t:=2^{-19}\cdot 9k\log_{2}^{-2}k$ for
all $w\in W$.

With these sets in hand, our set $U$ will (roughly) be of the form
$U=\bigcup_{w\in W}U_{w}$, where each $U_{w}$ is a set produced by applying
Theorem 5.4 to $S_{w}\subset N_{H}(w)$, while the sets $T_{w}$ will be used to
establish ‘bad’ control between vertices in distinct $U_{w}$.

As the following diagram suggests, our partition is guided by the
neighbourhoods of vertices in the set $W=\\{w_{i}\\}_{i}$. The high
‘$J$-degree’ of vertices in $S_{2}$ guarantees a strong clustering behaviour,
so that each vertex $w_{i}$ has a large set $T_{w_{i}}$ of vertices which
behave very similarly. These sets can be used to obtain ‘bad’ control between
vertices in distinct $S_{w_{i}}$.

Figure 2: The clusters formed around each $w\in W$.

We now proceed with the details. To begin, select a set $W_{0}\subset S_{2}$
by including each element independently with probability $p:=1/8\Delta$, where
$\Delta:=\Delta(H)$. For each $w\in W_{0}$ we set:

$\displaystyle S_{w}:=\big{\\{}v\in V(H):N_{H}(v)\cap W_{0}=\\{w\\}\big{\\}}.$

We then let $W\subset W_{0}$ be the set $W:=\\{w\in
W_{0}:|S_{w}|\geq|N_{H}(w)|/2\\}$. Lastly, each $w\in W$ is also an element of
$S_{2}$, by definition, so we have $d_{J}(w)\geq m/600k>t$. We take $T_{w}$ to
be an arbitrary subset of size $t$ from $N_{J}(w)$.

Having specified the sets, it remains to show that with positive probability
properties (i)$-$(iv) hold for our choices. To see this, note that (ii) holds
by definition of $S_{w}$ and $W$. Property (iii) also always holds as if $v\in
S_{w}\cap N_{H}(w^{\prime})$ then $v\in N_{H}(w)\cap N_{H}(w^{\prime})$ and
$\\{w,w^{\prime}\\}\subset N_{H}(v)\cap W_{0}$, which by definition of $S_{w}$
implies $w=w^{\prime}$. Lastly (iv) immediately holds by construction.
It only remains to prove that (i) holds with positive probability. To see
this, note that given $w\in S_{2}$ and $v\in N(w)$ we have:

$\mathbb{P}\big{(}v\in S_{w}\big{|}w\in
W_{0}\big{)}=(1-p)^{d^{S_{2}}_{H}(v)-1}>(1-p)^{\Delta}\geq
e^{-2p\Delta}=e^{-1/4}.$

Thus $\mathbb{P}(v\notin S_{w}|w\in W_{0})\leq 1-e^{-1/4}\leq 1/4$ and so
$\mathbb{E}\big{[}|N(w)\setminus S_{w}|\big{|}w\in W_{0}\big{]}\leq|N(w)|/4$.
It follows from Markov’s inequality that:

${\mathbb{P}}(w\notin W|w\in W_{0})=\mathbb{P}\big{(}|N(w)\setminus
S_{w}|\geq|N(w)|/2\big{|}w\in W_{0}\big{)}\leq 1/2.$

We can now further deduce that:

${\mathbb{E}}\big{[}|W_{0}\setminus W|\big{]}=\sum_{w\in
S_{2}}{\mathbb{P}}(w\notin W|w\in W_{0})\cdot{\mathbb{P}}(w\in
W_{0})\leq{\mathbb{E}}\big{[}|W_{0}|\big{]}/2=|S_{2}|p/2,$

since ${\mathbb{E}}[|W_{0}|]=|S_{2}|p$ because
$|W_{0}|\sim\mbox{Bin}(|S_{2}|,p)$. It follows that
${\mathbb{E}}[|W|]={\mathbb{E}}[|W_{0}|-|W_{0}\setminus
W|]\geq|S_{2}|p/2=|S_{2}|/16\Delta$. Thus we can fix a choice of $W$ so that
(i), and hence (i)$-$(iv), are satisfied.

Our current aim is to find distinct expected degrees in each subgraph
$G[S_{w}]$ with $w\in W$ by appealing to Theorem 5.4 and to use the control
sets $\\{T_{w}\\}_{w\in W}$ that ensure we can control the degrees between the
different sets, so that we can find our required set $U$ in $\bigcup_{w\in
W}S_{w}$.
To proceed with this, first observe that the sets $\\{S_{w}\\}_{w\in W}$ are
pairwise disjoint, since for distinct $w,w^{\prime}\in W$ we have $S_{w}\cap
S_{w^{\prime}}\subset S_{w}\cap N_{H}(w^{\prime})=\emptyset$ by (ii) and
(iii).
Next, notice that the sets $\\{T_{w}\\}_{w\in W}$ are also pairwise disjoint.
Indeed, suppose there is some $v\in T_{w_{1}}\cap T_{w_{2}}$ for some distinct
$w_{1},w_{2}\in W$ and assume $|N(w_{1})|\leq|N(w_{2})|$. Let
$S_{v}:=S_{w_{2}}\cap N(v)$ and $\overline{S_{v}}:=S_{w_{2}}\setminus N(v)$.
As $v\sim w_{1}$ in $J$, $N_{H}(w_{1})\cap S_{w_{2}}=\emptyset$ and
$S_{w_{2}}\subset N_{H}(w_{2})$, we immediately see that
$|S_{v}|\leq\varepsilon|N(w_{1})|\leq\varepsilon|N(w_{2})|$. However $v\sim
w_{2}$ in $J$, thus $|\overline{S_{v}}|\leq\varepsilon|N(w_{2})|$. It follows
that $|N(w_{2})|/2\leq|S_{w_{2}}|=|S_{v}|+|\overline{S_{v}}|\leq
2\varepsilon|N(w_{2})|=|N(w_{2})|/24$, which is a contradiction. Therefore
$T_{w_{1}}\cap T_{w_{2}}=\emptyset$ for any $w_{1}\neq w_{2}$ in $W$.

We want to ensure that vertices of $S_{w}$ have high degree in $T_{w}$,
whereas their degree in $T_{w^{\prime}}$ with $w^{\prime}\neq w$ is low. Given
$w\in W$ we define:

$\displaystyle R_{w}:=\big{\\{}v\in\bigcup_{w^{\prime}\neq
w}S_{w^{\prime}}:d_{H}^{T_{w}}(v)\geq t/3\big{\\}},\qquad\mbox{and}\qquad
L_{w}:=\big{\\{}v\in S_{w}:d_{H}^{T_{w}}(v)\leq 2t/3\big{\\}}.$

If we count the non-edges between $S_{w}$ and $T_{w}$ we see there are at
least $(t/3)|L_{w}|$ of them, whereas their number is at most
$t(\varepsilon|N(w)|)$ since each vertex of $T_{w}$ is connected to $w$ in
$J$. It follows that $|L_{w}|\leq 3\varepsilon|N(w)|\leq
3\varepsilon(2|S_{w}|)\leq|S_{w}|/8$, using (ii) above and that
$\varepsilon=1/48$. Similarly, by double counting the edges between
$\bigcup_{w^{\prime}\neq w}S_{w^{\prime}}$ and $T_{w}$ we obtain
$|R_{w}|\leq|S_{w}|/8$.

We now set $S^{\prime}_{w}:=S_{w}\setminus\bigcup_{v\in W}(L_{v}\cup R_{v}\cup
T_{v})\subset S_{w}$ for each $w\in W$. Discarding elements if necessary, we
may assume that $|S^{\prime}_{w}|>1$ for all $w\in W$. As the sets
$\\{S_{w}\\}_{w\in W}$ are pairwise disjoint, this also holds for
$\\{S_{w}^{\prime}\\}_{w\in W}$. From our bounds above we find that:

$\displaystyle\big{|}\bigsqcup_{w\in
W}S^{\prime}_{w}\big{|}\geq\big{|}\bigsqcup_{w\in
W}S_{w}\big{|}-\big{|}\bigcup_{v\in W}(L_{v}\cup R_{v}\cup
T_{v})\big{|}-\big{|}W\big{|}$ $\displaystyle\geq\sum_{w\in
W}\big{(}|S_{w}|-|L_{w}|-|R_{w}|-|T_{w}|-1\big{)}$
$\displaystyle\geq\sum_{w\in W}\big{(}|S_{w}|-|S_{w}|/4-t-1\big{)}$
$\displaystyle\geq\sum_{w\in W}\frac{|S_{w}|}{2}\geq|W|\frac{\delta(G)}{4}.$

The second inequality here comes from $|L_{w}|,|R_{w}|\leq|S_{w}|/8$, whereas
the third one uses that:

$1+t:=1+\frac{9k}{2^{19}\log_{2}^{2}k}\overset{\eqref{eqn:log-
corres}}{\leq}\frac{k}{400\log_{2}^{2}n}\leq\frac{\Delta(H)}{40\log_{2}n}\leq\frac{\delta(H)}{8}\leq\frac{|S_{w}|}{4}.$

The final inequality above comes from (ii). Continuing with the previous
expression, using that $\delta(H)\geq\Delta/(5\log_{2}n)$ and that, by
property (i), $|W|\geq|S_{2}|/16\Delta\geq m/32\Delta$, we obtain:

$\displaystyle\sum_{w\in
W}\big{|}S^{\prime}_{w}\big{|}\geq\frac{|W|\delta(G)}{4}\geq\bigg{(}\frac{|S_{2}|}{16\Delta}\bigg{)}\bigg{(}\frac{\Delta}{20\log_{2}n}\bigg{)}=\frac{m}{640\log_{2}n}\geq\frac{n}{2^{15}\log_{2}^{2}n}.$
(11)

We are now in good position to find the desired set $U$. To do this, our main
aim is to apply Theorem 5.4 to each graph $G[S_{w}^{\prime}]$. With this in
mind, for each $w\in W$ let $k_{w}:=|S^{\prime}_{w}|k/n$, and note that
$|S_{w}^{\prime}|/k_{w}=n/k$. Also recall that
$|S^{\prime}_{w}|\leq|N_{H}(w)|\leq\Delta\leq 4nk^{-1/3}$, hence:

$\displaystyle\frac{|S^{\prime}_{w}|}{k_{w}^{5/2}}=\frac{|S^{\prime}_{w}|}{(|S_{w}^{\prime}|k/n)^{5/2}}=\frac{n^{5/2}}{k^{5/2}|S^{\prime}_{w}|^{3/2}}\geq\frac{n^{5/2}}{k^{5/2}\cdot\Delta^{3/2}}\geq\frac{n^{5/2}}{k^{5/2}(4nk^{-1/3})^{3/2}}=\frac{n}{8k^{2}}\geq
1000.$

We also have $\hom(G[S^{\prime}_{w}])\leq\hom(G)\leq
n/12k=|S_{w}^{\prime}|/12k_{w}$. Thus for each $w\in W$, provided $k_{w}\geq
1$, we can apply Theorem 5.4 to $G[S^{\prime}_{w}]$ to obtain a set
$U_{w}\subset S^{\prime}_{w}$ with $|U_{w}|\geq k_{w}+1$ and a probability
distribution $\mathcal{D}_{w}$ on $[0.1,0.9]^{S^{\prime}_{w}}$ such that:

$\displaystyle\operatorname{bad}_{\mathcal{D}_{w}}^{S^{\prime}_{w}}({U_{w}})\leq|U_{w}|\cdot
f(|U_{w}|),\ \ \ \text{where }f(x):=8\log_{2}x.$ (12)

As in the proof of Theorem 5.4, if $k_{w}\leq 1$ then any set $U_{w}\subset
S^{\prime}_{w}$ of size $2\geq k_{i}+1$ trivially satisfies (12), thus the
above computations all make sense.

We now set $U:=\bigcup_{w\in W}U_{w}$ and $S^{\prime}:=\bigcup_{w\in
W}S^{\prime}_{w}$. Our distribution ${\cal D}$ will again be a product
distribution, with ${\cal D}_{w}$ the forming factors. For each $w\in W$ we
also take ${\cal E}_{w}$ to denote the uniformly constant distribution on
$T_{w}$ given by ${\cal E}_{w}:={\cal U}_{T_{w}}$ and set $T:=\cup_{w\in
W}T_{w}$. We note that given distinct $w,w^{\prime}\in W$ and $u\in U_{w}$,
$u^{\prime}\in U_{w^{\prime}}$ we have $d_{H}^{T_{w}}(u)\geq 2t/3\geq
d_{H}^{T_{w}}(u^{\prime})+t/3$. Therefore, by the choice of ${\cal E}_{w}$ and
from Lemma 4.2 we find that:

$\displaystyle\operatorname{bad}_{\mathcal{\cal
E}_{w}}^{T_{w}}({u,u^{\prime}})\leq 9/t.$ (13)

We also let ${\cal T}_{R}$ denote the trivial $R$-induced distribution, where
$R:=V(G)\setminus(S^{\prime}\cup T)$. Let ${\cal D}$ be the product
distribution on
$[0.1,0.9]^{S^{\prime}}\times[0.1,0.9]^{T}\times[0.1,0.9]^{R}=[0.1,0.9]^{V(G)}$
below:

$\displaystyle{\cal D}:=\big{(}\prod_{w\in W}{\cal
D}_{w}\big{)}\times\big{(}\prod_{w\in W}{\cal E}_{w}\big{)}\times{\cal
T}_{R}.$

To complete the proof, we are only left to lower bound $|U|$ and upper bound
$\operatorname{bad}_{\mathcal{D}}({U})$. For the lower bound, using (11) and
that $\log_{2}n\leq 2\sqrt{2}\log_{2}k$ from (10), we obtain:

$\displaystyle|U|=\sum_{w\in W}\big{|}U_{w}\big{|}\geq\sum_{w\in
W}k_{w}\geq\sum_{w\in
W}|S_{w}^{\prime}|\cdot\frac{k}{n}=\frac{k}{n}\bigg{(}\big{|}\bigcup_{w\in
W}S_{w}^{\prime}\big{|}\bigg{)}\geq\frac{k}{2^{19}\log^{2}k}=\frac{t}{9}.$

For the upper bound on $\operatorname{bad}_{\mathcal{D}}({U})$, we have:

$\displaystyle\operatorname{bad}_{\mathcal{D}}({U})$ $\displaystyle=\sum_{w\in
W}\operatorname{bad}_{\mathcal{D}}({U_{w}})+\sum_{\\{w,w^{\prime}\\}\subset
W}\operatorname{bad}_{\mathcal{D}}({U_{w},U_{w^{\prime}}})$
$\displaystyle\leq\sum_{w\in W}\operatorname{bad}_{\mathcal{\cal
D}_{w}}^{S_{w}^{\prime}}({U_{w}})+\sum_{\\{w,w^{\prime}\\}\subset
W}\operatorname{bad}_{\mathcal{\cal E}_{w}}^{T_{w}}({U_{w},U_{w^{\prime}}})$
$\displaystyle\leq\sum_{w\in W}\operatorname{bad}_{\mathcal{\cal
D}_{w}}^{S_{w}^{\prime}}({U_{w}})+\sum_{\\{w,w^{\prime}\\}\subset
W}|U_{w}|\cdot|U_{w^{\prime}}|\cdot\max_{(u,u^{\prime})\in U_{w}\times
U_{w^{\prime}}}\operatorname{bad}_{\mathcal{\cal
E}_{w}}^{T_{w}}({u_{w},u_{w^{\prime}}})$ $\displaystyle\leq\sum_{w\in
W}|U_{w}|\cdot f(|U_{w}|)+\sum_{\\{w,w^{\prime}\\}\subset
W}|U_{w}|\cdot|U_{w^{\prime}}|\cdot\bigg{(}\frac{9}{t}\bigg{)}.$

The first inequality here follows Lemma 4.1, the second is immediate from the
definition of $\operatorname{bad}_{\mathcal{D}}^{S}({U,V})$, whereas the third
one holds by (12) and (13).

Choose a smallest subset $W^{\prime}:=\\{w_{1},\ldots,w_{M}\\}$ of $W$ so that
$|\bigsqcup_{w\in W^{\prime}}U_{w}|\geq t/9$. If $W^{\prime}=\\{w^{\prime}\\}$
for some $w^{\prime}\in W$ then we are done by simply taking
$U=U_{w^{\prime}}$ since
$\operatorname{bad}_{\mathcal{D}}({U_{w^{\prime}}})\leq|U_{w^{\prime}}|f(|U_{w^{\prime}}|)$.
Otherwise we can assume that the sequence $U_{i}:=U_{w_{i}}$ is non-increasing
in size with $i$, i.e. that $|U_{1}|\geq|U_{2}|\geq...\geq|U_{M}|$. Setting
$U_{<i}:=\bigcup_{j<i}U_{i}$, we immediately see from our choice of
$W^{\prime}$ that $|U_{<i}|\leq t/9$. Our bound on
$\operatorname{bad}_{\mathcal{D}}({U})$ from above thus gives:

$\displaystyle\operatorname{bad}_{\mathcal{D}}({U})\leq\sum_{i\in[M]}|U_{i}|\cdot
f\big{(}|U_{i}|\big{)}+\sum_{i\in[M]}\bigg{(}\frac{9|U_{<i}|}{t}\bigg{)}|U_{i}|\leq\sum_{i\in[M]}|U_{i}|\cdot
f\big{(}|U_{i}|\big{)}+\sum_{i\in[2,M]}|U_{i}|.$

For each $i\geq 2$ we have $|U_{i}|\leq|U_{<i}|$ from the ordering and so by
applying Lemma 2.5 we get $|U_{<i}|\cdot
f(|U_{<i}|)+|U_{i}|\leq|U_{<i+1}|\cdot f(|U_{<i+1}|)$. Repeatedly applying
this as $i$ increases gives us
$\operatorname{bad}_{\mathcal{D}}({U})\leq|U|\cdot f(|U|)$, noting that
$U_{<m+1}=U$. This completes the proof. ∎

Let us remark by combining the two cases in the proof above that $|U|\geq
2^{-25}k\log_{2}^{-2}(k+1)$.
We are finally able to prove Theorem 5.1. The proof is very similar to that of
Theorem 5.4 but, as the details are involved, for completeness we will go
through it with care.

###### Proof of Theorem 5.1.

We will prove a slightly more convenient statement, namely that given the
hypothesis there is a set $U\subset V(G)$ and a distribution ${\cal D}$ on
$[0.1,0.9]^{V(G)}$ such that $|U|\geq 2^{-26}(k+k^{3/4})\log_{2}^{-2}(k+1)$
and $\operatorname{bad}_{\mathcal{D}}({U})\leq 8|U|\log_{2}|U|$. We will prove
this by induction on $|V(G)|$. Note that the theorem trivially holds in the
first case where the hypothesis applies, when $n=20000$ and $k=1$ (taking $U$
to be any sets of size $1$ and ${\cal D}$ the trivial distribution). Also, as
in Theorem 5.9, when $k$ is small there is nothing to prove, so we can assume
$k\geq 2^{25}$.

Let $V_{0}$ be a largest vertex set of $G$ such that
$|\operatorname{div}(u,v)|\geq 2k^{3/2}$ for all $u,v\in V_{0}$. If
$|V_{0}|\geq k+1$ then we are done by Lemma 5.2, otherwise assume that
$V_{0}=\\{v_{1},v_{2},\ldots,v_{L}\\}$ for some $L\leq k$ and now for each
$i\in[L]$ define the set $V_{i}:=\\{v\in
V(G):|\operatorname{div}(v,v_{i})|<2k^{3/2}\\}$. Due to the maximality of
$S_{0}$ we get $V(G)=\bigcup_{i=1}^{L}V_{i}$. The proof splits into the two
already familiar cases:

Case I: Every $j\in[L]$ with $d_{G}(v_{j})\in[{nk^{-1/3}},n-1-nk^{-1/3}]$
satisfies $|V_{j}|\leq 3k$.

We have seen that there are at most $3k^{2}$ vertices of $G$ that do not lie
in a set $V_{j}$ of size at least $3k$. Moreover,
$d_{G}(v_{i})-2k^{3/2}<d_{G}(v)<d_{G}(v_{i})+2k^{3/2}$ for all $i\in[L]$ and
$v\in V_{i}$. Therefore, at least $n-3k^{2}$ vertices $v\in V(G)$ have degree
$d_{G}(v)\notin[nk^{-1/3}+2k^{3/2},n-1-nk^{-1/3}-2k^{3/2}]$. Therefore for all
such vertices we have $d_{G}(v)\leq nk^{-1/3}+2k^{3/2}$ or $d_{G}(v)\geq
n-1-nk^{-1/3}-2k^{3/2}$. We will assume that at least half of these vertices
satisfy the first condition, as otherwise we can follow an identical argument
working with $\overline{G}$ instead. Consequently we find a set $V\subset
V(G)$ with $|V|\geq(n-3k^{2})/2\geq 12n/25$ and $\Delta(G[V])\leq
nk^{-1/3}+2k^{3/2}<4|V|k^{-1/3}$. Moreover, $|V|\geq 8000k^{2}$ and
$\hom(G[V])\leq\hom(G)\leq n/25k\leq|V|/12k$, hence we can apply Theorem 5.9
to $G[V]$ to obtain a distribution ${\cal D}_{1}$ on $[0.1,0.9]^{V}$ and a
vertex set $U\subset V$ with $\operatorname{bad}_{\mathcal{D}}({U})\leq
8|U|\log_{2}|U|$ and $|U|\geq
2^{-25}k\log_{2}^{-2}(k+1)>2^{-26}(k+k^{3/4})\log_{2}^{-2}(k+1)$ . We also set
${\cal D}_{0}:={\cal T}_{V(G)\setminus V}$, i.e. the trivial distribution
induced by $V(G)\setminus V$, and let ${\cal D}:={\cal D}_{0}\times{\cal
D}_{1}$ denote the product distribution on $[0.1,0.9]^{V(G)}$. By making use
of Lemma 4.1 we can, once again, obtain
$\operatorname{bad}_{\mathcal{D}}({U})\leq\operatorname{bad}_{\mathcal{D}_{1}}^{V}({U})\leq
8|U|\log_{2}|U|$, as required.

Case II: There is $j\in[L]$ such that
$d_{G}(v_{j})\in[{nk^{-1/3}},n-1-nk^{-1/3}]$ and $|V_{j}|\geq 3k$.

As in Theorem 5.4, pick a subset $V$ of $V_{j}$ of size $3k$ such that
$v_{j}\in V$, then set ${X_{1}}:=N(v_{j})\setminus V$ and
${X_{2}}=:V(G)\setminus(V\cup N(v_{j}))$. We note that both
$|{X_{1}}|,|{X_{2}}|\geq nk^{-1/3}-3k$. The same double counting argument from
Theorem 5.4 works here to give us the sets $Y_{1}=\\{u\in
X_{1}:d_{G}^{V}(u)\geq 2k\\}$ and $Y_{2}=\\{u\in{X_{2}}:d_{G}^{V}(u)\leq
k\\}$, both of size at least $nk^{-1/3}-3k-6k^{3/2}>4096k^{3/2}>2^{48}$, such
that $|X_{i}\setminus Y_{i}|\leq 6k^{3/2}$ for each $i\in\\{1,2\\}$. Since
$V(G)=V\cup X_{1}\cup{X_{2}}$ is a partition, this shows that
$Z:=V(G)\setminus(Y_{1}\cup Y_{2})$ satisfies $|Z|\leq 2\cdot 6k^{3/2}+3k\leq
15k^{3/2}$.

To complete the proof we will apply the induction hypothesis to both $Y_{1}$
and $Y_{2}$. Let $t_{i}:=|Y_{i}|$ for $i\in\\{1,2\\}$ and set
$k_{i}:=k(t_{i}/n)\leq k$. This gives us $\hom(G[Y_{i}])\leq\hom(G)\leq
n/25k=t_{i}/25k_{i}$. We also have $t_{i}k_{i}^{-2}\geq
k_{i}^{-1}(t_{i}/k_{i})=k_{i}^{-1}(n/k)\geq nk^{-2}\geq 20000$. Therefore, for
$i=1,2$ we can apply the induction hypothesis to $G[Y_{i}]$ to find a
probability distribution $\mathcal{D}_{i}$ on $[0.1,0.9]^{Y_{i}}$ and a set
$U_{i}\subset Y_{i}$ which satisfies $|U_{i}|\geq
2^{-26}(k_{i}+k_{i}^{3/4})\log_{2}^{-2}(k_{i}+1)$ and:

$\displaystyle\operatorname{bad}_{\mathcal{D}_{i}}({U_{i}})\leq|U_{i}|\cdot
f(|U_{i}|),\ \ \ \text{where }f(x):=8\log_{2}x.$ (14)

Let us remark that if $k_{i}<2^{33}$ then any set $U_{i}\subset Y_{i}$ of size
$2\geq 2^{-25}k_{i}\log_{2}^{-2}(k_{i}+1)$ trivially satisfies (14), as
already noted many times before, thus the above computations all make sense.
We can also assume that $\max\\{|U_{1}|,|U_{2}|\\}\leq k$, as otherwise the
theorem follows immediately by just taking $U$ to equal one of these sets.

We will also let ${\cal D}_{0}:={\cal U}_{V}$ denote the uniformly constant
distribution on $[0.1,0.9]^{V}$ and let ${\cal D}_{3}:={\cal T}_{Z}$ denote
the trivial $Z$-induced distribution. We now set $U:=U_{1}\cup U_{2}$ and let
${\cal D}$ denote the product distribution $\prod_{i\in[0,3]}{\cal D}_{i}$ on
$[0.1,0.9]^{V}\times\prod_{i\in[2]}[0.1,0.9]^{Y_{i}}\times[0.1,0.9]^{Z}=[0.1,0.9]^{V(G)}$.

Note that $d^{V}_{G}(u)\geq 2k\geq d_{G}^{V}(v)+k$ for all $u\in Y_{1}$ and
$v\in Y_{2}$, by definition of $Y_{1}$ and $Y_{2}$. It then follows from Lemma
4.2 that for all such vertices we have:

$\displaystyle\operatorname{bad}_{\mathcal{D}_{0}}^{V}({u,v})\leq\frac{3}{k}.$
(15)

As $V(G)=Y_{1}\cup Y_{2}\cup Z$ is a partition and $|Z|\leq 15k^{3/2}$, we get
$t_{1}+t_{2}\geq n-15k^{3/2}$, therefore $k_{1}+k_{2}\geq
k-15n^{-1}k^{5/2}\geq k-\sqrt{k}/300$. Moreover, recall $t_{i}\geq
nk^{-1/3}-3k-6k^{3/2}>nk^{-1/3}/2$, hence $k_{i}=k(t_{i}/n)\geq k^{2/3}/2$ for
$i\in\\{1,2\\}$. By using Lemma 2.4 we obtain that:

$k_{1}^{3/4}+k_{2}^{3/4}\geq\frac{\sqrt{k}}{\sqrt[4]{8}}+\left(k-\frac{\sqrt{k}}{300}-\frac{\sqrt[3]{k^{2}}}{2}\right)^{3/4}>\frac{\sqrt{k}}{2}+k^{3/4}\cdot\left(1-\frac{2k^{-1/3}}{3}\right)^{3/4}.$

Using the inequalities $1-t\geq\exp(-2t)$ and $\exp(-t)\geq 1-t$, which hold
for any $t\in[0,0.5]$ and in particular for $t=\Theta(k^{-1/3})$, we can
further deduce that:

$\displaystyle
k_{1}^{3/4}+k_{2}^{3/4}\geq\frac{\sqrt{k}}{2}+k^{3/4}\cdot\exp\left(-k^{-1/3}\right)>\frac{\sqrt{k}}{2}+k^{3/4}-k^{-5/12}>k^{3/4}+\frac{\sqrt{k}}{300}.$
(16)

We are now in a position to lower bound the size of $U$:

$\displaystyle|U|=|U_{1}|+|U_{2}|$
$\displaystyle\geq\frac{1}{2^{26}}\cdot\left(\frac{k_{1}+k_{1}^{3/4}}{\log_{2}^{2}(k_{1}+1)}+\frac{k_{2}+k_{2}^{3/4}}{\log_{2}^{2}(k_{2}+1)}\right)\geq$
$\displaystyle\geq\frac{1}{2^{26}\log_{2}^{2}(k+1)}\cdot\big{(}k_{1}+k_{1}^{3/4}+k_{2}+k_{2}^{3/4}\big{)}\overset{\eqref{concavity-
ineq}}{\geq}$
$\displaystyle\geq\frac{1}{2^{26}\log_{2}^{2}(k+1)}\cdot\left(k_{1}+k_{2}+\frac{\sqrt{k}}{300}+k^{3/4}\right)\geq\frac{k+k^{3/4}}{2^{26}\log_{2}^{2}(k+1)}.$

Finally, we are able to estimate $\operatorname{bad}_{\mathcal{D}}({U})$ as
follows:

$\displaystyle\operatorname{bad}_{\mathcal{D}}({U})$
$\displaystyle=\sum_{\\{u,v\\}\subset
U_{1}}\operatorname{bad}_{\mathcal{D}}({u,v})+\sum_{\\{u,v\\}\subset
U_{2}}\operatorname{bad}_{\mathcal{D}}({u,v})+\sum_{(u,v)\in U_{1}\times
U_{2}}\operatorname{bad}_{\mathcal{D}}({u,v})$
$\displaystyle=\operatorname{bad}_{\mathcal{D}}({U_{1}})+\operatorname{bad}_{\mathcal{D}}({U_{2}})+|U_{1}||U_{2}|\cdot\max_{(u,v)\in
U_{1}\times U_{2}}\big{\\{}\operatorname{bad}_{\mathcal{D}}({u,v})\big{\\}}$
$\displaystyle\leq\operatorname{bad}_{\mathcal{D}_{1}}({U_{1}})+\operatorname{bad}_{\mathcal{D}_{2}}({U_{2}})+|U_{1}||U_{2}|\cdot\max_{(u,v)\in
U_{1}\times
U_{2}}\big{\\{}\operatorname{bad}_{\mathcal{D}_{0}}^{V}({u,v})\big{\\}}$
$\displaystyle\leq|U_{1}|\cdot f(|U_{1}|)+|U_{2}|\cdot
f(|U_{2}|)+\frac{3}{k}\cdot|U_{1}||U_{2}|\leq|U|\cdot f(|U|).$

The final three inequalities here respectively follow from Lemma 4.1, then
from (14) and (15), and lastly using that $\max\\{|U_{1}|,|U_{2}|\\}\leq k$
and Lemma 2.5. This completes the proof. ∎

##  6 Distinct degrees in random graphs

In this section we will study $f(G(n,p))$, the number of distinct degrees
which can be found in an induced subgraph of the Erdős$-$Rényi random graph
$G(n,p)$. Our results extend the estimates for the case of constant $p$ due to
Bukh and Sudakov [9] and to Conlon, Morris, Samotij and Saxton [10]. We
restate Theorem 1.3 for the reader’s convenience.

See 1.3

Although the estimation of $f(G(n,p))$ is quite natural in itself, we believe,
as discussed in the concluding remarks, that the behaviour for
$p\in[n^{-1/2},1/2]$ essentially determines the extremal relationship between
$\hom(G)$ and $f(G)$ beyond the range of the Narayanan–Tomon conjecture, when
$\hom(G)<n^{1/2}$. As a result, our calculations will focus on the case (i) of
Theorem 1.3. The next subsection contains the proof the upper bound on
$f(G(n,p))$ in this case, whereas the second subsection contains the more
difficult lower bound. In the final subsection we briefly indicate how to
approach the case when $p\leq n^{-1/2}$.

###  6.1 Upper bound on $f(G(n,p))$

In this subsection we prove the upper bound on $f(G(n,p))$. Our approach
closely follows that of Bukh and Sudakov (see Proposition 2.4 in [9]), but we
include the complete details, as the estimates are more involved in the sparse
case.

######  Proposition 6.1.

Given $n\in{\mathbb{N}}$ and $p\in[n^{-1/2},1/2]$, one has
$f\big{(}G(n,p)\big{)}=O\big{(}\sqrt[3]{pn^{2}}\big{)}$ whp.

###### Proof.

Suppose $G\sim G(n,p)$ has a subset $A\subset V(G)$ of size $a$ such that
$G[A]$ has $8b$ distinct degrees, where $b=16\sqrt[3]{pn^{2}}$. As at most
$6b-1$ of our distinct degrees can lie in the interval $(pa-3b,pa+3b)$, either
there are at least $b$ vertices of $A$ that have degree at least $pa+3b$ or at
least $b$ vertices that have degree at most $pa-3b$.

We will assume first that we are in the former case, as this is the more
intricate one. Let $B\subset A$ be a set of $b$ vertices which all have degree
at least $pa+3b$. Let us now look at the number $e(A,B)$ of edges with one
endpoint in $A$ and one in $B$ (those with both their endpoints in $B$ will be
counted twice since $B\subset A$). We then have $pab+3b^{2}\leq
e(A,B)=2e(B)+e(A\setminus B,B)$. As $|B|=b$ implies $e(B)<b^{2}$, we find
that:

$\displaystyle e(A\setminus B,B)\geq pab+b^{2}\geq p(a-b)b+b^{2}.$ (17)

Letting $F$ denote the event that there are sets $A$ and $B$ which satisfy
(17), it suffices to show that ${\mathbb{P}}(F)=o(1)$. To see this, first
suppose that $16p(a-b)\geq b$. As $\mathbb{E}[e(A\setminus B,B)]=p(a-b)b$, by
using Chernoff’s Inequality with $\delta={b}/{16p(a-b)}\leq 1$ we get that:

$\displaystyle\mathbb{P}\left(e(A\setminus B,B)\geq pb(a-b)+b^{2}\right)$
$\displaystyle\leq\mathbb{P}\left(e(A\setminus B,B)\geq
pb(a-b)+2^{-4}b^{2}\right)$
$\displaystyle\leq\exp\left(\dfrac{-b^{3}}{2^{10}p(a-b)}\right)\leq\exp\left(\dfrac{-b^{3}}{2^{10}pn}\right),$

where the final inequality uses that $a-b\leq a\leq n$. Therefore, the union
bound implies that event $F$ can happen with probability at most:

${\mathbb{P}}(F)\leq
2^{n}\cdot\dbinom{n}{b}\cdot\exp\left(\dfrac{-b^{3}}{4\cdot pn}\right)\leq
2^{2n}\cdot\exp\left(\dfrac{-b^{3}}{2^{10}\cdot pn}\right).$

This tends to zero as $n\to\infty$, as $b\geq 16\sqrt[3]{pn^{2}}$.

Now suppose instead that $16p(a-b)<b$. As $e(A\setminus B,B)$ has binomial
distribution, we have:

$\mathbb{P}\left(e(A\setminus B,B)\geq
pb(a-b)+b^{2}\right)\leq\dbinom{b(a-b)}{b^{2}}\cdot
p^{b^{2}}\leq\left(\dfrac{2ep(a-b)}{b}\right)^{b^{2}}\leq 2^{-b^{2}}.$

Recalling that $p\geq n^{-1/2}$ and that $b\geq 16\sqrt[3]{pn^{2}}\geq
16\sqrt[3]{n^{-1/2}n^{2}}\geq 16\sqrt{n}$, using the union bound we find that
the event $F$ occurs with probability at most:

${\mathbb{P}}(F)\leq 2^{n}\binom{n}{b}2^{-b^{2}}\leq 2^{2n}\cdot
2^{-(16\sqrt{n})^{2}}.$

Hence, it follows again that ${\mathbb{P}}(F)=o(1)$ in this second case.

Finally, if there is a set $B\subset A$ of $b$ vertices that all have degree
at most $pa-3b$ in $G[A]$, then $e(A\setminus B,B)\leq e(A,B)\leq b(pa-3b)\leq
pb(a-b)-b^{2}$. If $p(a-b)<b$ then it is clear that such a set $B$ exists with
$0$ probability since we cannot have a negative number of edges. Otherwise we
can simply apply Chernoff’s Inequality for $\delta=\dfrac{b}{p(a-b)}\leq 1$ to
get:

$\mathbb{P}\bigg{(}e(A\setminus B,B)\leq
pb(a-b)-b^{2}\bigg{)}\leq\exp\left(-\dfrac{b^{3}}{2p(a-b)}\right)\leq\exp\left(-\dfrac{b^{3}}{2pn}\right),$

where the last inequality follows as $a-b\leq a\leq n$. We have seen before
that the union bound gives us probability of at most
$2^{n}\cdot\binom{n}{b}\cdot\exp\left(-b^{3}/2pn\right)$ for such a set $B$ to
exist and we have shown in the previous case that this probability tends to
$0$ as $n\to\infty$. ∎

###  6.2 Lower bound on $f(G(n,p))$

We now focus on proving our sharp lower bound for $f(G(n,p))$. Before we
start, we will present a few results that will help us along the way.
Given $D>0$ and a graph $G$, we call a set $U\subset V(G)$ $D$-_diverse_ if it
is $D$-diverse to $V(G)$. We say that the graph $G$ is $D$-_diverse_ if $V(G)$
is $D$-diverse (see Section 4 before Lemma 4.3).

######  Proposition 6.2.

If $p\gg\log n/n$ then all vertices of $G(n,p)$ have degree asymptotic to $np$
whp. In particular, whp they all have degrees less than $2np$.

###### Proof.

Let $u$ be a vertex of $G(n,p)$. Then $d_{G(n,p)}(u)\sim Bin(n-1,p)$, so we
can apply Chernoff’s Inequality for $\delta=3\sqrt{\dfrac{\log n}{np}}$ to get
$\mathbb{P}\big{(}|d(u)-np|\geq 3\sqrt{np\log n}\big{)}\leq 2n^{-9/2}$. The
result now follows by the union bound. The last part is a consequence of the
fact that $\delta\leq 1$. ∎

######  Lemma 6.3.

If $p\gg\log n/n$ and $p\leq 1/2$ then whp $G(n,p)$ is $p(n-1)$-diverse.

###### Proof.

Let us first notice that $|\text{div}(u,v)|\sim Bin(n-2,q)$ for all distinct
$u,v\in V(G)$, where $q:=2p(1-p)$. This holds as every vertex of
$\text{div}(u,v)$ has to be in $N(u)\setminus N(v)$ or in $N(v)\setminus N(u)$
and these two possibilities represent disjoint events that happen with
probability $p(1-p)$.
Note that $q\geq p\gg\log n/n$ and so we can apply Chernoff’s Inequality for
$\delta=3\sqrt{\dfrac{\log n}{nq}}$ to obtain
$\mathbb{P}\big{(}|\text{div}(u,v)|\leq nq-3\sqrt{nq\log n}\big{)}\leq
n^{-9/2}$. By the union bound, we therefore deduce that
$|\text{div}(u,v)|>nq(1-\delta)$ for any $u,v\in V(G)$ whp. Since $q\geq p$
and $\delta\to 0$, we get that $G(n,p)$ is $p(n-1)$-diverse whp in this case.
∎

######  Lemma 6.4.

Let $n\in{\mathbb{N}}$ and $p\in[n^{-1/2},1/2]$ and suppose $G\sim G(n,p)$ and
let $V(G):=U\sqcup S$ be a vertex partition such that $\sqrt{n}\leq 4|U|\leq
pn$. Then, with high probability, there is a subset $W\subset S$ such that $U$
is $pn/3$-diverse to $W$ and $d^{U}_{G}(w)\leq 10p|U|$ for all $w\in W$.

###### Proof.

Define the set $S_{B}:=\\{v\in V:d_{G}^{U}(v)\geq 10p|U|\\}$. For any $v\in S$
the random variable $d_{G}^{U}(v)$ has distribution $Bin(|U|,p)$, hence, as
$p|U|\geq 2.5$, we deduce that:

$\tilde{p}:=\mathbb{P}(v\in S_{B})\leq(e/10)^{10p|U|}<3^{-2.5}<1/10.$

Now for each subset $W\subset S$ we see that $|W\cap S_{B}|$ has distribution
$Bin(|W|,\tilde{p})$. Therefore, for any $u_{1},u_{2}\in U$ we can deduce by
using Theorem 2.7 and Lemma 6.3 that:

$\mathbb{P}\left(|\text{div}(u_{1},u_{2})\cap
S_{B}|>\frac{|\text{div}(u_{1},u_{2})|}{3}\right)\leq\left(3e\tilde{p}\right)^{|\text{div}(u_{1},u_{2})|/3}\leq\left(\frac{9}{10}\right)^{\sqrt{n}/4}.$

Call a pair $\\{u_{1},u_{2}\\}\subset U$ of vertices _big_ if
$|\text{div}(u_{1},u_{2})\cap S_{B}|>|\text{div}(u_{1},u_{2})|/3$. By using
the union bound we immediately deduce that $U$ contains a _bad_ pair of
vertices with probability at most $p^{2}n^{2}/8\cdot(9/10)^{\sqrt{n}/4}\to 0$
as $n\to\infty$. Set now $W:=S\setminus S_{B}$ and note that whp for all
distinct $u_{1},u_{2}\in U$ we have $|\text{div}(u_{1},u_{2})\setminus
S_{B}|>2|\text{div}(u_{1},u_{2})|/3\geq 2p(n-1)/3$. We then get:

$\big{|}N_{G}^{W}(u_{1})\triangle
N_{G}^{W}(u_{2})\big{|}\geq\big{|}\text{div}(u_{1},u_{2})\setminus
S_{B}\big{|}-|U|\geq\frac{2p(n-1)}{3}-\frac{\sqrt{n}}{4}>\frac{pn}{3}.$

The second property follows directly from the definition of $W$ and so our
result is proved. ∎

######  Definition 6.5.

Let $G$ be a $n$-vertex graph and let $0<p\leq 1/2$. We call a set $U$ of
vertices of $G$ $p$_-convenient_ if $d_{G}(u)\leq 2pn$ for all $u\in U$ and
there is a set $W\subset V(G)\setminus U$ such that $U$ is $pn/3$-diverse to
$W$ and $d^{U}_{G}(w)\leq 10p|U|$ for all $w\in W$.

We now expose the randomness in $G(n,p)$ and obtain a fixed graph $G$.
According to Proposition 6.2 and Lemma 6.4, we may assume that $G$ contains a
$p$-convenient set $U$ of size $\sqrt[3]{pn^{2}}/4$.

At this point, the reader might have already noticed that the $p$-convenient
conditions fit in very well with those from Lemma 4.3. Indeed, the set $U$ is
$pn/3$-diverse to $W$ and $10p$-balanced, so the hypothesis of the lemma is
satisfied. The most natural thing to do would now be to apply the lemma with
the blended distribution $\mathcal{B}_{\beta}(U,W)$. However, in order to
obtain a set of $\Theta(|U|)$ degrees, we would like the first term in the RHS
of (5) to be of order $|U|^{-1}$, which forces
$\beta:=\Theta\left(|U|/pn\right)$. This would then make the second term in
the RHS of (5) to be a constant, so it seems that we cannot get the desired
‘bad’ control. One can obtain weaker bounds on $f(G(n,p))$ by altering the
parameters here, but there is an unavoidable loss as things stand.

There is though a way around this issue. In Lemma 4.3 we solve the problem of
coordinates lying outside $[0.1,0.9]$ by dealing with each pair of vertices
$\\{u_{1},u_{2}\\}\subset U$ individually. However, in certain situations it
is possible to show that many vertices $u_{1}\in U$ are _simultaneously_ good
for all pairs $\\{u_{1},u_{2}\\}\subset U$. The crucial twist here is that the
diversity term $D:=pn/3$ satisfies $D=\Omega(\Delta(G))$. This allows us to
guarantee that a fixed vertex $u_{1}\in U$ whp is likely to have no neighbours
in $\text{div}(u_{1},u_{2})$ whose coordinates are ’outliers’, and this
happens _for all_ $u_{2}\in U$. The approach here builds upon that of Jenssen,
Keevash, Long and Yepremyan [19].

A slight change in our notation will be convenient below. Given a graph $G$
with vertex partition $V(G)=U\sqcup W$ and a probability vector
$\textbf{\text@underline{p}}=(p_{w})_{w\in W}\in[0,1]^{W}$, we write
$G(\textbf{\text@underline{p}})$ to denote the probability space on the set of
induced subgraphs of $G$ _that contain_ $U$, where for each vertex set
$S\subset W$, the induced subgraph $G[U\cup S]$ is selected with probability
$\prod_{v\in S}p_{v}\prod_{v\in W\setminus S}(1-p_{v})$.

######  Proposition 6.6.

Let $n\in{\mathbb{N}}$, $p\in[n^{-1/2},1/2]$ and let $G$ be an $n$-vertex
graph with a $p$-convenient set $U\subset V(G)$ of size $\sqrt[3]{pn^{2}}/4$.
Then there is a vector $\textbf{\text@underline{p}}\in[0.1,0.9]^{V(G)\setminus
U}$ and a set $U^{\prime}\subset U$ with $|U^{\prime}|\geq|U|/500$ so that
$\big{|}\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u_{1})]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u_{2})]\big{|}\geq
1$ for all distinct $u_{1},u_{2}\in U^{\prime}$.

###### Proof.

We may assume that $n$ is large enough so that all asymptotic bounds hold.
First set $\beta:=|U|/5pn<0.1$ and let $S\subset V(G)\setminus U$ be such that
$U$ is $pn/3$-diverse to $S$ and $d^{U}_{G}(v)\leq 10p|U|$ for all $v\in S$.
As in the proof of Lemma 4.3, for each $u\in U$ define the random vector
$\textbf{\text@underline{q}}^{u}$ on $\mathbb{R}^{S}$ by
$\textbf{\text@underline{q}}^{u}:=\textbf{\text@underline{p}}^{\prime}-\alpha_{u}\cdot\operatorname{proj}_{S}({\bf{u}})$,
where $\textbf{\text@underline{p}}^{\prime}$ is the vector from before the
truncation in the definition of the blended distribution
$\mathcal{B}_{\beta}(U,S)$. Recall we do this so that
$\textbf{\text@underline{q}}^{u}$ is independent of $\alpha_{u}$.

We call a vertex $u\in U$ _good_ if there are at most $d_{G}^{S}(u)/25$
coordinates $v\in S\cap N(u)$ so that
$\textbf{\text@underline{q}}_{v}^{u}\notin[0.2,0.8]$. Let $U^{g}\subset U$
denote the set of _good_ vertices.
We claim that $\mathbb{P}(|U^{g}|\geq|U|/2)>1/2$. To prove this, take $u\in U$
and note that $\textbf{\text@underline{q}}^{u}_{v}$ is a sum of at most
$10p|U|$ uniform independent random variables, thus by Hoeffding’s inequality:

$\mathbb{P}\big{(}\textbf{\text@underline{q}}_{v}^{u}\notin[0.2,0.8]\big{)}=\mathbb{P}\big{(}|\textbf{\text@underline{q}}_{v}^{u}-1/2|>0.3\big{)}\leq
2\exp\left(\dfrac{-50\cdot 0.09\cdot
p^{2}n^{2}}{10p|U|^{3}}\right)=2e^{-7.2}<\frac{1}{100}.$

We deduce that the expected number of coordinates $v\in V\cap N(u)$ with
$\textbf{\text@underline{q}}_{v}^{u}\notin[0.2,0.8]$ is at most
$d_{G}^{V}(u)/100$. By Markov we get that the vertex $u$ is not good with
probability less than $1/4$. Therefore, the expected number of vertices $u\in
U$ that are not good is at most $|U|/4$ and the claim follows from a simple
application of Markov’s Inequality.

We now set $T:=V(G)\setminus(S\cup U)$ and let $\mathcal{T}_{T}$ denote the
trivial $T$-induced distribution. Take $\mathcal{D}$ to be the product
distribution $B_{\beta}(U,S)\times\mathcal{T}_{T}$ on $[0.1,0.9]^{S\cup T}$.
Given distinct vertices $u_{1},u_{2}\in U$, we let $E_{u_{1},u_{2}}$ denote
the event that
$\left|\mathbb{E}_{\textbf{\text@underline{p}}\sim\mathcal{D}}\big{[}d_{G(\textbf{\text@underline{p}})}(u_{1})-d_{G(\textbf{\text@underline{p}})}(u_{2})\big{]}\right|\leq
1$. Moreover, since $U$ is $pn/3$-diverse to $S$, we know that either
$|N_{G}^{S}(u_{1})\setminus N_{G}^{S}(u_{2})|\geq pn/6$ or
$|N_{G}^{S}(u_{2})\setminus N_{G}^{S}(u_{1})|\geq pn/6$. We set
$m_{S}(u_{1},u_{2}):=u_{1}$ in the first case and $m_{S}(u_{1},u_{2}):=u_{2}$
in the second one.

Our next claim is that $\mathbb{P}\big{(}E_{u,u^{\prime}}\ |\
m_{S}(u,u^{\prime})\in U^{g}\big{)}\leq 120|U|^{-1}$ for all $u\neq
u^{\prime}$ in $U$. To prove it, we can assume that $u=m_{S}(u,u^{\prime})$.
As $u\in U^{g}$, at most $2pn/25$ vertices in $N_{G}(u)$ represent coordinates
$v$ such that $\textbf{\text@underline{q}}^{u}_{v}\notin[0.2,0.8]$. Therefore,
we can find a subset $Y\subset N_{G}^{S}(u)\setminus N_{G}^{S}(u^{\prime})$ of
size $pn/12$ such that $\textbf{\text@underline{q}}^{u}_{v}\in[0.2,0.8]$ for
all $v\in Y$. Since
$\textbf{\text@underline{p}}^{\prime}_{v}=\textbf{\text@underline{q}}^{u}_{v}+\alpha_{u}\textbf{u}_{v}$
and $|\alpha_{u}|<0.1$, we deduce that no $Y$-coordinate of
$\textbf{\text@underline{p}}^{\prime}$ gets truncated when creating
$\textbf{\text@underline{p}}\sim B_{\beta}(U,S)$. Condition now on any choice
of $\bm{\alpha}:=(\alpha_{w})_{w\neq u}$ such that $u\in U^{g}$ and note that
$\alpha_{u}$ is independent of it.
By looking at the following expression (when
$\textbf{\text@underline{p}}\sim\mathcal{D}$) as a function of $\alpha_{u}$:

$\displaystyle{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}(u)]-{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}(u^{\prime})]$
$\displaystyle=\text{ constant
}+{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(u)]-{\mathbb{E}}[d_{G(\textbf{\text@underline{p}})}^{S}(u^{\prime})]$
$\displaystyle=\text{ constant
}+(\operatorname{proj}_{S}({\bf{u}})-\operatorname{proj}_{S}({\bf{v}}))\cdot\operatorname{proj}_{S}({\bf{\textbf{\text@underline{p}}}})$

we observe that $E_{u,u^{\prime}}$ holds provided that, conditioned on
$\bm{\alpha}$, this difference lies in an interval of length $2$. The same
argument as in Lemma 4.3 gives us that $E_{u,u^{\prime}}|\bm{\alpha}$ happens
with probability at most $24(pn\beta)^{-1}=120|U|^{-1}$. The claim follows
from the law of total probability.

To complete the proof, we consider the graph $J$ on the vertex set $U^{g}$
where $u_{1}u_{2}\in E(J)$ if $E_{u_{1},u_{2}}$ holds. By the second claim we
get $\mathbb{E}[{e(J)}]\leq 120|U|^{-1}\cdot|U^{g}|(|U^{g}|-1)/2<60|U|$, thus
by Markov $\mathbb{P}\big{(}e(J)>120|U|\big{)}<1/2$. It follows that
$\mathbb{P}\big{(}e(J)\leq 120|U|\big{)}>1/2$ and recall that
$\mathbb{P}(|U^{g}|\geq|U|/2)>1/2$. Therefore, with positive probability, we
can choose $\textbf{\text@underline{p}}\sim\mathcal{D}$ such that
$|U^{g}|\geq|U|/2$ and $e(J)\leq 120|U|$. For such a choice, the average
degree of the resulting graph $J$ is $4e(J)/2|U_{g}|\leq 4e(J)/|U|\leq 480$.
Thus, by Turán’s Theorem $J$ has an independent set of size at least
$|U|/500$. This independent set in $J$ is precisely what we required. ∎

######  Proposition 6.7.

Let $G$ be a $n$-vertex graph and let $p\in[n^{-1/2},1/2]$. Suppose that there
is a $p$-convenient set $U\subset V(G)$ in $G$, a vector
$\textbf{\text@underline{p}}\in[0.1,0.9]^{V(G)\setminus U}$ and a vertex
subset $U^{\prime}\subset U$ so that
$\big{|}\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u_{1})]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u_{2})]\big{|}\geq
1$ for all distinct $u_{1},u_{2}\in U^{\prime}$. Then
$f(G)=\Omega(|U^{\prime}|)$.

###### Proof.

We can assume $n$ is sufficiently large. Let $H$ be a random induced subgraph
selected according to $G(\textbf{\text@underline{p}})$ and define for it the
following sets:

$\displaystyle B=\\{u\in
U^{\prime}:\big{|}d_{H}(u)-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}]\big{|}\leq\sqrt{2pn}\\},$
$\displaystyle P=\\{\\{u,u^{\prime}\\}\subset
U^{\prime}:\big{|}\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u)]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u^{\prime})]\big{|}\leq
2\sqrt{2pn}\\},$ $\displaystyle J=\\{\\{u,u^{\prime}\\}\in
P:d_{H}(u)=d_{H}(u^{\prime})\\}.$

Our first claim is that $\mathbb{P}(|B|\geq|U^{\prime}|/2)\geq 1/2$. To prove
it, we start by estimating $|B|$. For any $u\in U^{\prime}$ we have
$\mathbb{V}\text{ar}\big{(}d_{G(\textbf{\text@underline{p}})}(u)\big{)}=\sum_{v\sim
u}p_{v}(1-p_{v})\leq pn/2$, thus Chebyshev’s Inequality implies that
$\mathbb{P}(u\notin B)\leq 1/4$. It follows that
$\mathbb{E}[|U^{\prime}\setminus B|]\leq|U^{\prime}|/4$, so by Markov’s
inequality we get that $\mathbb{P}(|U^{\prime}\setminus
B|\geq|U^{\prime}|/2)\leq 1/2$, which is equivalent to our claim.

We now want to estimate $|J|$. First note that the separation in expected
degree for $U^{\prime}$ implies that $|P|\leq 2|U^{\prime}|\sqrt{2pn}$. Each
$\\{u,u^{\prime}\\}$ belongs to $J$ with probability
$\mathbb{P}\big{(}d_{H}(u)-d_{H}(u^{\prime})=0\big{)}$, which we claim is
$O\left(1/\sqrt{pn}\right)$. This happens because
$d_{H}(u)-d_{H}(u^{\prime})=\sum\xi_{v}X_{v}$, where the sum is taken over all
$v\in\text{div}(u,u^{\prime})\setminus U$, $\xi_{v}\in\\{-1,1\\}$ and
$X_{v}\sim Be(p_{v})$ measures whether $v\in V$ is picked as a vertex of $H$
or not. As $U$ is $pn/3$-diverse to some subset $S\subset V(G)\setminus U$, we
deduce that $|\text{div}(u,u^{\prime})\setminus U|\geq|N_{G}^{S}(u)\triangle
N_{G}^{S}(u^{\prime})|\geq pn/3$, so we can apply Theorem 2.3 to prove the
previous claim. Therefore
$\mathbb{E}[|J|]\leq|P|\cdot\displaystyle\max_{\\{u,u^{\prime}\\}\in
P}\mathbb{P}\big{(}d_{H}(u)=d_{H}(u^{\prime})\big{)}=O(|U^{\prime}|)$.
It follows that $\mathbb{P}\big{(}|J|=O(|U^{\prime}|)\big{)}>1/2$ by Markov,
so together with the first claim, we are able to deduce that both
$|J|=O(|U^{\prime}|)$ and $|B|\geq|U^{\prime}|/2$ happen with positive
probability. The end of the proof follows the same idea as before: make a
choice of $H$ for which this happens and by Turán’s Theorem the graph $J[B]$
obtained by building edges between the vertices of $B$ which have equal degree
in $H$ has an independent set of size $\Omega(|U^{\prime}|)$. This set must
consist of vertices with distinct degrees in $H$, as if $u,u^{\prime}\in B$
and $d_{H}(u)=d_{H}(u^{\prime})$ then $\\{u,u^{\prime}\\}\in P$ and so
$\\{u,u^{\prime}\\}\in J$, which represents an edge in $J[B]$. ∎

With all these ingredients, we are finally able to prove the following:

######  Theorem 6.8.

Given $n\in{\mathbb{N}}$ and $p\in[n^{-1/2},1/2]$, one has
$f\big{(}G(n,p)\big{)}=\Omega\big{(}\sqrt[3]{pn^{2}}\big{)}$ whp.

###### Proof.

We expose the randomness in $G(n,p)$ and thus move to a fixed graph $G$.
According to Proposition 6.2 and Lemma 6.4, we can find a $p$-convenient set
$U$ in $G$ of size $\sqrt[3]{pn^{2}}/4$. We then apply Proposition 6.6 to find
a vector $\textbf{\text@underline{p}}\in[0.1,0.9]^{V(G)\setminus U}$ and a
subset $U^{\prime}\subset U$ of size $\Omega\left(\sqrt[3]{pn^{2}}\right)$ so
that
$\big{|}\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u_{1})]-\mathbb{E}[d_{G(\textbf{\text@underline{p}})}(u_{2})]\big{|}\geq
1$ for all distinct $u_{1},u_{2}\in U^{\prime}$. Lastly, Proposition 6.7
allows us to convert a constant proportion of the distinct expected degrees in
$U^{\prime}$ to genuine distinct degrees, thus completing the proof. ∎

###  6.3  $f(G(n,p))$ when $p\ll n^{-1/2}$

For completeness, in this subsection we discuss the behaviour of $f(G(n,p))$
for $p\ll n^{1/2}$. First, to see that there is a change in behaviour here
over the range $p\in[n^{-1/2},1/2]$, note that if $G\sim G(n,p)$ with $\log
n/n\ll p\ll n^{-1/2}$ then a simple concentration argument combined with the
union bound shows that whp $d_{G}(u)=O(pn)$ for every vertex $u\in V(G)$,
showing that $f(G)=O(pn)=o(\sqrt[3]{pn^{2}})$ in this case.

As indicated in Theorem 1.3 (ii), in this regime the maximum degree of
$G(n,p)$ is a key parameter. The following simple proposition is useful here.

######  Proposition 6.9.

Let $G$ be an $n$-vertex graph and let $U\subset V(G)$ with $|U|=k$ such that
$|N_{G}(u)\setminus\big{(}U\cup\cup_{u^{\prime}\in
U\setminus\\{u\\}}N(u^{\prime})\big{)}|\geq k$ for all $u\in U$. Then
$f(G)\geq k$.

###### Proof.

Let $U:=\\{u_{1},u_{2}\ldots,u_{k}\\}$ such that $|N_{G}(u_{i})\cap U|$ is
non-decreasing with $i$. For each $i\in[k]$ take $S_{i}\subset
N_{G}(u_{i})\setminus\big{(}U\cup\cup_{u^{\prime}\in
U\setminus\\{u\\}}N(u^{\prime})\big{)}$ with $|S_{i}|=i\ -$ by the hypothesis
such sets exist. It is now easy to see that the degrees of the vertices
$u_{1},u_{2},\ldots,u_{k}$ are strictly increasing in the induced subgraph
$G\big{[}U\cup(\cup_{i\in[k]}S_{i})\big{]}$, giving $f(G)\geq k$, as required.
∎

The following observations show that
$f(G(n,p))=\Theta\big{(}\Delta(G(n,p))\big{)}$ in this regime.

  * (i)

If $\log n/n\ll p\leq n^{-1/2}$ then whp $d_{G}(u)\in[pn/2,2pn]$ for all $u\in
V(G)$, therefore we deduce that $\Delta(G(n,p))=\Theta(np)$;

  * (ii)

If $\log n/n\ll p\leq n^{1/2}$ then given any fixed set $U\subset V(G(n,p))$
with $|U|=pn/8$ and $u\in U$ we have
${\mathbb{E}}\big{[}N_{G}(u)\setminus(U\cup\cup_{u^{\prime}\in
U\setminus\\{u\\}}N(u^{\prime}))\big{]}=p(n-|U|)(1-p)^{|U|}\geq pn/4$.
Chernoff’s Inequality then applies to give us that
$|N_{G}(u)\setminus(U\cup\cup_{u^{\prime}\in
U\setminus\\{u\\}}N(u^{\prime}))|\geq pn/8=|U|$ for all $u\in U$ whp.
Proposition 6.9 together with (i) then gives
$f(G)\geq|U|=\Theta(\Delta(G(n,p)))$ for $\log n/n\ll p\leq n^{-1/2}$ whp.

  * (iii)

If $0\leq p\leq O(\log n/n)$ then $G(n,p)$ has $\Omega(\Delta(G(n,p)))$
vertices of degree $\Omega(\Delta(G(n,p)))$ whp (e.g. see Theorem 3.1 in [7]).
It is therefore possible to find a set $U$ of $c\cdot\Delta(G(n,p))$ vertices
with degree at least $5|U|$, provided that $c>0$ is sufficiently small.

  * (iv)

It is also true that if $p\leq n^{-3/4}$ then whp $|N(u)\cap
N(u^{\prime})|\leq 3$ for all pairs of distinct vertices $u,u^{\prime}\in
V(G(n,p))$. With $U$ chosen as in (iii) it follows that
$|N(u)\setminus(U\cup\cup_{u^{\prime}\in
U\setminus\\{u^{\prime}\\}}N(u^{\prime}))|\geq|N(u)|-|U|-3|U|\geq|U|$. Thus
$f(G(n,p))=\Theta(\Delta(n,p))$ for $p=O(\log n/n)$.

##  7 Concluding remarks

Theorem 1.1 proves an essentially sharp dependence between $\hom(G)$ and
$f(G)$ for $n$-vertex graphs with $\hom(G)\geq n^{1/2}$, which asymptotically
resolves a conjecture of Narayanan and Tomon from [26]. It would be appealing
to further remove the logarithmic terms here.

Another perhaps more compelling problem is to understand the relationship
between these parameters when $\hom(G)<n^{1/2}$. Recall that Theorem 1.3
gives:

$f\big{(}G(n,p)\big{)}=\begin{cases}\Theta\left(\sqrt[3]{pn^{2}}\right)\text{
for }p\in[n^{-1/2},1/2];\\\ \Theta\big{(}\Delta(G(n,p))\big{)}\text{ for
}p\in[0,n^{-1/2}].\end{cases}$

It is well known that $\text{hom}(G(n,p))\sim-\log n/\log(1-p)$ (see e.g. [8])
when $0<p\leq 1/2$ is a fixed constant. For a general $p:=p(n)\leq 1/2$, the
probability of having a set of size $k$ which is homogeneous in $G(n,p)$ is at
most:

$\binom{n}{k}\big{(}p^{\binom{k}{2}}+(1-p)^{\binom{k}{2}}\big{)}\leq
2n^{k}(1-p)^{\binom{k}{2}}\leq
2n^{k}e^{-p\binom{k}{2}}=2\left(ne^{-p(k-1)/2}\right)^{k}.$

In particular, $\mbox{hom}(G(n,p))\leq 4p^{-1}\log n$ whp. Combined with the
bounds for $f(G(n,p))$ from Theorem 1.3 we find that for $p\in[n^{-1/2},1/2]$
we have:

$f(G(n,p))=\widetilde{\Omega}\Bigg{(}\sqrt[3]{\frac{n^{2}}{\hom(G(n,p))}}\Bigg{)}\quad\mbox{whp}.$

We believe that a similar bound holds for any $n$-vertex graph $G$ with
$\hom(G)<n^{1/2}$.

######  Conjecture 7.1.

If $G$ is an $n$-vertex graph then:

$\displaystyle
f(G)\geq\min\left(\sqrt[3]{\frac{n^{2}}{\hom(G)}},\frac{n}{\hom(G)}\right)n^{-o(1)}.$

Observe that the minimum above changes exactly when $\hom(G)=n^{1/2}$, value
after which the Narayanan–Tomon conjecture begins to apply. Theorem 1.1 proves
it for $\hom(G)\geq n^{1/2}$. Theorem 1.3 shows that this behaviour is
essentially tight for $G(n,p)$ when $p=n^{-1/2}$, when
$\hom(G(n,p))=n^{1/2+o(1)}$. At the opposite extreme, $n$-vertex graphs with
$\hom(G)$ as small as possible (Ramsey graphs) were proven by Jenssen et al.
in [19] to have $f(G)=\Omega(n^{2/3})$, and so the conjecture is true at both
ends of the interval $\hom(G)\in[\Omega(\log n),n^{1/2}]$.

Acknowledgement

We would like to thank the referees for their careful reading of the paper,
and for a number of useful suggestions.

## References

  * [1] N Alon, S Friedland and G Kalai  “Regular subgraphs of almost regular graphs”  In _Journal of Combinatorial Theory, Series B_ 37.1, 1984, pp. 79–91  DOI: https://doi.org/10.1016/0095-8956(84)90047-9
  * [2] Noga Alon, Michael Krivelevich and Benny Sudakov  “Induced subgraphs of prescribed size”  In _Journal of Graph Theory_ 43.4, 2003, pp. 239–251  DOI: https://doi.org/10.1002/jgt.10117
  * [3] Noga Alon, Michael Krivelevich and Benny Sudakov  “Large nearly regular induced subgraphs”  In _SIAM Journal on Discrete Mathematics_ 22.4 Society for IndustrialApplied Mathematics Publications, 2008, pp. 1325–1337  DOI: 10.1137/070704927
  * [4] Noga Alon and Joel H. Spencer  “The Probabilistic Method”  New York: Wiley, 2004
  * [5] Boaz Barak, Anup Rao, Ronen Shaltiel and Avi Wigderson  “2-source dispersers for $n^{o(1)}$-entropy, and Ramsey graphs beating the Frankl-Wilson construction”  In _Annals of Mathematics_ JSTOR, 2012, pp. 1483–1543
  * [6] B. Bollobás  “Extremal Graph Theory”  USA: Dover Publications, 2004
  * [7] Béla Bollobás  “Random Graphs”, Cambridge Studies in Advanced Mathematics  Cambridge University Press, 2001  DOI: 10.1017/CBO9780511814068
  * [8] Béla Bollobás and Paul Erdős  “Cliques in random graphs”  In _Mathematical Proceedings of the Cambridge Philosophical Society_ 80.3 Cambridge University Press, 1976, pp. 419–427  DOI: 10.1017/S0305004100053056
  * [9] Boris Bukh and Benny Sudakov  “Induced subgraphs of Ramsey graphs with many distinct degrees”  In _Journal of Combinatorial Theory, Series B_ 97.4, 2007, pp. 612–619  DOI: https://doi.org/10.1016/j.jctb.2006.09.006
  * [10] D. Conlon, R. Morris, W. Samotij and D. Saxton  “The number of distinct degrees in an induced subgraph of a random graph”  In _unpublished_
  * [11] David Conlon, Jacob Fox and Benny Sudakov  “Recent developments in graph Ramsey theory”  In _Surveys in Combinatorics 2015_ , London Mathematical Society Lecture Note Series  Cambridge University Press, 2015, pp. 49–118  DOI: 10.1017/CBO9781316106853.003
  * [12] P. Erdős  “On a lemma of Littlewood and Offord”  In _Bulletin of the American Mathematical Society_ 51.12 American Mathematical Society, 1945, pp. 898–902  DOI: bams/1183507531
  * [13] P. Erdős  “Some of my favourite problems in various branches of Combinatorics”  In _Le mathematiche_ 47.2, 1992, pp. 231–240  URL: https://lematematiche.dmi.unict.it/index.php/lematematiche/article/view/587
  * [14] P. Erdős  “Some remarks on the theory of graphs”  In _Bulletin of the American Mathematical Society_ 53.4 American Mathematical Society, 1947, pp. 292–294  DOI: bams/1183510596
  * [15] P. Erdős and G. Szekeres  “A Combinatorial Problem in Geometry”  In _Classic Papers in Combinatorics_ Boston, MA: Birkhäuser Boston, 1987, pp. 49–56  DOI: 10.1007/978-0-8176-4842-8˙3
  * [16] P. Erdős and A. Szemerédi  “On a Ramsey-type theorem”  In _Period Math Hung_ 2.1, 1972, pp. 295–299  DOI: https://doi.org/10.1007/BF02018669
  * [17] Asaf Ferber and Michael Krivelevich  “Every graph contains a linearly sized induced subgraph with all degrees odd”, 2021  arXiv:2009.05495 [math.CO]
  * [18] R.L. Graham, B.L. Rothschild and J.H. Spencer  “Ramsey Theory”, Wiley Series in Discrete Mathematics and Optimization  Wiley, 1991
  * [19] Matthew Jenssen, Eoin Long, Peter Keevash and Liana Yepremyan  “Distinct degrees in induced subgraphs”  In _Proceedings of the American Mathematical Society_ 148.9 American Mathematical Society, 2020, pp. 3835–3846  DOI: 10.1090/proc/15060
  * [20] Ross Kang, Eoin Long, Viresh Patel and Guus Regts  “On a Ramsey-type problem of Erdős and Pach”  In _Bulletin of the London Mathematical Society_ 49.6 London Mathematical Society, 2017, pp. 991–999  DOI: 10.1112/blms.12094
  * [21] Matthew Kwan and Benny Sudakov  “Proof of a conjecture on induced subgraphs of Ramsey graphs”  In _Transactions of the American Mathematical Society_ 372, 2017  DOI: 10.1090/tran/7729
  * [22] Matthew Kwan and Benny Sudakov  “Ramsey Graphs Induce Subgraphs of Quadratically Many Sizes”  In _International Mathematics Research Notices_ 2020, 2017  DOI: 10.1093/imrn/rny064
  * [23] Xin Li  “Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors”  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2017  Montreal, Canada: Association for Computing Machinery, 2017, pp. 1144–1156  DOI: 10.1145/3055399.3055486
  * [24] L. Lovász  “Combinatorial Problems and Exercises”, AMS/Chelsea publication  North-Holland Publishing Company, 1993  URL: https://books.google.co.uk/books?id=e99fXXYx9zcC
  * [25] Bhargav Narayanan, Julian Sahasrabudhe and István Tomon  “Ramsey Graphs Induce Subgraphs of Many Different Sizes”  In _Combinatorica_ 39, 2016  DOI: 10.1007/s00493-017-3755-0
  * [26] Bhargav Narayanan and István Tomon  “Induced Subgraphs With Many Distinct Degrees”  In _Combinatorics, Probability and Computing_ 27.1 Cambridge University Press, 2018, pp. 110–123  DOI: 10.1017/S0963548317000256
  * [27] H.. Prömel and V. Rödl  “Non-Ramsey Graphs Are clogn-Universal”  In _Journal of Combinatorial Theory, Series A_ 88.2, 1999, pp. 379–384  DOI: https://doi.org/10.1006/jcta.1999.2972
  * [28] L. Pyber, V. Rödl and E. Szemerédi  “Dense Graphs without 3-Regular Subgraphs”  In _Journal of Combinatorial Theory, Series B_ 63.1, 1995, pp. 41–54  DOI: https://doi.org/10.1006/jctb.1995.1004
  * [29] J.L. Ramírez-Alfonsín and B.A. Reed  “Perfect Graphs”, Wiley Series in Discrete Mathematics and Optimization  Wiley, 2001
  * [30] F.. Ramsey  “On a Problem of Formal Logic”  In _Proceedings of the London Mathematical Society_ s2-30.1, 1930, pp. 264–286  DOI: https://doi.org/10.1112/plms/s2-30.1.264
  * [31] A.. Scott  “Large Induced Subgraphs with All Degrees Odd”  In _Combinatorics, Probability and Computing_ 1.4 Cambridge University Press, 1992, pp. 335–349  DOI: 10.1017/S0963548300000389
  * [32] S. Shelah  “Erdős and Rényi Conjecture”  In _J. Comb. Theory, Ser. A_ 82, 1998, pp. 179–185