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?

  • 1
    $\begingroup$ Hint: look at the other Ramsey-type results you've covered in your graph theory class, learn the key ideas, then apply them. $\endgroup$ May 21 '19 at 18:15
  • $\begingroup$ 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. $\endgroup$ May 21 '19 at 18:35
  • $\begingroup$ 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'$. $\endgroup$ May 21 '19 at 18:44
  • $\begingroup$ The question doesn't make sense. It asks about "the minimum $n"$ such that" and then $n$ is never mentioned again. $\endgroup$
    – bof
    May 22 '19 at 0:17
  • 6
    $\begingroup$ Please do not delete your question after it has received an answer. This is an abuse of the MSE system. $\endgroup$
    – Xander Henderson
    May 23 '19 at 12:46

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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.