# The Induced Bipartite Ramsey Theorem:
An Exposition

William Gasarch and Gary Peng

##  1 Introduction

This paper presents a proof of the Induced Bipartite Ramsey Theorem. Although
based on the treatment in Diestel [1], our treatment differs from his in the
following ways:

  1. 1.

We provide more detail.

  2. 2.

We provide examples on small graphs.

  3. 3.

We include the Ramsey Theorem for general (i.e., not necessarily induced)
bipartite graphs for contrast.

  4. 4.

We view the Induced Bipartite Ramsey Theorem as a theorem of interest in and
of itself. (Diestel presents the Induced Bipartite Ramsey Theorem as a lemma
for the Induced Ramsey Theorem for general graphs.)

  5. 5.

We do not prove the Induced Ramsey Theorem for general graphs.

To summarize, our goal is pedagogical.

In both our treatment and Diestel’s, we only deal with the case of 2 colors.
Extending the results to $c$ colors is a straightforward but tedious exercise.

##  2 Bipartite Graphs

###  2.1 Preliminaries

######  Notation 2.1.

Let $n\in\sf N$. We denote the set $\\{1,\ldots,n\\}$ by $[n].$

######  Notation 2.2.

Let $X$ be a set and $k\in\sf N$. We denote the set of $k$-subsets of $X$ by
$\displaystyle\binom{X}{k}$.

######  Definition 2.3.

A bipartite graph is a graph $G=(V,E)$ where (1) $V$ can be partitioned into
disjoint sets $A,B$ and (2) $E\subseteq A\times B$. We can think of $A$ as
being on the left side of $G$ and $B$ as being on the right side of $G$.
Figure 2.1 shows a bipartite graph.

A123B456 Figure 2.1: A Bipartite Graph

######  Definition 2.4.

Let $G=(A,B,E)$ be a bipartite graph. We say that $G$ is complete if
$E=A\times B,$ and in this case, we denote $G$ by $K_{|A|,|B|}.$ Figure 2.2
shows $K_{3,3}$.

123456 Figure 2.2: $K_{3,3}$

######  Notation 2.5.

Let $n\in\sf N$ and $k\in\sf N$ with $k\leq n.$ We denote the bipartite graph

$G=\left([n],\binom{[n]}{k},E\right),$

where

$E=\left\\{(x,X)\in[n]\times\binom{[n]}{k}\colon x\in X\right\\},$

by $B_{n,k}.$ Figure 2.3 shows $B_{4,2}$.

12341, 21, 31, 42, 32, 43, 4 Figure 2.3: $B_{4,2}$

We now look at two different ways a graph can be a subgraph of another graph.

######  Notation 2.6.

Let $G=(V,E)$ be a graph and $H=(V^{\prime},E^{\prime})$ be a graph with
$V^{\prime}\subseteq V.$

  1. 1.

We say that $H$ is a subgraph of $G$ if $\displaystyle
E^{\prime}\subseteq\binom{V^{\prime}}{2}\cap E$.

  2. 2.

We say that $H$ is an induced subgraph of $G$ if $\displaystyle
E^{\prime}=\binom{V^{\prime}}{2}\cap E$.

Figures 2.4 and 2.6 show subgraphs that are not induced subgraphs. Figures 2.5
and 2.7 show subgraphs that are induced subgraphs.

1234 Figure 2.4: The red subgraph is not an induced subgraph. 1234 Figure 2.5:
The blue subgraph is an induced subgraph. 123456 Figure 2.6: The red subgraph
is not an induced subgraph. 123456 Figure 2.7: The blue subgraph is an induced
subgraph.

##  3 Hypergraphs

We will need the following concepts:

######  Definition 3.1.

Let $a\geq 1$. An $a$-ary hypergraph is a pair $(V,E)$ where $V$ is a set and
$E\subseteq\binom{V}{a}$. Note that a graph is a 2-ary hypergraph.

######  Definition 3.2.

Let $G=(V,E)$ be an $a$-ary hypergraph and $\text{COL}:E\rightarrow[c]$ be a
$c$-coloring of $E.$ We say that $H\subseteq V$ is a homogeneous set if COL
restricted to $\displaystyle\binom{H}{a}\cap E$ is constant.

We now state the $a$-ary Ramsey Theorem:

######  Theorem 3.3.

Let $a,c,k\in\sf N$. Then there exists $n$ such that, for all $c$-colorings of
$\binom{[n]}{a}$, there exists a homogenous set of size $k$.

######  Notation 3.4.

Let $a,c,k\in\sf N.$ We denote by $R_{a,c}(k)$ the minimum $n$ that is
guaranteed to exist by Theorem 3.3.

###  3.1 The Bipartite Ramsey Theorem

The following theorem is folklore:

######  Theorem 3.5.

For all $a,b\in\sf N$, there exists $n,k\in\sf N$ such that for all
$2$-colorings of the edges of $K_{n,k},$ there exists a monochromatic
$K_{a,b}.$ In particular, we can take $k=2b$ and $n=a2^{2b}$.

###### Proof.

Let $\text{COL}:[n]\times[k]\rightarrow[2]$ be a $2$-coloring of the edges of
$K_{n,k},$ where $n,k\in\sf N$ are constants to be determined later, and
define $\text{COL}^{\prime}:[n]\rightarrow[2^{k}]$ as

$\text{COL}^{\prime}(x)=(\text{COL}(x,1),\ldots,\text{COL}(x,k)).$

Then, since there are $n$ elements in the domain and $2^{k}$ elements in the
co-domain of $\text{COL}^{\prime}$, some color $\vec{c}=(c_{1},...,c_{k})$ is
mapped to by at least $\frac{n}{2^{k}}$ left-vertices in $K_{n,k}$. (We will
later pick $n,k$ such that $2^{k}$ divides $n$.) Thus, since
$c_{i}\in\\{\hbox{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}
RED},\hbox{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}
BLUE}\\}$, there exists
$c^{*}\in\\{\hbox{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}
RED},\hbox{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}
BLUE}\\}$ that appears at least $\frac{k}{2}$ times in $\vec{c}.$ (We will
later pick $k$ such that 2 divides $k$.) Hence, $\vec{c}$ looks something like

$\vec{c}=(\cdots c^{*}\cdots c^{*}\cdots c^{*}\cdots\cdots\cdots
c^{*}\cdots).$

Now, suppose that the $c^{*}$ occur at positions
$p_{1},\ldots,p_{\frac{k}{2}}$. Then, the $\frac{n}{2^{k}}$ left-vertices that
map to $\vec{c}$ and the right-vertices $p_{1},\ldots,p_{\frac{k}{2}}$ induce
a monochromatic complete bipartite graph.

To finish the proof, we will now pick $n,k$. We need the following:

  1. 1.

$\frac{n}{2^{k}}\geq a$ and $2^{k}|n$

  2. 2.

$\frac{k}{2}\geq b$ and $2|k$

Therefore, we can take $k=2b$ and $n=a2^{k}=a2^{2b}$. ∎

##  4 The Induced $B_{4,2}$ Ramsey Theorem

By Theorem 3.5, for all $a\in\sf N$, there exists $n,k\in\sf N$ such that for
all 2-colorings of the edges of $K_{n,k}$, there exists a monochromatic
$K_{a,a}$. Note that this is also an induced monochromatic $K_{a,a}$.

What if we wanted a monochromatic $B_{4,2}$? Since $B_{4,2}$ is a subgraph of
$K_{4,6}$, we can just force a monochromatic $K_{4,6}$ and take the
monochromatic $B_{4,2}$ inside it.

What if we wanted the monochromatic $B_{4,2}$ to be induced? (See Figure 4.1
for the difference between a monochromatic $K_{4,6}$ and a monochromatic
$B_{4,2}$). In this case, no complete bipartite graph works since $B_{4,2}$
cannot be an induced subgraph of any complete bipartite graph. So, what can we
do? As it turns out, we can use a bipartite graph that is not complete. In
fact, we will use a $B_{n,k}$.

12341, 21, 31, 42, 32, 43, 412341, 21, 31, 42, 32, 43, 4 Figure 4.1: a
monochromatic $K_{4,6}$ (left) and a monochromatic $B_{4,2}$ (right)

######  Theorem 4.1.

There exists $n,k\in\sf N$ such that for all 2-colorings of the edges of
$B_{n,k}$, there exists an induced monochromatic $B_{4,2}.$

###### Proof.

Let

$n=R_{3,2\binom{3}{2}}(9)=R_{3,6}(9).$

We will show that any 2-coloring of the edges of $\displaystyle
B_{n,3}=\left([n],\binom{[n]}{3},E\right),$ where

$E=\left\\{(x,X)\in[n]\times\binom{[n]}{3}\colon x\in X\right\\}$

has an induced monochromatic $B_{4,2}$ (i.e., $k=3$). Figure 4.2 shows
$B_{n,3}$.

1234$n-3$$n-2$$n-1$$n$$1,2,3$$1,2,4$$n-3,n-2,n$$n-2,n-1,n$$\dots$$\dots$
Figure 4.2: $B_{n,3}$

Let $\displaystyle\text{COL}:E\rightarrow[2]$ be a $2$-coloring of the edges
of $B_{n,3}$. We will define
$\displaystyle\text{COL}^{\prime}\colon\binom{[n]}{3}\rightarrow\left[2\binom{3}{2}\right]$
for $\displaystyle X=\\{z_{1}<z_{2}<z_{3}\\}\in\binom{[n]}{3}$. In particular,
since there are edges of the form $(z_{1},X)$, $(z_{2},X)$ and $(z_{3},X)$ in
$B_{n,3}$, $2$ of these edges – say $(z_{i},X)$ and $(z_{j},X)$ – have the
same color $c$ under COL. We define $\text{COL}^{\prime}(X)=(c,\\{i,j\\})$.

Now, by the definition of $n$, there is a homogeneous set $H$ (relative to
$\text{COL}^{\prime}$) of size 9 and color $(c,\\{i,j\\}).$ Without loss of
generality, we may assume that $H=\\{1,\ldots,9\\}$ and that
$c=\hbox{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}
RED}.$ We will now work out the case where $(i,j)=(1,3)$ and sketch the other
cases later.

Case 1: $(i,j)=(1,3)$

In this case, for all right-vertices $X\subseteq H$ in $B_{n,3},$ the 1st and
3rd edges coming into $X$ are  RED. However, we won’t assume anything about
the color of the 2nd edge coming into $X$. Thus, in the figures below, we
will, as the Rolling Stones would do, paint the edges whose colors we won’t
assume anything about  BLACK.

Figure 4.3 shows $B_{n,3}$ restricted to the left-vertices $1,\ldots,4.$

1234$1,2,3$$1,2,4$$1,3,4$$2,3,4$$\vdots$$\vdots$ Figure 4.3: $B_{n,3}$
restricted to the left-vertices $1,\ldots,4$

Now, consider the subgraph induced by left-vertices $2,4,6,8$ and the right-
vertices $\\{2,3,4\\}$, $\\{2,3,6\\}$, $\\{2,3,8\\}$, $\\{4,5,6\\}$,
$\\{4,5,8\\}$, $\\{6,7,8\\}$ in $B_{n,3}$. Note that this subgraph is a
monochromatic  RED $B_{4,2},$ as shown in Figure 4.4. Indeed, for any right-
vertex $\\{a<b<c\\}$ in this subgraph, the middle entry $b$ is absent from the
left-vertex set. We now see why we wanted a homogeneous set of size 9: We
wanted a set of four left-vertices such that (1) any pair of adjacent vertices
has ONE missing vertex between them (2) the top vertex has ONE missing vertex
above it and (3) the bottom vertex has ONE missing vertex below it. This ONE
will be what changes when we generalize.

2468$2,[3],4$$2,[3],6$$2,[3],8$$4,[5],6$$4,[5],8$$6,[7],8$ Figure 4.4: the
induced $B_{4,2}$ in the $(i,j)=(1,3)$ case

Case 2: $(i,j)=(1,2)$

See Figure 4.5.

Case 3: $(i,j)=(2,3)$

See Figure 4.6. ∎

2468$2,4,[5]$$2,6,[7]$$2,8,[9]$$4,6,[7]$$4,8,[9]$$6,8,[9]$ Figure 4.5: the
induced $B_{4,2}$ in the $(i,j)=(1,2)$ case
2468$[1],2,4$$[1],2,6$$[1],2,8$$[3],4,6$$[3],4,8$$[5],6,8$ Figure 4.6: the
induced $B_{4,2}$ in the $(i,j)=(2,3)$ case

##  5 The Induced $B_{n,k}$ Ramsey Theorem

We now generalize Theorem 4.1 to apply to $B_{n,k}$ for any $n,k\in\sf N$.
Most of the ideas used were already in the proof of Theorem 4.1.

######  Theorem 5.1.

Let $a,b\in\sf N$ with $b\leq a.$ Then, there exists $n,k\in\sf N$ such that
for all 2-colorings of the edges of $B_{n,k}$, there exists an induced
monochromatic $B_{a,b}.$

###### Proof.

Let $s\in\sf N$ be a constant to be determined later, and let

$n=R_{2b-1,2\binom{2b-1}{b}}(s).$

We will show that any 2-coloring of the edges of $\displaystyle
B_{n,2b-1}=\left([n],\binom{[n]}{2b-1},E\right),$ where

$E=\left\\{(x,X)\in[n]\times\binom{[n]}{2b-1}\colon x\in X\right\\}$

has an induced monochromatic $B_{a,b}$ (i.e., $k=2b-1$).

Let $\displaystyle\text{COL}:E\rightarrow[2]$ be a $2$-coloring of the edges
of $B_{n,2b-1}$. We will define
$\displaystyle\text{COL}^{\prime}\colon\binom{[n]}{2b-1}\rightarrow\left[2\binom{2b-1}{b}\right]$
for $\displaystyle X=\\{z_{1}<\cdots<z_{2b-1}\\}\in\binom{[n]}{2b-1}$. In
particular, since there are edges of the form $(z_{1},X)$, $\cdots$,
$(z_{2b-1},X)$ in $B_{n,2b-1}$, $b$ of these edges – say
$(z_{i_{1}},X),\cdots,(z_{i_{b}},X)$ – have the same color $c$. We define
$\text{COL}^{\prime}(X)=(c,\\{i_{1},\ldots,i_{b}\\})$.

Now, by the definition of $n,$ there exists a homogeneous set $H$ (relative to
$\text{COL}^{\prime}$) of size $s$ and color $(c,\\{i_{1},\ldots,i_{b}\\})$.
Without loss of generality, we may assume that $H=\\{1,\ldots,s\\}$ and that
$c=\hbox{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}
RED}$. Thus, for all right-vertices $X\subseteq H$ in $B_{n,2b-1}$, the
$i_{1}$th, $\ldots$, $i_{b}$th edges coming into $X$ are  RED.

We will now choose $s$. Recall that in the proof of Theorem 4.1, we wanted an
induced $B_{4,2}$ and chose $s=9$. We then took the 4 (4 was the first number
in $B_{4,2}$) left-vertices $2,4,6,8$ because there was ONE (ONE was one less
than 2, the second number in $B_{4,2}$) invisible vertex between any pair of
adjacent vertices, ONE invisible vertex above the top vertex, and ONE
invisible vertex below the bottom vertex. Hence, we choose $s=ab+b-1$ so that
we can take the left-vertices $b,2b,\ldots,ab$ and have $b-1$ vertices after
$ab$. We now leave the rest of the proof to the reader. ∎

##  6 The Induced Bipartite Ramsey Theorem For a Particular Graph

By Theorem 3.5, there is an Induced Ramsey Theorem for every bipartite graph
of the form $K_{a,b}$. By Theorem 5.1, there is an Induced Ramsey Theorem for
every bipartite graph of the form $B_{a,b}$. What about other bipartite
graphs? In this section, we will consider the case of a small bipartite graph,
the one in Figure 6.1. Since it is just an example, we will call it a
proposition instead of a theorem.

$1$$2$$3$$1$$2$ Figure 6.1: A Small Bipartite Graph

######  Proposition 6.1.

Let $G$ be the bipartite graph in Figure 6.1. Then, there exists $n,k\in\sf N$
such that for all 2-colorings of the edges of $B_{n,k}$, there exists an
induced monochromatic $G$.

###### Proof.

Let $n,k\in\sf N$ be such that for all 2-colorings of the edges of $B_{n,k}$,
there exists an induced monochromatic $B_{7,4}$. (Note that such $n,k$ exist
by Theorem 5.1.) Then, let $\displaystyle\text{COL}:E\rightarrow[2]$ be a
$2$-coloring of the edges of $B_{n,k}$, and label the left-vertices of the
induced monochromatic $B_{7,4}$ as
$1,2,3,1^{\prime},2^{\prime},3^{\prime},1^{\prime\prime},2^{\prime\prime}$.
Now, consider the induced subgraph of this $B_{7,4}$ that has

  1. 1.

left-vertices $1,2,3$

  2. 2.

right-vertices $\\{1,2,3,1^{\prime}\\}$ and
$\\{1,3,2^{\prime},1^{\prime\prime}\\}$

Figure 6.2 shows this induced bipartite graph. Note that it is $G$. ∎

$1$$2$$3$$1,2,3,1^{\prime}$$1,3,2^{\prime},1^{\prime\prime}$ Figure 6.2: The
Induced Bipartite Graph $G$

In this next section, we generalize Proposition 6.1 to any bipartite graph.
The key to the proof of Proposition 6.1 is that $B_{7,4}$ has an induced $G$,
where $G$ is the bipartite graph in Figure 6.1. We will now show that for any
bipartite graph $G$, there exists $a,b\in\sf N$ such that $G$ is an induced
subgraph of $B_{a,b}$. We will then prove the Induced Bipartite Ramsey
Theorem, which will follow directly from this result.

######  Lemma 6.2.

Let $G=(C,D,E)$ be a bipartite graph. Then, there exists $a,b\in\sf N$ such
that $G$ is an induced subgraph of $B_{a,b}$.

###### Proof.

Let $C=\\{1,\ldots,c\\}$ and $D=\\{1,\ldots,d\\}$. Now, consider the graph
$B_{a,b},$ where $a=2c+d$ and $b=c+1,$ and label the left-vertices as $\\\
1,\ldots,c,1^{\prime},\ldots,c^{\prime},1^{\prime\prime},\ldots,d^{\prime\prime}.$
We will now show that $G$ is an induced subgraph of $B_{a,b}$ by giving the
vertices that induce $G$:

  1. 1.

The left-vertices are $1,\ldots,c$. These will correspond to the left-vertices
in $G,$ which are also named $1,\ldots,c$.

  2. 2.

For the right-vertices, we will form a $b$-set to correspond to each right-
vertex $1\leq j\leq d$ in $G.$ We start by adding $\\{z_{1},\ldots,z_{L}\\},$
the neighbors of $j$ in $G,$ to the set. (Note that $L\leq c<c+1=b$.) Next, we
add $j^{\prime\prime}$ to the set to distinguish it from the other right-
vertices in $B_{a,b}$ that contain $\\{z_{1},\ldots,z_{L}\\}.$ Note the set
has $L+1$ elements now. To finish, we add $1^{\prime},\ldots,(b-L-1)^{\prime}$
to the set to bring the size up to $b$.

Clearly, the above vertices induce $G$. ∎

You can look at Figure 6.1 for a simple example of $G$ and Figure 6.2 for the
corresponding induced $G$. These were the graphs from Proposition 6.1, but now
you can see that they are special cases of Lemma 6.2.

We are now ready to prove the main result of this paper.

######  Theorem 6.3.

Let $G$ be a bipartite graph. There exists $n,k\in\sf N$ such that for all
2-colorings of the edges of $B_{n,k}$, there exists an induced monochromatic
$G$.

###### Proof.

By Lemma 6.2, there exists $a,b\in\sf N$ such that there exists an induced
monochromatic $G$ in $B_{a,b},$ and by Theorem 5.1, there exists $n,k\in\sf N$
such that for all 2-colorings of the edges of $B_{n,k}$, there exists an
induced monochromatic $B_{a,b}$. Now, let COL be a 2-coloring of the edges of
$B_{n,k}$. Then, there is an induced monochromatic $B_{a,b}$, and since there
is an induced $G$ in the $B_{a,b}$, there will be an induced monochromatic $G$
in $B_{n,k}$. ∎

##  7 Acknowledgements

We presented this proof in a seminar. We thank the people who listened to us
and helped us polish this presentation. They are Nik Carlson, Ainesh
Chatterjee, Andy Cui, Ilya Hajiaghayi, Cheng-Yuan Lee, Zhu Lipeng, John Purdy,
and Kelin Zhu. We also thank proofreaders Rob Brady and Soren Brown.

## References

  * [1] R. Diestel.  Graph theory.  Springer-Verlag, 2017.