Bounding the number of edges in a graph satisfying a certain property

Question

I am going through past papers because I am revising for my Graph Theory exam this week. I encountered the following question:

The bipartite Ramsey number $R(s,t)$ is the minimum $n$ s.t. a bipartite graph $G=(X \cup Y,E)$, when edge colored with ${\color{red}{red}}$ and ${\color{blue}{blue}}$, either has

1) A set $X^\prime \subseteq X$ of size $s$, $Y^\prime \subseteq Y$ of size $s$ for which all the edges between these sets are ${\color{blue}{blue}}$

2) A set $X^\prime \subseteq X$ of size $t$, $Y^\prime \subseteq Y$ of size $t$ for which all the edges between these sets are ${\color{red}{red}}$

Show that $$R(s,t) \leq (s+t)2^{s+t}. $$

Also: for each $n \geq 2$, there is a bipartite graph of size $n$ each such that for each $|X^\prime| = |Y^\prime| = 3 \log n$, there is a ${\color{red}{red}}$ and a ${\color{blue}{blue}}$ edge between $X^\prime$ and $Y^\prime$.

I have no clue how to even start with either statement... is there any one that can provide me with a hint?

Answer 1

Let $\gamma\in(0,1)$. For a vertex $v$ of a coloured $K_{n,n}$, if $v$ has red-degree $\geq \gamma n$ we say $v$ is good for red, and similarly blue-degree $\geq (1-\gamma)n$ is good for blue. By Pigeonhole, every vertex is good for at least one colour.

Pigeonhole again, with the vertices of $X$ shows there are at least $\gamma n$ vertices that are good for red or at least $(1-\gamma)n$ vertices that are good for blue. Call these the "good" vertices and the corresponding colour "good". For each good vertex $x$, let $C(x)=\{y\in Y\mid (x,y)\text{ is of ``good'' colour}\}$. If we can find an $s$-subset (if red, else $t$-subset) $Y'\subset Y$ such that $Y'$ is a subset of at least $s$ ($t$ for blue) of the $C(x)$'s we would be done.

So it boils down to bounding another Ramsey-type result:

Given any $k\geq 2$, there exists an integer $n=n(k)$ such that any $n$ $n$-subsets of $[2n-1]=\{1,2,\dots,2n-1\}$, there are $k$ of these that share (at least) $k$ elements in common.

If you can bound $n(k)$ from above in some way, you can go back and bound $R(s,t)$ from above and choose $\gamma$ in some way to optimise the bound. Can you do this?