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

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?

• Hint: look at the other Ramsey-type results you've covered in your graph theory class, learn the key ideas, then apply them. May 21 '19 at 18:15
• Yes actually I studied the topic really well, learned about the upper and lower bounds on $R(s,t)$, how you can conclude $R(3,4) = 9$, how to derive $R(s,t)$ from $R(s,t-1)$ and $R(s-1,t)$, even multiple colors $R(c_i)$. I can imagine that you might think I haven't looked at the topic closely enough and I understand that. All I am asking for is a hint. May 21 '19 at 18:35
• I think your "also" is missing the word "coloured" before "bipartite graph", otherwise I could colour every edge red so there are no blue edges for any choice of $X',Y'$. May 21 '19 at 18:44
• The question doesn't make sense. It asks about "the minimum $n"$ such that" and then $n$ is never mentioned again.
– bof
May 22 '19 at 0:17
• Please do not delete your question after it has received an answer. This is an abuse of the MSE system. May 23 '19 at 12:46

## 1 Answer

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?