Show that no matter how we colour all edges of K5,5 with red and blue you can find a copy of K2,2 which either has all edges red or all edges blue.

Question

Show that no matter how we colour all edges of $K_{5,5}$ with red and blue you can find a copy of $K_{2,2}$ which either has all edges red or all edges blue.

I have done this: $R_2(G_1,G_2)\le R_2(10,4)$($10$ and $4$ being the number of vertices of the graphs)

but it doesn't seem right as work after this step (calculating $R_2(10,4)$ is not a reasonable task to do). Any hint on this question?

Answer 1

Each of the top vertices has at least three red edges or at least three blue edges. For one of the colours, there are at least three top vertices $a,b,c$ that have at least three edges each of that colour. Remove all edges of the other colour. So $a,b,c$ are still of degree at least $3$. If $a$ and $b$ have two common neighbours, we are done. So assume otherwise, i.e., the neighbours of $a,b$ cover the bottom row completely. Then two of the at least three neighbours of $c$ are also neighbours of $a$ or two are neighbours of $b$.

Answer 2

Here's an equivalent formulation that might be more familiar:

In a $ 5 \times 5 $ square grid, each square is colored red or blue. Then, there exists 2 rows and 2 columns who's intersection yields squares of the same color.

The equivalence follows from: the color of square $(i,j)$ is the color of the edge connecting top vertex $i$ to bottom vertex $j$.

---

The standard incidence matrix proof works with this problem.

• WLOG, there is a color (say red) with $ \geq 13$ squares.
• Let $r_i$ be the number of red squares in the $i$th column.
• For each column, let's count the number of red-pairs of squares (formed by 2 rows).
• There $ { r_i \choose 2 } $ column pairs in each column.
• There are at least $ \sum { r_i \choose 2 } \geq 5 { \frac{ \sum r_i } { 5} \choose 2 } = 5 { 13/5 \choose 2 } = 10.4 $ such column pairs. Since this is an integer, there are at least 11 such column pairs.
• Since there are $ \frac{ 5 \times 4 } { 2 } = 10 $ pairs of rows, by the pigeonhole principle, there must be a pair of rows that have at least 2 column pairs.
• This gives us the 2 rows and 2 columns that are of the same color.

The good news is that this easily generalizes to finding (say) $K_{3,3}$ in a $K_{n, n }$.