Relation between Ramsey Numbers: $R(s, t) > (t-1)(s-1)$

212 Views Asked by At

I was thinking if I could prove this relation by arranging the $(s − 1)(t − 1)$ in an $(s − 1) × (t − 1)$ 2-D grid and coloring an edge by color-1 if the two endpoints of the edge are in the same row and by color-2 if the two endpoints of the edge are in the same column. I'm not sure if this method will work, but any other approach would be really helpful.

1

There are 1 best solutions below

1
On BEST ANSWER

That doesn't work, since you need to colour all the edges. Instead, try colouring edges red if they are in the same row and blue if they are not. How many points can you find such that all edges between them are red? What about blue?