șs țt

# A bipartite version of the Erdős–McKay conjecture

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.

###### Abstract

An old conjecture of Erdős and McKay states that if all homogeneous sets in an
$n$-vertex graph are of order $O(\log n)$ then the graph contains induced
subgraphs of each size from $\\{0,1,\ldots,\Omega(n^{2})\\}$. We prove a
bipartite analogue of the conjecture: if all balanced homogeneous sets in an
$n\times n$ bipartite graph are of order $O(\log n)$ then the graph contains
induced subgraphs of each size from $\\{0,1,\ldots,\Omega(n^{2})\\}$.

##  1 Introduction

Given a graph $G$ we write $\mbox{hom}(G)$ to denote the homogeneous number of
$G$, given by:

$\displaystyle\operatorname{hom}(G):=\max\big{\\{}t\in{\mathbb{N}}:\exists\
U\subset V(G)\mbox{ with }|U|=t\mbox{ such that }G[U]\mbox{ is complete or
empty}\big{\\}}.$

In its simplest form, Ramsey’s theorem [23], [10] states that any $n$-vertex
graph $G$ satisfies $\operatorname{hom}(G)=\Omega(\log n)$ and a classical
result of Erdős [9] shows that this behaviour is essentially optimal; there
are $n$-vertex _Ramsey graphs_ $G_{0}$ with $\operatorname{hom}(G_{0})=O(\log
n)$. However, the existence of such Ramsey graphs has only been demonstrated
indirectly via probabilistic methods and finding explicit constructions of
graphs exhibiting such behaviour remains a tantalising open problem (a $1000
Erdős problem [8]).

Despite the challenges in constructing Ramsey graphs, and perhaps influenced
by them, there has been much success in understanding the intrinsic properties
possessed by these graphs. For example, Ramsey graphs have been shown to
(roughly) exhibit similar behaviour to the Erdős-Renyi random graph w.h.p.
with respect to edge density [11], non-isomorphic induced subgraphs [24],
universality of small induced subgraphs [22], and the possible edge sizes and
degrees appearing in induced subgraphs [16], [15], [13].

A challenging remaining problem in this context is the Erdős–McKay conjecture
[12]. Informally, the conjecture asks whether every Ramsey graph must contain
(essentially) the entire interval of possible induced subgraph sizes. More
precisely the conjecture asks whether every $n$-vertex graph $G$ with
$\operatorname{hom}(G)\leq C\log n$ satisfies
$\\{0,\ldots,\Omega_{C}(n^{2})\\}\subset\\{e(G[U]):U\subset V(G)\\}$. The best
known bound for the conjecture is due to Alon, Krivelevich and Sudakov [1] who
proved that such graphs necessarily contain induced subgraphs of each size in
$\\{0,\ldots,n^{\Omega_{C}(1)}\\}$. The conjecture was also proved for random
graphs (in a strong form) by Calkin, Frieze and McKay in [7]. More recently,
Kwan and Sudakov [16] gave further support proving that such graphs
necessarily contain induced subgraphs of $\Omega_{C}(n^{2})$ different sizes,
which improved an earlier almost quadratic bound of Narayanan, Sahasrabuhde
and Tomon [18].

Our aim here is to study the natural analogue of this conjecture for bipartite
graphs. Recall that the bipartite analogue of Ramsey’s theorem states that any
balanced bipartite graph $G=(V_{1},V_{2},E)$ with $|V_{1}|=|V_{2}|=n$ contains
either $K_{t,t}$ or $\overline{K_{t,t}}$ as an induced subgraph with
$t=\Omega(\log n)$. This type of behaviour is again known to be the best
possible in general, though explicit constructions of ‘bipartite Ramsey
graphs’ are also unknown. In fact, these are more challenging in a sense as
such constructions would lead to constructions in the usual Ramsey setting
(see e.g. [5]).

Given the context above, and the difficulties in the Erdős–McKay conjecture,
it is natural to ask what can be said about the edge sizes of induced
subgraphs in balanced $n$-vertex bipartite Ramsey graphs? A general result of
Narayanan, Sahasrabuhde and Tomon [20] gives some information here. These
authors also studied a generalisation of the Erdős ‘multiplication table
problem’, and showed that any bipartite graph with $m$ edges has induced
subgraphs of $\widetilde{\Omega}(m)$ distinct sizes. Recently Baksys and Chen
[4] raised the bipartite Ramsey question and proved an analogue of Kwan and
Sudakov’s theorem: any balanced bipartite Ramsey graph on vertex classes of
order $n$ has induced subgraphs of $\Omega(n^{2})$ different edge sizes.

Our main theorem extends this line of research, proving an analogue of the
Erdős–McKay conjecture in the bipartite setting. Before stating it, we give a
more precise definition of the Ramsey property for bipartite graphs, in a
slightly more general setting.

######  Definition 1.1.

Given $C>0$, a graph $G=(V_{1},V_{2},E)$ is called $C$_-bipartite-Ramsey_ if
for any $t_{1}\geq C\log_{2}|V_{1}|$ and $t_{2}\geq C\log_{2}|V_{2}|$ there is
no induced copy of $K_{t_{1},t_{2}}$ or $\overline{K_{t_{1},t_{2}}}$ in $G$.

We will often simply say that $G$ is a $C$-Ramsey graph when it is clear that
$G$ is bipartite.

We can now state our main result, which gives an analogue of the Erdős–McKay
conjecture in the bipartite Ramsey setting.

######  Theorem 1.2.

Given $C>0$ there is $\alpha>0$ such that the following holds. Suppose that
$G=(V_{1},V_{2},E)$ is a $C$-bipartite-Ramsey graph. Then
$\\{0,\ldots,\alpha|V_{1}||V_{2}|\\}\subset\\{e(G[U]):U\subset V(G)\\}$.

Our proof of Theorem 1.2 follows a similar line of approach to [18], [16] and
[4], in which we first show that one can get close to the desired edge sizes
and then refine this to show that certain perturbations are typically
available to allow one to adjust to the exact size. Anti-concentration
estimates are a key tool in ensuring that the desired perturbations are
‘sufficiently rich’ here. We prove such bounds using diversity of vertices and
diversity for pairs of vertices, introduced by Bukh and Sudakov [6] and Kwan
and Sudakov [16] respectively, though a different notion of pair diversity was
key here in obtaining the required behaviour. We were also able to keep track
of the perturbation structure using certain sumset techniques.

Before beginning on the proof of the theorem, we will make two simple
observations on the relation between vertex classes and the size of a
$C$-bipartite-Ramsey graph $G=(V_{1},V_{2},E)$, which are useful for future
reference.

  * •

Given any $\alpha\in(0,1)$ and $U_{i}\subset V_{i}$ with
$|U_{i}|\geq|V_{i}|^{\alpha}$ for $i=1,2$, the induced graph $G[U_{1},U_{2}]$
is $(C\alpha^{-1})$-Ramsey.

  * •

Suppose that $|V_{1}|\geq|V_{2}|$ and let $W\subset V_{2}$ of size
$|W|=2C\log|V_{2}|$. By the pigeonhole principle there is a set $U\subset
V_{1}$ with $|U|\geq|V_{1}|2^{-|W|}$ such that for all $u\in U$ one has
$N_{G}^{W}(u)=W^{\prime}$. It follows that $G$ contains an induced
$K_{t_{1},t_{2}}$ or $\overline{K_{t_{1},t_{2}}}$ where
$t_{1}=|V_{1}|2^{-|W|}$ and $t_{2}=C\log|V_{2}|$. As $G$ is $C$-Ramsey it
follows that $t_{1}\leq C\log|V_{1}|$, which in particular gives
$|V_{1}|\leq|V_{2}|^{O_{C}(1)}$. Thus the vertex classes of $C$-bipartite-
Ramsey graphs are necessarily polynomially related.

Notation. Given disjoint sets $V_{1}$ and $V_{2}$ we write $G=(V_{1},V_{2},E)$
to represent a bipartite graph $G$ with vertex set $V(G)=V_{1}\sqcup V_{2}$
and edge set $E(G)=E\subset V_{1}\times V_{2}$. The _edge density_ of $G$ is
given by $e(G)\large{/}|V_{1}||V_{2}|$. Given $U_{i}\subset V_{i}$ for $i=1,2$
we write $G[U_{1},U_{2}]$ to denote the induced subgraph
$G[U_{1},U_{2}]=(U_{1},U_{2},E\cap(U_{1}\times U_{2}))$.

Given a graph $G$ and $u,v\in V(G)$, we write $u\sim v$ if $u$ and $v$ are
adjacent vertices in $G$. 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 vertices $u,v\in V(G)$ we write $\text{div}_{G}(u,v)$ for the symmetric
difference $N(u)\triangle N(v)$. The _biased diversity_ of $u$ and $v$,
denoted by $\text{divb}_{G}(u,v)$, is going to be the largest of the two sets
$N(u)\setminus N(v)$ and $N(v)\setminus N(u)$. If these have the same size
then we arbitrarily pick one of the sets to be $\text{divb}_{G}(u,v)$. Clearly
$|\text{divb}_{G}(u,v)|\geq|\text{div}_{G}(u,v)|/2$.

We will also be interested in _ordered pairs_ of vertices
$\bm{p}=(u,v)\in\binom{V(G)}{2}$. Naturally, given such a pair $\bm{p}$ we can
define $\text{div}_{G}(\bm{p}):=\text{div}_{G}(u,v)$. We will also make the
convention throughout that all pairs are ordered so that
$\text{divb}_{G}(\bm{p})=N(u)\setminus N(v)$, which implies $d(u)\geq d(v)$.
Moreover, for later diversity purposes, we will need to study
$\operatorname{deg-diff}^{S}({\bf p}):=d_{G}^{S}(u)-d_{G}^{S}(v)$.

Given integers $m\leq n$ we will write $[m,n]$ to denote the interval
$\\{m,m+1,\ldots,n\\}$ and given $n\in{\mathbb{N}}$ we write $[n]$ for the
interval $\\{1,\ldots,n\\}$. All logarithms in the paper will be base $2$
unless otherwise stated. Floor and ceiling signs are omitted throughout for
clarity of presentation.

##  2 Collected tools

###  2.1 Density control

We start by proving a density result for bipartite Ramsey graphs. The proof
uses a well-known argument due to Kovari$-$Sós$-$Turán [14].

######  Lemma 2.1.

Given $C>1$ there is $n_{C}\in\mathbb{N}$ such that the following holds.
Suppose that $G=(V_{1},V_{2},E)$ is a $C$-bipartite-Ramsey graph with
$|V_{1}|,|V_{2}|\geq n_{C}$. Then $G$ has edge density between $(16C)^{-1}$
and $1-(16C)^{-1}$.

###### Proof.

To see this let $\varepsilon=(16C)^{-1},t_{1}=C\log|V_{1}|$,
$t_{2}=C\log|V_{2}|$ and assume that $t_{1}\leq t_{2}$. It is enough to show
that our graph cannot have density larger than $1-\varepsilon$, as the other
statement follows by looking at the (bipartite) complement $\overline{G}$.

For the sake of contradiction, suppose the density $d(G)>1-\varepsilon$, and
let us count in two ways the number $M$ of stars $K_{t_{1},1}$ which are
formed by taking a single vertex in $V_{2}$ and $t_{1}$ of its neighbours. On
one hand, each vertex $v\in V_{2}$ contributes $\binom{d(v)}{t_{1}}$ stars,
giving us:

$\displaystyle M\geq\sum_{v\in
V_{2}}\binom{d(v)}{t_{1}}\geq|V_{2}|\cdot\binom{e(G)/|V_{2}|}{t_{1}}\geq|V_{2}|\cdot\binom{(1-\varepsilon)|V_{1}|}{t_{1}}\geq|V_{2}|\cdot(1-2\varepsilon)^{t_{1}}\binom{|V_{1}|}{t_{1}}.$
(1)

Here we have used Jensen’s inequality for the map $x\to\binom{x}{t_{1}}$ in
the second inequality, and that $t_{1}\leq\varepsilon|V_{1}|$ for the final
step, as $|V_{1}|\geq n_{C}$.

On the other hand, if $G$ is $K_{t_{1},t_{2}}$-free then for each subset
$S\subset V_{1}$ of $t_{1}$ vertices there are at most $t_{2}-1$ vertices in
$V_{2}$ that can form a star with $S$, and so
$M\leq(t_{2}-1)\binom{|V_{1}|}{t_{1}}$. Combined with (1) this gives
$|V_{2}|\leq(t_{2}-1)(1-2\varepsilon)^{-t_{1}}\leq|V_{2}|^{1/2}e^{4\varepsilon
t_{1}}$, using that $|V_{2}|\geq n_{C}$ and that $1-x\geq e^{-2x}$ for
$x\in[0,1/2]$. It follows that $|V_{2}|\leq e^{8\varepsilon
t_{2}}=|V_{1}|^{8C\varepsilon}=|V_{2}|^{1/2}$, a contradiction. ∎

######  Corollary 2.2.

For any $C>1$ there exists $n_{C}\in\mathbb{N}$ such that the following holds
true. Any $C$-bipartite-Ramsey graph $G=(V_{1},V_{2},E)$ with
$|V_{1}|,|V_{2}|\geq n_{C}$ contains at least $2|V_{1}|/3$ vertices in $V_{1}$
which all have degrees between $(32C)^{-1}|V_{2}|$ and
$(1-(32C)^{-1})|V_{2}|$.

###### Proof.

Suppose for the sake of contradiction that the conclusion is not true. Let
$\varepsilon:=1/32C$ and suppose at most $2|V_{1}|/3$ vertices $v\in V_{1}$
have degrees between $\varepsilon|V_{2}|$ and $(1-\varepsilon)|V_{2}|$. Then,
by the pigeonhole principle, without loss of generality we can assume that
there is a set $U_{1}\subset V_{1}$ with $|U_{1}|\geq|V_{1}|/6$ such that all
vertices in $U_{1}$ have degree less than $\varepsilon|V_{2}|$. But then the
edge density of the induced bipartite graph $G[U_{1},V_{2}]$ is less than
$\varepsilon$. On the other hand, it is easy to see that if $G$ is
$C$-bipartite-Ramsey, since $6|U_{1}|\geq|V_{1}|\geq n_{C}$, the graph
$G[U_{1},V_{2}]$ is $2C$-bipartite-Ramsey. This is a contradiction by Lemma
2.1. ∎

In particular, the following consequence of Corollary 2.2 will be useful
later.

######  Lemma 2.3.

Given $C>1$ and a natural number $L$ there is $n_{0}\in\mathbb{N}$ such that
the following holds. Suppose that $G=(V_{1},V_{2},E)$ is a $C$-bipartite-
Ramsey graph with $|V_{i}|\geq n_{0}$. Then, taking
$\varepsilon_{i}:=(64C)^{-i}$ for all $i\in[L]$, one can find vertices
$U:=\\{u_{1},u_{2},\ldots,u_{L}\\}\subset V_{1}$ such that
$\big{|}N(u_{i})\setminus\underset{j<i}{\bigcup}N(u_{j})\big{|}\geq\varepsilon_{i}|V_{2}|$
and $\big{|}V_{2}\setminus\underset{j\leq
i}{\bigcup}N(u_{j})\big{|}\geq\varepsilon_{i}|V_{2}|$ for all $i\in[L]$.

###### Proof.

By Corollary 2.2 we can pick $u_{1}\in V_{1}$ such that
$d(u_{1})\in[\varepsilon_{1}|V_{2}|,(1-\varepsilon_{1})|V_{2}|]$. Our
requirement is clearly satisfied for $i=1$. Now let us assume that we have
found $u_{1},u_{2},\ldots,u_{i}$ with $i<L$ that satisfy our requirements and
let us look for a vertex $u_{i+1}$.

Let $S_{i}:=V_{1}\setminus\\{u_{1},u_{2},\ldots,u_{i}\\}$ and
$T_{i}:=V_{2}\setminus\underset{j\leq i}{\cup}N(u_{j})$. Note that
$|S_{i}|\geq|V_{1}|-L\geq|V_{1}|^{1/2}$ and that
$|T_{i}|\geq(64C)^{-L}|V_{2}|\geq|V_{2}|^{1/2}$ since $|V_{1}|,|V_{2}|\geq
n_{0}$. Therefore, the subgraph $G[S_{i},T_{i}]$ is $(2C)$-bipartite-Ramsey.
Thus, by Corollary 2.2, it follows that we can find a vertex $u_{i+1}\in
S_{1}$ such that
$d^{T_{i}}_{G}(u_{i+1})\in[\varepsilon_{1}|T_{i}|,(1-\varepsilon_{1})|T_{i}|]$.
But this is precisely the vertex we were looking for, as then we have
$|N(u_{i+1})\setminus\underset{j\leq i}{\cup}N(u_{j})|\geq
d^{T_{i}}_{G}(u_{i+1})\geq\varepsilon_{1}|T_{i}|\geq\varepsilon_{i+1}|V_{2}|$
and we also get that $|V_{2}\setminus\underset{j\leq
i+1}{\cup}N(u_{j})|\geq|T_{i}\setminus
N^{T_{i}}_{G}(u_{i+1})|\geq\varepsilon_{1}|T_{i}|\geq\varepsilon_{i+1}|V_{2}|$.

By repeating this step $L$ times we reach our conclusion. ∎

###  2.2 Richness and diversity

We will use the notion of richness, which was introduced by Kwan and Sudakov
[16].

######  Definition 2.4.

Given $\delta,\varepsilon>0$, a bipartite graph $G=(V_{1},V_{2},E)$ is
$(\delta,\varepsilon)$_-bipartite-rich_ if for each $i\in\\{1,2\\}$ the
following holds: for every set $W\subset V_{i}$ with $|W|\geq\delta|V_{i}|$
there are at most $|V_{3-i}|^{1/5}$ vertices $v\in V_{3-i}$ such that
$|N(v)\cap W|\leq\varepsilon|V_{3-i}|$ or $|\overline{N}(v)\cap
W|<\varepsilon|V_{3-i}|$.

By adapting a result of Kwan and Sudakov (Lemma 4 in [16]) to the bipartite
context, we show that the Ramsey setting guarantees richness.

######  Lemma 2.5.

Given $C,\delta>0$ there is $\varepsilon>0$ and $n_{0}\in\mathbb{N}$ such that
the following holds true. Every $C$-bipartite-Ramsey graph $G=(V_{1},V_{2},E)$
with $|V_{1}|,|V_{2}|\geq n_{0}$ is $(\delta,\varepsilon)$-bipartite-rich.

###### Proof.

It is enough to prove that the bipartite-richness condition holds when $i=1$.
So set $\varepsilon:=(200C)^{-1}$ and suppose there is a set $U_{1}\subset
V_{1}$ with $|U_{1}|\geq\delta|V_{1}|$ which contradicts the bipartite-
richness condition – more precisely that there is a set $W_{2}\subset V_{2}$
with $|W_{2}|\geq|V_{2}|^{1/5}$ such that $|N(v)\cap
U_{1}|<\varepsilon|U_{1}|$ or $|\overline{N(v)}\cap U_{1}|<\varepsilon|U_{1}|$
for all $v\in W_{2}$. Without loss of generality, we can assume that there is
a subset $U_{2}\subset W_{2}$ of size $|V_{2}|^{1/5}/2$ such that $|N(v)\cap
U_{1}|<\varepsilon|U_{1}|$ for all $v\in W_{2}$. But this means that the edge
density of $G[U_{1},U_{2}]$ is less than $\varepsilon$.

On the other hand, as $|U_{i}|\geq|V_{i}|^{1/5}/2\geq|V_{i}|^{1/6}$ as
$|V_{i}|\geq n_{C}$, and since $G=G[V_{1},V_{2}]$ is $C$-Ramsey, it follows
$G[U_{1},U_{2}]$ is $6C$-Ramsey. But by Lemma 2.1 such a graph must have edge
density at least $(196C)^{-1}>\varepsilon,$ which is a contradiction, thus
proving our result. ∎

Next, we discuss the notion of _diversity_ , which was introduced by Bukh and
Sudakov [6] (in the non-bipartite setting).

######  Definition 2.6.

A bipartite graph $G=(V_{1},V_{2},E)$ is said to be $c$_-bipartite-diverse_ if
for each $i\in\\{1,2\\}$ the following holds: every vertex $v\in V_{i}$ has
$|\text{div}_{G}(v,w)|\leq c|V_{3-i}|$ for at most $|V_{i}|^{1/5}$ vertices
$w\in V_{i}$.

We also introduce a useful diversity notion for pairs. We note that diversity
for pairs was also considered by Kwan and Sudakov in [16], who considered
multisets of neighbourhoods, but we require a different notion suitable for
our later applications.

######  Definition 2.7.

A bipartite graph $G=(V_{1},V_{2},E)$ is said to be $(c,\alpha)$_-pair-
diverse_ if for each $i\in\\{1,2\\}$ the following holds true for both
$i=1,2$. For each ordered pair $\bm{p}\in\binom{V_{i}}{2}$ with
$|\text{div}(\bm{p})|\geq\alpha|V_{3-i}|$ there are at most $|V_{i}|^{1/5}$
pairwise vertex disjoint pairs $\bm{p}^{\prime}=(x,y)\in\binom{V_{i}}{2}$ such
that $|\text{divb}_{G}(\bm{p})\setminus N(x)|\leq c|V_{3-i}|$ or
$|\text{divb}_{G}(\bm{p})\setminus N(y)|\leq c|V_{3-i}|$.

######  Lemma 2.8.

Let $G=(V_{1},V_{2},E)$ be a $(\delta,\varepsilon)$-bipartite-rich graph with
$\delta\leq 1/2$. Then:

  1. (i)

$G$ is $\varepsilon/2$-diverse;

  2. (ii)

$G$ is $(\alpha\varepsilon/2,\alpha)$-pair-diverse for all $\alpha\geq
2\delta$.

###### Proof.

It is enough to show that each property holds when taking $i=1$.

_(i)_ For each $v\in V_{1}$ either $|N(v)|\geq|V_{2}|/2$ or
$|\overline{N(v)}|\geq|V_{2}|/2$. In the former case, all but at most
$|V_{1}|^{1/5}$ vertices $w\in V_{1}$ we have
$|N(v)\cap\overline{N(w)}|\geq\varepsilon|N(v)|\geq\varepsilon/2\cdot|V_{2}|$,
and in the latter, for all but at most $|V_{1}|^{1/5}$ vertices $w\in V_{1}$
we have
$|\overline{N(v)}\cap{N(w)}|\geq\varepsilon|\overline{N(v)}|\geq\varepsilon/2\cdot|V_{2}|$.
In either case, there are at most $|V_{1}|^{1/5}$ vertices $w\in V_{1}$ with
$|\text{div}_{G}(v,w)|<\varepsilon/2\cdot|V_{2}|$, as desired.

_(ii)_ Suppose now there is an ordered pair $\bm{p}\in\binom{V_{1}}{2}$ and a
collection $Y$ of $|V_{1}|^{1/5}$ vertex disjoint pairs
$\bm{p}_{i}:=(x_{i},y_{i})\in\binom{V_{1}}{2}$ such that
$|\text{divb}(\bm{p})\setminus N(x_{i})|\leq\alpha\varepsilon/2\cdot|V_{2}|$
for each $i$. Note that if $|\text{div}(\bm{p})|\geq\alpha|V_{2}|$ then
$|\text{divb}(\bm{p})|\geq\alpha/2\cdot|V_{2}|$. But in this case there are
$|V_{1}|^{0.5}$ distinct vertices $z_{i}\in\\{x_{i},y_{i}\\}$ such that
$|\text{divb}(\bm{p})\cap\overline{N(z_{i})}|\leq\alpha\varepsilon/2\cdot|V_{2}|\leq\varepsilon|\text{divb}(\bm{p})|$,
which contradicts the richness of the set $\text{divb}(\bm{p})$. ∎

###  2.3 Probabilistic tools

Throughout the proof we will use Markov’s inequality, Chebyshev’s inequality,
the Chernoff bound and Turán’s theorem. Statements and proofs of all of these
can be found, for example, in [3]. We will also need a probabilistic variation
of the Erdős-Littlewood-Offord theorem, whose proof can be found, for instance
in [13].

######  Theorem 2.9.

Fix some non-zero parameters $a_{1},a_{2},\dots,a_{n}\in\mathbb{R}$ and
$\alpha\in(0,0.5]$, then let $p_{1},p_{2},\dots,p_{n}\in[\alpha,1-\alpha]$.
Suppose that $X_{1},X_{2},\dots,X_{n}$ are independent Bernoulli random
variables with $X_{i}\sim Be(p_{i})$. Then the following holds:

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

The following natural proposition will be useful in our proof of Theorem 1.2.

######  Proposition 2.10.

Given an integer $d\geq 2$, there is an integer $n_{0}:=n_{0}(d)$ such that if
$X$ is a uniformly chosen subset of $[n]$, where $n\geq n_{0}$, then for any
integer $k$ with $0\leq k<d$ one has:

$\frac{1}{d+1}\leq\mathbb{P}\big{(}|X|\equiv
k\pmod{d}\big{)}\leq\frac{1}{d-1}.$

To avoid an involved computational argument, we show that it can be easily
deduced from a standard result about stochastic processes. The next few
paragraphs represent a brief introduction which is given for completeness. For
more details, the reader can refer to [21].

A _Markov chain_ is a sequence $\bm{X}:=(X_{n})_{n\geq 0}$ of random variables
taking values in some common ground set $I$ such that, for all $n\geq 1$ and
$i_{0},i_{1},\ldots,i_{n}\in I$, one has:

$\mathbb{P}\big{(}X_{n}=i_{n}\ |\ X_{0}=i_{0};\ X_{1}=i_{1};\ \ldots;\
X_{n-1}=i_{n-1}\big{)}=\mathbb{P}\big{(}X_{n}=i_{n}\ |\
X_{n-1}=i_{n-1}\big{)}.$

A Markov chain is called _homogeneous_ if, in addition,
$p_{i,j}:=\mathbb{P}(X_{n}=j|X_{n-1}=i)$ depends only on the states $i$ and
$j$, not on the time $n$. These quantities are known as the transition
probabilities of the chain. We are only interested in homogeneous chains and
we can observe that in order to describe such a chain it is enough to have the
initial distribution $\lambda$ of $X_{0}$, given by
$\lambda_{i}:=\mathbb{P}(X_{0}=i)$, and the transition matrix
$P:=(p_{i,j})_{i,j\in I}$. Moreover, if we write $p_{i,j}^{(n)}$ for
$\mathbb{P}(X_{k+n}=j|X_{k}=i)$ then it is easy to see that
$p_{i,j}^{(n)}=(P^{n})_{i,j}$.

A Markov chain $\bm{X}$ on the set $I$ with transition matrix
$P:=(p_{i,j})_{i,j\in I}$ is called _irreducible_ if for all $i,j\in I$ there
is $n\geq 0$ such that $p_{i,j}^{(n)}>0$. The _period_ of a state $i\in I$ is
defined to be the greatest common divisor of the set $\\{n\geq
1:p_{i,i}^{(n)}>0\\}$. The Markov chain $\bm{X}$ is called _aperiodic_ if all
its states have period $1$.

We say $\pi=(\pi_{i})_{j\in I}$ is a _stationary distribution_ for a Markov
chain $\bm{X}$ if starting the chain from $X_{0}$ with distribution $\pi$
implies that $X_{n}$ has distribution $\pi$ for all $n\geq 1$. As the
distribution of $X_{n}$ is given by $\pi P^{n}$, where $P$ is the transition
matrix, we deduce that $\pi$ is a stationary distribution if and only if $\pi
P=\pi$.

######  Theorem 2.11.

Suppose $\bm{X}$ is an irreducible and aperiodic Markov chain on a ground set
$I$ with transition matrix $P$, stationary distribution $\pi$ and any initial
distribution. Then, for all $j\in I$, one has $\mathbb{P}(X_{n}=j)\to\pi_{j}$
as $n\to\infty$.

###### Proof of Proposition 2.10.

We can view choosing $X$ as going through each number from $1$ to $n$ and
independently tossing a fair coin for each to decide whether it is an element
of $X$ or not. Thus $|X|\ (\text{mod }d)$ can be viewed as a Markov chain on
$\\{0,1,2,\ldots,d-1\\}$ starting at $0$ and with transition probabilities
$p_{i,i}=p_{i,i-1}=0.5$ for each $0\leq i<d$, where indices ar taken modulo
$d$. This chain is aperiodic as $p_{i,i}^{(1)}=0.5$ and it is also irreducible
as we can reach state $i$ from state $j$ in $i-j\ (\text{mod }d)$ steps with
positive probability. It is easy to see that the stationary distribution $\pi$
is given by $\pi_{i}=1/d$. The conclusion now follows from Theorem 2.11. ∎

###  2.4 Progressions in sumsets

Given sets $A_{1},\ldots,A_{K}\subset{\mathbb{Z}}$, the sumset of
$A_{1},\ldots,A_{K}$ is the set $A_{1}+\ldots+A_{K}$ given by:

$\displaystyle A_{1}+\cdots+A_{K}=\big{\\{}a_{1}+\cdots+a_{K}:a_{i}\in
A_{i}\mbox{ for all }i\in[K]\big{\\}}.$

Much research has focused on the topic of estimating the size or understanding
the structure of sumsets under certain assumptions on the sets (see for
example [25] or Chapter 2 of [26]). For our purposes, the following elementary
estimate will suffice.

######  Lemma 2.12.

Given $\delta,B>0$ there are $C,d_{0}\geq 1$ such that the following holds.
Suppose that $A_{1},\ldots,A_{K}\subset[-M,M]$ with $K\geq CM$ and that
$|A_{i}|\geq\delta M\geq 2$ for all $i\in[K]$. Then there is
$a\in{\mathbb{Z}}$ and $d\in{\mathbb{N}}$ with $1\leq d\leq d_{0}$ such that:

$\displaystyle\big{\\{}a+id:0\leq i\leq BM^{2}\big{\\}}\subset
A_{1}+A_{2}+\cdots+A_{K}.$ (2)

###### Proof.

We will prove the statement under the assumption that $A_{i}\subset[0,M]$ for
all $i\in[K]$. Note that the general case follows immediately by taking
translations of the sets, i.e. replacing $A_{i}$ with
$A_{i}^{\prime}=A_{i}-c_{i}$ for $c_{i}=\min\\{a:a\in A_{i}\\}$. Indeed if (2)
holds for $A_{1}^{\prime},\ldots,A_{K}^{\prime}$ (which may now lie in
$[0,2M]$ instead of $[-M,M]$) then (2) also holds for $A_{1},\ldots,A_{K}$
(possibly with a different value of $a$). The same argument also allows us to
assume that $0\in A_{i}$ for all $i\in[K]$.

Moreover, note that as $|A_{i}|\geq\delta M$ for all $i\in[K]$, we have
$|A_{i}\cap[0,M^{\prime}]|\geq 2\delta M/3\geq 2$ for at least $\delta M/3$
values of $M^{\prime}\in[0,M]$ (for $M^{\prime}=M,M-1,M-2,\ldots$). By double
counting, it follows that there is $0<M^{\prime}\leq M$ and some $I\subset[K]$
with $|I|\geq\delta K/3\geq(\delta C/3)M$ such that
$|A_{i}\cap[0,M^{\prime}]|\geq 2\delta M/3\geq 2$ and $M^{\prime}\in A_{i}$
for all $i\in I$. By restricting all the sets to $[0,M^{\prime}]$, then
reordering them and using that $0\in A_{i}$ for all $i\in[K]$, by slightly
adjusting the parameter $C$ we can assume that $\\{0,M\\}\subset A_{i}$ for
all $i\in[K]$.

Given a set $S\subset{\mathbb{Z}}$, we will let
$\overline{S}:=\\{a\in[0,M-1]:a\equiv s\mod M\mbox{ for some }s\in S\\}$. For
each $i\in[K]$ let $S_{i}:=\overline{A_{1}+\cdots+A_{i}}$. By reordering the
sets $A_{1},\ldots,A_{K}$, we may assume that $|S_{i+1}|>|S_{i}|$ for $i\leq
K^{\prime}$ and that $S_{i}=S_{K^{\prime}}$ for all $i\geq K^{\prime}$.
Observe that $S_{K^{\prime}}\subset[0,M-1]$ and that
$|S_{K^{\prime}}|\geq|S_{1}|+(K^{\prime}-1)\geq K^{\prime}+1$, therefore
$K^{\prime}<M$.

Now, as $0\in A_{i}$ for all $i\in[K]$, we have $0\in
S_{K^{\prime}}\subset\overline{S_{K^{\prime}}+A_{K^{\prime}+1}}=S_{K^{\prime}+1}$.
As $|S_{K^{\prime}+1}|=|S_{K^{\prime}}|$ it follows that $S_{K^{\prime}}$
contains the subgroup of ${\mathbb{Z}}_{M}$ generated by $A_{K^{\prime}+1}$.
As $|A_{K^{\prime}+1}|\geq\delta M$ it follows that there is some $d\leq
d_{0}(\delta)$ with $d|M$ such that $\\{id:0\leq i\leq M/d\\}\subset
S_{K^{\prime}}\subset S_{M}$.

To proceed with the last step, recall that $\\{0,M\\}\in A_{i}$ for all
$i\in[K]$. Using this, it is easy to see that as $\\{id:0\leq i\leq
M/d\\}\subset S_{K^{\prime}}\subset S_{M}$, we have $\\{M^{2}+id:0\leq i\leq
M/d\\}\subset A_{1}+\cdots+A_{2M}$. More generally, as $d|M$, we have:

$\big{\\{}M^{2}+id+jM:0\leq i\leq M/d,\mbox{ }0\leq j\leq K-2M\big{\\}}\subset
A_{1}+\cdots+A_{K},$

and so (2) holds by taking $a=M^{2}$ and $K\geq CM\geq(B+2)M$. This completes
the proof. ∎

##  3 Proof of Theorem 1.2

###  3.1 Pair-stars and pair-matchings

We start this section by defining two constructions which will be of central
importance in our attempt to find induced subgraphs of many sizes. Let
$G=(V_{1},V_{2},E)$ be a bipartite graph.

An $\varepsilon$_-pair-star_ of size $k$ rooted at $x_{0}$ associated to
$V_{1}$ is a set ${\cal P}_{S}=\\{x_{0},x_{1},x_{2},\ldots,x_{k}\\}\subset
V_{1}$ which satisfies the following properties:

  1. (i)

$|d_{G}(x_{j})-d_{G}(x_{0})|\leq{|V_{2}|}^{0.5}$ for all $j\in[k]$;

  2. (ii)

$|\text{div}(x_{i},x_{j})|\geq\varepsilon|V_{2}|$ for all $i\neq j$ in
$[0,k]$.

We define the head of ${\cal P}_{S}$ to be the set $H({\cal
P}_{S})=\\{x_{0}\\}$.

An $\varepsilon$_-pair-matching_ of size $k$ associated to $V_{1}$ is a
collection ${\cal P}_{M}=\\{\bm{p}_{1},\bm{p}_{2},\ldots,\bm{p}_{k}\\}$ of
vertex disjoint ordered pairs of vertices in $V_{1}$ which satisfy the
following properties:

  1. (i)

${\bf p}_{i}=(x_{i},y_{i})$ for all $i\in[k]$ and the pairs ${\bf
p}_{1},\ldots,{\bf p}_{k}$ are vertex disjoint;

  2. (ii)

$\operatorname{deg-diff}({\bm{p}_{i}})\leq|V_{2}|^{0.5}$ for all $i\in[k]$;

  3. (iii)

$|\text{divb}(\bm{p}_{i})\setminus N(x_{j})|\geq\varepsilon|V_{2}|$ and
$|\text{divb}(\bm{p}_{i})\setminus N(y_{j})|\geq\varepsilon|V_{2}|$ for all
$i\neq j$ in $[k]$.

We define the head of ${\cal P}_{M}$ to be $H({\cal
P}_{M})=\\{x_{i}:i\in[k]\\}$.

By swapping $V_{1}$ and $V_{2}$ above, we can define _pair-stars_ and _pair-
matchings_ associated to $V_{2}$. Our result in this subsection gives large
pair-stars or large pair-matchings in $C$-Ramsey graphs.

######  Lemma 3.1.

Given $C>1$ there is $\varepsilon>0$ and $n_{C}\in\mathbb{N}$ such that the
following holds. Suppose that $G=(V_{1},V_{2},E)$ is a $C$-bipartite-Ramsey
graph with $|V_{1}|\geq|V_{2}|/2\geq n_{C}$. Then either:

  * •

$V_{1}$ contains an $\varepsilon$-pair-star of size $|V_{1}|^{0.5}$, or

  * •

$V_{1}$ contains an $\varepsilon$-pair-matching of size $|V_{1}|^{0.5}$.

###### Proof.

Let us start by dividing the interval $[0,|V_{2}|]$ into
$\ell:={|V_{2}|}^{1/2}$ disjoint intervals $I_{1},I_{2},\ldots I_{l}$ of
length ${|V_{2}|}^{1/2}$ and let, for each interval $I_{j}$, $n_{j}$ denote
the number of vertices in $V_{1}$ whose degree lie in $I_{j}$. Now any
vertices $x,y\in I_{j}$ with $d(x)\geq d(y)$ give an ordered pair
$\bm{p}=(x,y)$ with $\operatorname{deg-diff}({{\bf p}})\leq{|V_{2}|}^{1/2}$.
Obviously $n_{1}+n_{2}+\ldots+n_{\ell}=|V_{1}|$, so by Jensen’s inequality the
collection $\mathcal{S}$ of such ordered pairs
$\bm{p}=(x,y)\in\binom{V_{1}}{2}$ has size:

$\displaystyle|{\cal
S}|\geq\sum_{j=1}^{\ell}\binom{n_{j}}{2}\geq\ell\cdot\binom{|V_{1}|/\ell}{2}\geq\frac{|V_{1}||\big{(}|V_{1}|/\ell-1\big{)}}{2}\geq\frac{|V_{1}|^{1.5}}{4},$

using $\ell=|V_{2}|^{0.5}\leq(2|V_{1}|)^{0.5}$ and $|V_{1}|\geq n_{C}$. By
Lemmas 2.8 and 2.5 we deduce that our graph $G$ is $\varepsilon_{0}$-diverse,
where $\varepsilon_{0}:=(400C)^{-1}$. Therefore, at most
$|V_{1}|^{1.2}=o(|\mathcal{S}|)$ pairs from $\mathcal{S}$ fail to be
${\varepsilon}_{0}$-diverse. By removing such pairs we obtain a collection
$\mathcal{S}_{0}$ of size at least $|V_{1}|^{1.5}/8$ such that
$\operatorname{deg-diff}({\bf p})\leq|V_{2}|^{1/2}$ and
$|\text{div}(\bm{p})|\geq\varepsilon_{0}|V_{2}|$ for all
$\bm{p}\in\mathcal{S}_{0}$.

Next, we view the elements of $\mathcal{S}_{0}$ as the (unordered) edges of a
graph $H$ on $V(G)$. We claim that either $H$ has a matching of size
$m:=|V_{1}|^{0.75}/4$ or a set of $m+1$ edges that have a common vertex. To
see why this is true, suppose that neither of these two events hold and let
$M$ be a largest matching in $H$. Then $|M|<m$ and so all the edges in
$e(H)\setminus M$ must be adjacent to an edge of $M$. But because of the other
condition, each edge of $M$ has at most $2m$ other edges adjacent to it. Thus
$e(H)<2m^{2}\leq|\mathcal{S}_{0}|$, which is a contradiction.

Let us now observe that this set of edges will create our _pair-star_ or
_pair-matching_. Indeed, assume first that we have obtained $m+1$ edges
$x_{0}x_{1},x_{0}x_{2},\ldots,x_{0}x_{m+1}$ in $\mathcal{S}_{0}$. Again, by
diversity, each vertex $x_{j}$ has at most $|V_{1}|^{0.2}$ other vertices
$x_{i}$ such that $|\text{div}(x_{j},x_{i})|<\varepsilon_{0}|V_{2}|$. Thus, by
Turán theorem there is a set $I\subset[0,m+1]$, with $0\in I$, of size at
least $(m+1)/(1+|V_{1}|^{0.2})\geq|V_{1}|^{0.5}$ such that
$|\text{div}(x_{j},x_{i})|\geq\varepsilon_{0}|V_{2}|$ for all $i\neq j$ in
$I$. Taking $x_{0}$ as the root gives our pair-star.

In the other case, assume that we have obtained $m$ disjoint ordered pairs
${\bf p}_{1},\ldots,{\bf p}_{m}$ in ${\cal S}_{0}$, with ${\bf
p}_{i}=(x_{i},y_{i})$. Then, by Lemmas 2.5 and 2.8 our graph $G$ is
$((\varepsilon_{0}/2)^{2},\varepsilon_{0}/2)$-pair-diverse, so for each pair
$(x_{j},y_{j})$ there are at most $|V_{1}|^{0.2}$ other pairwise disjoint
edges $x_{i}y_{i}$ such that $|\text{divb}(x_{j},y_{j})\setminus
N(x_{i})|<(\varepsilon_{0}/2)^{2}|V_{2}|$ or
$|\text{divb}(x_{j},y_{j})\setminus N(y_{i})|<(\varepsilon_{0}/2)^{2}|V_{2}|$.
Setting $\varepsilon=(\varepsilon_{0}/2)^{2}$, by Turán, there is a set
$I\subset[m]$ of size at least
$m\left(1+|V_{1}|^{0.2}\right)^{-1}\geq|V_{1}|^{0.5}$ such that
$|\text{divb}({\bf p}_{j})\setminus N(x_{i})|\geq\varepsilon|V_{2}|$ and
$|\text{divb}({\bf p}_{j})\setminus N(y_{i})|\geq\varepsilon|V_{2}|$ for all
$i\neq j$ in $I$. This represents our pair-matching. ∎

###  3.2 Degree control from pair-stars and pair-matchings

Our next aim is to show that when picking a subset $W\subset V_{2}$ uniformly
at random, there is a very good chance that _pair-stars_ and _pair-matchings_
associated to $V_{1}$ produce well distributed degree sets in $W$. The
following lemma will be useful in this context.

######  Lemma 3.2.

Let $G=(V_{1},V_{2},E)$ be a bipartite graph and suppose the subset $W\subset
V_{2}$ is selected uniformly at random. Then:

  1. (i)

if $x,y\in V_{1}$ with $|\text{\emph{div}}(x,y)|\geq\delta|V_{2}|$ then
$\mathbb{P}\left(d^{W}(x)=d^{W}(y)\right)=O_{\delta}\left(|V_{2}|^{-0.5}\right).$

  2. (ii)

if $\bm{p}_{1}=(x_{1},y_{1})\in\binom{V_{1}}{2}$ and
$\bm{p}_{2}=(x_{2},y_{2})\in\binom{V_{1}}{2}$ with
$|\text{\emph{divb}}(\bm{p}_{1})\setminus N(x_{2})|\geq\delta|V_{2}|$ and
$|\text{\emph{divb}}(\bm{p}_{1})\setminus N(y_{2})|\geq\delta|V_{2}|$ then
$\mathbb{P}\big{(}\operatorname{deg-diff}^{W}({{\bf
p}_{1}})=\operatorname{deg-diff}^{W}({{\bf
p}_{2}})\big{)}=O_{\delta}\left(|V_{2}|^{-0.5}\right).$

###### Proof.

(i) We will use a classical randomness exposure argument. Suppose we reveal
the random set $W$ on $V_{2}\setminus\text{div}(x,y)$. Then, given such a
choice, the difference $d^{W}(x)-d^{W}(y)$ becomes
$d^{U}(x)-d^{U}(y)+\text{constant}$, where $U:=W\cap\text{div}(x,y)$. Now,
$d^{U}(x)-d^{U}(y):=\sum_{v\in\text{div}(x,y)}\theta_{v}X_{v}$, where for each
$v\in\text{div}(x,y)$ we have $\theta_{v}\in\\{-1,1\\}$ and
$X_{v}\sim\text{Bern}(0.5)$. Since $|\text{div}(x,y)|\geq\delta|V_{2}|$, by
Theorem 2.9, the random variable $d^{W^{\prime}}(x)-d^{W^{\prime}}(y)$ hits
any particular value with probability $O_{\delta}\left(|V_{2}|^{-1/2}\right)$.
The conclusion follows from the law of total probability.

(ii) The argument here is similar, but a little more involved. By the choice
of the ordering we have $\mbox{divb}({\bf p}_{1})=N(x_{1})\setminus N(y_{1})$.
Note that the condition in the lemma now gives that the set
$T=\mbox{divb}({\bf p}_{1})\setminus
N(x_{2})=N(x_{1})\setminus\big{(}N(x_{2})\cup N(y_{1})\big{)}$ satisfies
$|T|\geq\delta|V_{2}|$. Letting $X$ denote the random variable
$X=\operatorname{deg-diff}^{W}({{\bf p}_{1}})-\operatorname{deg-
diff}^{W}({{\bf p}_{2}})$ we have:

$\displaystyle X=d^{W}(x_{1})-d^{W}(y_{1})-d^{W}(x_{2})+d^{W}(y_{2}).$

Now note that if we expose the random set $W\cap(V_{2}\setminus T)$ then the
random variable $X$ reduces to $d^{W\cap T}(x_{1})+d^{W\cap T}(y_{2})-C$,
where $C$ is some constant depending only on $W\cap(V_{2}\cap T)$ – crucially,
here we use that $y_{1}$ and $x_{2}$ have no neighbour in $T$. But $d^{W\cap
T}(x_{1})+d^{W\cap T}(y_{2})=\sum_{v\in T}\theta_{v}X_{v}$ where
$\theta_{v}\in\\{1,2\\}$ is a constant for each $v\in T$ and
$X_{v}\sim\text{Bern}(0.5)$ so that $\\{X_{v}\\}_{v\in T}$ are independent. By
Theorem 2.9, since $|T|\geq\delta|V_{2}|$, the random variable $d^{W\cap
T}(x_{1})+d^{W\cap T}(y_{2})$ takes any particular value with probability at
most $O_{\delta}\left(|V_{2}|^{-0.5}\right)$. The conclusion again follows
from the law of total probability. ∎

Let $G=(V_{1},V_{2},E)$ be a bipartite graph and select a vertex set $W\subset
V_{2}$. Given an $\varepsilon$-pair star ${\cal
P}=\\{x_{0},x_{1},\ldots,x_{k}\\}$ rooted at $x_{0}$ and associated to
$V_{1}$, we write:

$\displaystyle A_{\cal
P}^{W}:=\big{\\{}d^{W}(x_{i})-d^{W}(x_{0}):i\in[k]\big{\\}}\cap\big{[}-3|V_{2}|^{0.5},3|V_{2}|^{0.5}\big{]}.$

The following lemma provides a useful estimate on the size of $A_{\cal
P}^{W}$.

######  Lemma 3.3.

Given $\varepsilon>0$ there is $\delta>0$ such that the following holds. Let
$G=(V_{1},V_{2},E)$ be a bipartite graph with $|V_{1}|\geq|V_{2}|/2$ and let
${\cal P}=\\{x_{0},\ldots,x_{|V_{2}|^{0.5}}\\}$ be a $\varepsilon$-pair-star
of size ${|V_{2}|}^{0.5}$ rooted at $x_{0}$ and associated to $V_{1}$. Suppose
that a set $W\subset B$ is selected uniformly at random, then
${\mathbb{P}}\big{(}|A_{\cal P}^{W}|\geq\delta|V_{2}|^{0.5}\big{)}\geq 3/4$.

###### Proof.

To begin, pick $j\in[|V_{2}|^{0.5}]$ and set
$D_{j}:=d^{W}(x_{j})-d^{W}(x_{0})$. By Chebyshev’s inequality, we have
$\left|D_{j}-\mathbb{E}[D_{j}]\right|\leq 2{|V_{2}|}^{0.5}$ with probability
at least $15/16$. As $\left|\mathbb{E}[D_{j}]\right|\leq|V_{2}|^{1/2}/2$, it
follows by triangle inequality that
$\mathbb{P}\left(|d^{W}(x_{0})-d^{W}(x_{j})|\leq 3|V_{2}|^{0.5}\right)\geq
15/16$.

Next, call a vertex $x_{j}$ with $j\in[|V_{2}|^{0.5}]$ _bad_ if
$|d^{W}(x_{0})-d^{W}(x_{j})|\leq 3|V_{2}|^{0.5}$ and _good_ otherwise. Note
$\mathbb{P}(x_{j}\text{ is bad})\leq 1/16$ and so
$\mathbb{E}\left[\big{|}\\{j\in[|V_{1}|^{0.5}]:x_{j}\text{ is
bad}\\}\big{|}\right]\leq|V_{2}|^{0.5}/16$. If $U$ denotes the set of _good_
vertices, then it follows by Markov that
$\mathbb{P}\left(|U|\geq|V_{2}|^{0.5}/2\right)\geq 7/8$.

Now we build a graph $H$ on $\\{x_{1},\ldots,x_{|V_{2}|^{1/2}}\\}$ where we
join two vertices by an edge in $H$ if their degrees in $W$ are equal. By
Lemma 3.2 (i) there is an edge in $H$ between two vertices $x_{i}$ and $x_{j}$
with probability $O_{\varepsilon}\left(|V_{2}|^{-1/2}\right)$. Therefore
$\mathbb{E}[e(H)]=O_{\varepsilon}\left((|V_{2}|^{0.5})^{2}\cdot|V_{2}|^{-0.5}\right)$
and by Markov we easily deduce that, with probability at least $7/8$, one has
$e(H)=O_{\varepsilon}\left(|V_{2}|^{0.5}\right)$.

Combining our estimates, by applying the union bound we find that
$|U|\geq|V_{2}|^{0.5}/2$ and that $e(H[U])\leq
e(H)=O_{\varepsilon}\left(|V_{2}|^{0.5}\right)$ with probability at least
$3/4$. But then the average degree of $H$ is of order
$O_{\varepsilon}\left(1\right)$, hence by Turán $H$ contains an independent
set of size $\Omega_{\varepsilon}\left({|V_{2}|^{0.5}}\right)$. This set
though gives us precisely the vertices with pairwise distinct degrees that we
sought. ∎

Let $G=(V_{1},V_{2},E)$ be a bipartite graph, and set $W\subset V_{2}$. Given
an $\varepsilon$-pair-matching ${\cal P}=\\{{\bf p}_{1},\ldots,{\bf p}_{k}\\}$
associated to $V_{1}$, we write:

$\displaystyle A_{\cal P}^{W}:=\big{\\{}\operatorname{deg-diff}^{W}({{\bf
p}_{i}}):i\in[k]\big{\\}}\cap\big{[}-3|V_{2}|^{0.5},3|V_{2}|^{0.5}\big{]}.$

The following lemma gives the analogous estimate for $A_{\cal P}^{W}$ when
${\cal P}$ is an pair-matching, and can be proven in exactly the same way as
in Lemma 3.3, replacing Lemma 3.2 (i) in the proof with Lemma 3.2 (ii)
instead.

######  Lemma 3.4.

Given $\varepsilon>0$ there is $\delta>0$ such that the following holds. Let
$G=(V_{1},V_{2},E)$ be a bipartite graph with $|V_{1}|\geq|V_{2}|/2$ and let
${\cal P}$ be a $\varepsilon$-pair-matching in $V_{1}$ of size
$|V_{2}|^{0.5}$. Suppose that a set $W\subset B$ is selected uniformly at
random, then ${\mathbb{P}}\big{(}|A_{\cal
P}^{W}|\geq\delta|V_{2}|^{0.5}\big{)}\geq 3/4$.

###  3.3 Breaking modular obstructions

######  Lemma 3.5.

Given a natural number $d>1$ and $\varepsilon>0$ there are $L,D>0$ such that
the following holds. Suppose that $G=(V_{1},V_{2},E)$ is a bipartite graph and
that $\\{u_{1},\ldots,u_{L}\\}\subset V_{1}$ such that
$S_{i}=N_{G}(u_{i})\setminus\cup_{j<i}N_{G}(u_{j})$ satisfies $|S_{i}|\geq D$
for all $i\in[L]$. Then, if a subset $W$ is chosen uniformly at random from
$V_{2}$, with probability at least $1-\varepsilon$ for every pair $(k,m)$ with
$0\leq k\leq m$ and $2\leq m\leq d$ there is $i\in[L]$ such that
$d_{G}^{W}(u_{i})\equiv k\mod m$.

###### Proof.

Suppose that $W\subset V_{2}$ is selected as in the lemma. To begin, we fix a
pair $(k,m)$ so that $0\leq k\leq m$ and $2\leq m\leq d$. For $i\in[L]$ let
$E_{i}$ denote the event $E_{i}:=\\{d^{W}_{G}(u_{i})\not\equiv k\mod m\\}$.
Our first aim is to upper bound ${\mathbb{P}}\big{(}\cap_{i\in[L]}E_{i})$. To
do this, we can observe that:

$\displaystyle\mathbb{P}\big{(}\cap_{i=1}^{L}E_{i}\big{)}=\prod_{i=1}^{L}\mathbb{P}\left(E_{i}|\cap_{j<i}E_{j}\right).$

Now the event $\cap_{j<i}E_{i}$ is entirely determined by the choice of
$W^{\prime}=W\cap(V_{2}\setminus S_{i})$. Thus, to upper bound
$\mathbb{P}\left(E_{i}|\cap_{j<i}E_{j}\right)$, it suffices to upper bound
$\mathbb{P}\left(E_{i}|W^{\prime}=W_{0}\right)$ for each choice of $W_{0}$.
However, given such a choice of $W_{0}$, the conditional probability
$\mathbb{P}\left(E_{i}|W^{\prime}=W_{0}\right)$ becomes
$\mathbb{P}\big{(}d^{W\cap S_{i}}_{G}(u_{i})\not\equiv k_{i}\ (\text{mod
}m)\big{)}$ for some $0\leq k_{i}<m$. Besides this, from our hypothesis we
know that $W\cap S_{i}\sim\mbox{Bin}(|S_{i}|,0.5)$ and $|S_{i}|\geq D$, so by
Proposition 2.10 this gives
$\mathbb{P}\left(E_{i}|\cap_{j<i}E_{j}\right)\leq\max_{W_{0}}{\mathbb{P}}(E_{i}|W^{\prime}=W_{0})\leq
d(d+1)^{-1}$. Combining all these, we obtain:

$\displaystyle\mathbb{P}\big{(}\cap_{i=1}^{L}E_{i}\big{)}\leq\prod_{i=1}^{L}\mathbb{P}\left(E_{i}|\cap_{j<i}E_{j}\right)\leq\Big{(}1-\frac{1}{d+1}\Big{)}^{L}\leq\exp\left(-L(d+1)^{-1}\right).$

To finish the proof, let $F_{(k,m)}$ denote the event that
$\\{d_{G}^{W}(u_{i})\not\equiv k\mod m\mbox{ for all }i\in[L]\\}$. We have
shown that ${\mathbb{P}}(F_{(k,m)})\leq\exp(-L(d+1)^{-1})$. It follows that
the probability that some congruence is not obtained is
${\mathbb{P}}\big{(}\cup_{(k,m)}F_{k,m}\big{)}\leq\sum_{(k,m)}{\mathbb{P}}(F_{k,m})\leq
d^{2}\exp(-L(d+1)^{-1})\leq\varepsilon$, provided that $L$ (and $D$ from
above) are sufficiently large. ∎

###  3.4 Completing the proof of Theorem 1.2

The following lemma is the final key step in our proof.

######  Lemma 3.6.

Given $C>1$, there are constants $a_{C}>0$ and $n_{C}\in\mathbb{N}$ such that
the following holds. Every $C$-bipartite-Ramsey graph $G=(V_{1},V_{2},E)$ with
$|V_{1}|,|V_{2}|\geq n_{C}$ has:

$\big{[}a_{C}|V_{1}||V_{2}|,2a_{C}|V_{1}||V_{2}|\big{]}\subset\big{\\{}e(G[U]):U\subset
V(G)\big{\\}}.$

###### Proof.

We start by fixing parameters $1\geq C^{-1}\gg\varepsilon\gg\delta\gg
d_{0}^{-1}\gg L^{-1}\gg C_{0}^{-1}\gg c\gg n_{C}^{-1}>0$. Without loss of
generality, we may assume that $|V_{1}|\geq|V_{2}|$. We also fix an arbitrary
set $V_{2}^{\prime}\subset V_{2}$ with $|V_{2}^{\prime}|=c|V_{2}|$ and a
partition $V_{1}=U_{1}\cup U_{2}\cup U_{3}$, where $|U_{i}|\geq|V_{1}|/4$ for
$i\in[3]$.

To begin, we claim that there are ${\cal P}_{1},\ldots,{\cal P}_{K}$ with
$K:=C_{0}|V_{2}|^{0.5}$ such that each ${\cal P}_{i}$ is either an
$\varepsilon$-pair-star or a $\varepsilon$-pair-matching in
$G[U_{1},V_{2}^{\prime}]$ of size $|V_{2}^{\prime}|^{0.5}$ and so that the
${\cal P}_{i}$’s are all vertex disjoint. To see this, suppose that we have
found ${\cal P}_{1},\ldots,{\cal P}_{i}$ and now seek ${\cal P}_{i+1}$. Let
$U_{1}^{\prime}$ denote the subset of $U_{1}$ with the vertices of
$\cup_{j\leq i}{\cal P}_{j}$ removed and apply Lemma 3.1 to
$G[U_{1}^{\prime},V_{2}^{\prime}]$, noting that as
$|U_{1}^{\prime}|\geq|U_{1}|-2K|V_{2}^{\prime}|^{0.5}\geq|U_{1}|-2(C_{0}|V_{2}|^{0.5})(c|V_{1}|)^{0.5}\geq|U_{1}|/2\geq|V_{1}|/8$,
making $G[U_{1}^{\prime},V_{2}^{\prime}]$ a $2C$-Ramsey graph. By Lemma 3.1,
we can find a $\varepsilon$-star-pair or a $\varepsilon$-pair-matching ${\cal
P}_{i+1}$ of size $|U_{1}^{\prime}|^{0.5}\geq|V_{2}^{\prime}|^{0.5}$, which
gives the desired set (perhaps after removing some of its elements). Thus such
a collection ${\cal P}_{1},\ldots,{\cal P}_{K}$ exists.

Our next step is to apply Lemma 2.3 to $G[U_{2},V_{2}^{\prime}]$, which is
again $2C$-Ramsey, to find a set $S_{2}=\\{s_{1},\ldots,s_{L}\\}\subset U_{2}$
such that $|N(s_{i})\setminus(\cup_{j<i}N(s_{j}))|\geq|V_{2}|^{0.5}$ for all
$i\in[L]$. It is possible to do this since $C^{-1}\gg L^{-1}\gg n_{C}^{-1}$.

The final step of preparation is to select a set $W\subset V_{2}^{\prime}$
uniformly at random. For each $i\in[K]$ let $A_{i}:=A_{{\cal P}_{i}}^{W}$. Now
consider the following events:

  * •

Let ${\cal E}_{1}$ denote the event that, for at least $K/2$ values $i\in[K]$,
we have $|A_{i}|\geq\delta|V_{2}^{\prime}|^{1/2}$. By Lemmas 3.3 and 3.4, and
using that $\varepsilon\gg\delta$, we see that for any $A_{i}$ we have
$|A_{i}|\geq\delta|W|^{1/2}$ with probability at least $3/4$, so a simple
application of Markov gives ${\mathbb{P}}({\cal E}_{1})\geq 1/2$;

  * •

Secondly, let ${\cal E}_{2}$ denote the event that, for every $0\leq k\leq m$
and $2\leq m\leq d_{0}$, there exists $s\in S_{2}$ with $d^{W}_{G}(s)\equiv
k\mod m$. By the choice of $S_{2}$, Lemma 3.5 gives ${\mathbb{P}}({\cal
E}_{2})\geq 7/8$;

  * •

Lastly, let ${\cal E}_{3}$ denote the event that $|W|\geq|V_{2}^{\prime}|/4$.
By Chebyshev’s inequality ${\mathbb{P}}({\cal E}_{3})\geq 7/8$.

It follows from the union bound that ${\mathbb{P}}({\cal E}_{1}\cap{\cal
E}_{2}\cap{\cal E}_{3})\geq 1/2$. Fix a choice of $W\subset
V_{2}^{\prime}\subset V_{2}$ for which all three events occur. By reordering,
we get that $|A_{i}|\geq\delta|V_{2}^{\prime}|^{1/2}\geq\delta|W|^{1/2}$ for
$i\in[K/2]$.

We are now ready to complete the proof. Take $V_{1}^{\mbox{init}}$ to be the
union of the heads of ${\cal P}_{i}$, i.e. $V_{1}^{\mbox{init}}:=\cup_{i\leq
L/2}H({\cal P}_{i})$, and $e_{0}:=e(G[V_{1}^{\mbox{init}},W])$. Take $a\in
A_{i}$ and note the following:

  1. (i)

If ${\cal P}_{i}=\\{x_{0},\ldots,x_{|V_{2}^{\prime}|^{0.5}}\\}$ is a pair-star
rooted at $x_{0}$ then by definition $d^{W}(x_{j})-d^{W}(x_{0})=a$ for some
$j\in[|V_{2}^{\prime}|^{1/2}]$. Removing $x_{0}$ from $V_{1}^{\mbox{init}}$
and adding $x_{j}$ changes the number of edges in the resulting graph by
exactly $a$.

  2. (ii)

Similarly, if ${\cal P}_{i}$ is a pair-matching then there is ${\bf
p}=(x,y)\in{\cal P}_{i}$ such that $\operatorname{deg-diff}^{W}({{\bf p}})=a$.
Removing $x$ from $V_{1}^{\mbox{init}}$ and adding $y$ to it changes the
number of edges by exactly $a$.

  3. (iii)

The edits from different ${\cal P}_{i}$’s can be performed independently of
one another, resulting in the same changes to the edge size given in (i) and
(ii).

From observations (i)$-$(iii) we can immediately deduce that:

$\\{e_{0}\\}+A_{1}+A_{2}+\cdots+A_{K/2}\subset\big{\\{}e(G[U,W]):U\subset
U_{1}\big{\\}}.$

By definition of $A_{i}:=A_{{\cal P}_{i}}^{W}$, we have
$A_{i}\subset[-3|V_{2}^{\prime}|^{1/2},3|V_{2}^{\prime}|^{1/2}]\subset[-6|W|^{1/2},6|W|^{1/2}]$
and $|A_{i}|\geq\delta|W|^{1/2}$. By taking $M=6|W|^{1/2}$ and $B=1$ in Lemma
2.12, as $\delta,1\gg C_{0}^{-1},d_{0}^{-1}$, it follows that there is
$a\in{\mathbb{Z}}$ and $1\leq d\leq d_{0}$ such that (2) holds, which gives:

$\displaystyle\\{e_{0}+a+id:0\leq i\leq
3|W|\\}\subset\\{e_{0}\\}+\\{a+id:0\leq i\leq M^{2}\\}$
$\displaystyle\subset\\{e_{0}\\}+A_{1}+A_{2}+\cdots+A_{L/2}$
$\displaystyle\subset\\{e(G[U,W]):U\subset U_{1}\\}.$ (3)

Furthermore, as $d\leq d_{0}$, by the choice of $S_{2}$ there are
$s_{i_{0}},s_{i_{1}},\ldots,s_{i_{d-1}}\in S_{2}$ with $d^{W}(s_{j})\equiv
j\mod d$ for each $j\in[0,d-1]$. Combined with (3.4), setting
$e_{1}=e_{0}+a+|W|$, this gives:

$\displaystyle\big{[}e_{1},e_{1}+|W|\big{]}\subset\big{\\{}e(G[U\cup\\{s\\},W]):U\subset
U_{1},s\in S_{2}\big{\\}}.$ (4)

To finish the proof, note that $|U_{3}|\geq|V_{1}|/4\geq|V_{1}|^{1/2}$ and
$|W|\geq|V_{2}^{\prime}|/4\geq|V_{2}|^{1/2}$. As $G$ is $C$-Ramsey, we get
that $G[U_{3},W]$ is $(2C)$-Ramsey. It follows from Corollary 2.2 that at
least $2|U_{3}|/3$ vertices in $U_{3}$ have degrees between $(64C)^{-1}|W|$
and $(1-(64C)^{-1})|W|$ in $G[U_{3},W]$. In particular,
$\\{e(G[U^{\prime},W]):U^{\prime}\subset U_{3}\\}$ contains an element from
each interval $[|W|i,|W|(i+1)]$ with $i\in[0,(96C)^{-1}|U_{3}|]$. However,
$e(G[U\cup\\{s\\}\cup U^{\prime},W])=e(G[U\cup\\{s\\},W])+e(G[U^{\prime},W])$
for any $U\subset U_{1},s\in S_{2}$ and $U^{\prime}\subset U_{3}$. Therefore,
we deduce from (4) that:

$\displaystyle\big{[}e_{1}+|W|,e_{1}+|W|+(96C)^{-1}|U_{3}||W|\big{]}\subset\big{\\{}e(G[U\cup\\{s\\}\cup
U^{\prime},W]):U\subset U_{1},s\in S_{2},U^{\prime}\subset U_{3}\big{\\}}.$

We can finally claim that the lemma holds with $a_{C}:=c/4000C$. To see this,
note that:

$\displaystyle e_{1}+|W|=e_{0}+a+|W|$
$\displaystyle\leq(K/2)|V_{2}^{\prime}|^{0.5}|W|+(K/2)(6|W|)^{0.5}|W|+|W|$
$\displaystyle\leq 4K|W|^{1.5}\leq
4(C_{0}|V_{2}|)^{0.5}(c|V_{2}|)^{1.5}=4c^{1.5}(C_{0})^{0.5}|V_{2}|^{2}\leq
a_{C}|V_{1}||V_{2}|,$

where we have used that $|W|\leq c|V_{2}|$, that $c\ll C_{0}^{-1},C^{-1}$, and
that $|V_{2}|\leq|V_{1}|$.
Since $a_{C}|V_{1}||V_{2}|=(c/4000C)|V_{1}||V_{2}|\leq(200C)^{-1}|U_{3}||W|$,
it is quite easy to observe that
$[a_{C}|V_{1}||V_{2}|,2a_{C}|V_{1}||V_{2}|]\subset\\{e(G[U]):U\subset
V(G)\\}$, as required. This completes the proof. ∎

With Lemma 3.6 in hand, it is now easy to complete the proof of Theorem 1.2.

###### Proof of Theorem 1.2.

By making $\alpha$ small enough we may assume, without losing generality, that
$|V_{1}|\geq|V_{2}|$ and that $|V_{2}|$ is large enough so that our estimates
below hold. We can also assume that $C>1$ since the Ramsey condition still
holds when we increase $C$.

First note that as $G=(V_{1},V_{2},E)$ is $C$-Ramsey, there is a vertex $v\in
V_{2}$ with degree at least $(32C)^{-1}|V_{1}|$ in $V_{1}$, by Corollary 2.2.
But then the induced subgraphs of the form $G[W,\\{v\\}]$, where $W\subset
V_{1}$, give all edge sizes in $[0,(32C)^{-1}|V_{1}|]$.

On the other hand, observe that by fixing any $W_{1}\subset V_{1}$ and
$W_{2}\subset V_{2}$ with $|W_{i}|\geq|V_{i}|^{1/3}$ for $i\in\\{1,2\\}$, the
graph $H=G[W_{1},W_{2}]$ is $(3C)$-Ramsey, as $G$ is $C$-Ramsey. It follows by
applying Lemma 3.6 to $H$ that there are induced subgraphs of each size in
$[a_{3C}|W_{1}||W_{2}|,2a_{3C}|W_{1}||W_{2}|]$. It follows, taking
$M=\\{(m_{1},m_{2}):|V_{i}|^{1/3}\leq m_{i}\leq|V_{i}|\mbox{ for
}i\in\\{1,2\\}\\}$, that $G$ contains a subgraph of each size in
$\cup_{(m_{1},m_{2})\in M}[a_{3C}m_{1}m_{2},2a_{3C}m_{1}m_{2}]$. It can be
easily seen that these sets together cover the interval
$[a_{C}(|V_{1}||V_{2}|)^{1/3},2a_{C}|V_{1}||V_{2}|]$.

Finally, note that the intervals $[0,(32C)^{-1}|V_{1}|]$ and
$[a_{3C}(|V_{1}||V_{2}|)^{1/3},2a_{3C}|V_{1}||V_{2}|]$ together cover
$[0,2a_{3C}|V_{1}||V_{2}|]$, since $|V_{1}|\geq|V_{2}|$ and $|V_{2}|$ is large
enough, thus completing the proof of the theorem. ∎

##  4 Concluding remarks

In this paper we have proven a bipartite analogue of the Erdős–McKay
conjecture, showing that any $C$-bipartite-Ramsey graph $G=(V_{1},V_{2},E)$
must contain induced subgraphs of all sizes in
$[0,\Omega_{C}(|V_{1}||V_{2}|)]$. Of course the Erdős–McKay conjecture itself
remains an outstanding problem, and we hope that some of our ideas will be
useful in future approaches here.

Another interesting direction is to understand the effect of weakening the
Ramsey hypothesis in Theorem 1.2, as considered already in a number of other
settings (see e.g. [2], [19], [17]). That is, what are we able to say about
the edge sizes of induced subgraphs of a bipartite graph $G=(V_{1},V_{2},E)$,
which do not contain induced copies of $K_{t_{1},t_{2}}$ or
$\overline{K_{t_{1},t_{2}}}$, where $t_{1}$ and $t_{2}$ are now general
parameters?

Lastly, we note that Narayanan, Sahasrabudhe and Tomon in [20] showed that any
bipartite graph with $m$ edges must have induced subgraphs of
$\Omega(m/\log^{12}(m))$ different sizes. An obvious upper bound here for the
number of such sizes is $m$, though if $m$ is a perfect square $m=k^{2}$ then
the complete bipartite graphs $K_{k,k}$ allows only $m/(\log
m)^{0.086...+o(1)}$ edge sizes. The authors of [20] conjecture that when
$m=k^{2}$ the graph $K_{k,k}$ is extremal here. It would be interesting to
understand whether our approach, perhaps combined with stability arguments,
could be applied to improve the knowledge here.

## References

  * [1] N. Alon, M. Krivelevich and B. Sudakov  “Induced subgraphs of prescribed size”  In _Journal of Graph Theory_ 43.4, 2003, pp. 239–251  URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.10117
  * [2] Noga Alon and Béla Bollobás  “Graphs with a small number of distinct induced subgraphs”  In _Discrete Mathematics_ 75.1-3 Elsevier, 1989, pp. 23–30  URL: https://www.sciencedirect.com/science/article/pii/0012365X89900745
  * [3] Noga Alon and Joel H. Spencer  “The Probabilistic Method”  New York: Wiley, 2004
  * [4] Mantas Baksys and Xuanang Chen  “On number of different sized induced subgraphs of Bipartite-Ramsey graphs”  In _arXiv preprint arXiv:2109.08485_ , 2021  URL: https://arxiv.org/abs/2109.08485
  * [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  DOI: http://doi.org/10.4007/annals.2012.176.3.3
  * [6] 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  URL: https://www.sciencedirect.com/science/article/pii/S0095895606001080
  * [7] Neil Calkin, Alan Frieze and Brendan D McKay  “On subgraph sizes in random graphs”  In _Combinatorics, Probability and Computing_ 1.2 Cambridge University Press, 1992, pp. 123–134  DOI: 10.1017/S0963548300000146
  * [8] Fan Chung and Ron Graham  “Erdos on graphs: His legacy of unsolved problems”  AK Peters/CRC Press, 1998
  * [9] 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
  * [10] P. Erdős and G. Szckeres  “A Combinatorial Problem in Geometry”  In _Classic Papers in Combinatorics_ Boston, MA: Birkhäuser Boston, 1987, pp. 49–56  URL: https://doi.org/10.1007/978-0-8176-4842-8_3
  * [11] P. Erdös and A. Szemerédi  “On a Ramsey-type theorem”  In _Period Math Hung_ 2.1, 1972, pp. 295–299  URL: https://link.springer.com/article/10.1007%5C%2FBF02018669#citeas
  * [12] Paul Erdös  “Some of my favourite problems in various branches of combinatorics”  In _Le Matematiche_ 47.2, 1992, pp. 231–240
  * [13] 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
  * [14] T. Kovari, V. Sós and P. Turán  “On a problem of K. Zarankiewicz”  In _Colloquium Mathematicae_ 3.1, 1954, pp. 50–57
  * [15] Matthew Kwan and Benny Sudakov  “Proof of a conjecture on induced subgraphs of Ramsey graphs”  In _Transactions of the American Mathematical Society_ 372.8, 2019, pp. 5571–5594  DOI: https://doi.org/10.1090/tran/7729
  * [16] 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
  * [17] Eoin Long and Laurentiu Ploscaru  “Distinct degrees and homogeneous sets”  In _arXiv preprint arXiv:2204.05932_ , 2022, pp. 36  URL: https://arxiv.org/abs/2204.05932
  * [18] Bhargav Narayanan, Julian Sahasrabudhe and István Tomon  “Ramsey graphs induce subgraphs of many different sizes”  In _Combinatorica_ 39.1 Springer, 2019, pp. 215–237  DOI: https://doi.org/10.1007/s00493-017-3755-0
  * [19] 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: https://doi.org/10.1017/S0963548317000256
  * [20] Bhargav P Narayanan, Julian Sahasrabudhe and István Tomon  “The multiplication table problem for bipartite graphs”  In _Combinatorica_ 37.5 Springer, 2017, pp. 991–1010  DOI: https://doi.org/10.1007/s00493-016-3322-0
  * [21] J.. Norris  “Markov Chains”, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, 1997  DOI: 10.1017/CBO9780511810633
  * [22] Hans Jürgen Prömel and Vojtěch Rödl  “Non-Ramsey Graphs Are clogn-Universal”  In _Journal of Combinatorial Theory, Series A_ 88.2, 1999, pp. 379–384  URL: https://www.sciencedirect.com/science/article/pii/S0097316599929722
  * [23] F.. Ramsey  “On a Problem of Formal Logic”  In _Proceedings of the London Mathematical Society_ s2-30.1, 1930, pp. 264–286  URL: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-30.1.264
  * [24] S. Shelah  “Erdős and Rényi Conjecture”  In _J. Comb. Theory, Ser. A_ 82, 1998, pp. 179–185  DOI: https://doi.org/10.1006/jcta.1997.2845
  * [25] E. Szemeredi and V.. Vu  “Long arithmetic progressions in sum-sets and the number of x-sumfree sets”  In _Proceedings of the London Mathematical Society_ 90.2, 2005, pp. 273–296  DOI: https://doi.org/10.1112/S0024611504015059
  * [26] Terence Tao and Van H Vu  “Additive combinatorics”  Cambridge University Press, 2006