4
$\begingroup$

Let $m,n\in \mathbb{N}$. We number the vertices of $K_{mn+1}$ $1,2,...,mn+1$ and color each of its edges either blue or red. Prove that at least one of the following must occur:

$a.$ There exist $m+1$ vertices, the edges between them are all blue. (A complete $K_{m+1}$ blue subgraph)

$b.$There exist $n+1$ vertices numbered $v_1<v_2<...<v_{n+1}$ for which $\{v_i,v_{i+1}\}$ is colored red for $i=1,...,n$

This looks like Erdos Szekeres relating to posets but I can't find the right operation. This also looks like it has something to do with Ramsey theory.

$\endgroup$
4
$\begingroup$

Let $f(k)$ be the length of the longest subsequence $a_1<a_2<\dots <a_l=k$ such that edges between consecutive vertices are red.

Clearly if $f(k)=f(l)$ then the edge between $k$ and $l$ must be blue. Suppose that $f(k)\in\{1,2,\dots n\}$ for all $k$, then by the pigeonhole principle there must be at least $m+1$ integers that share the same value of $f$. These $m+1$ integers form a blue $K_{m+1}$.

$\endgroup$
  • $\begingroup$ My edit was to change $f(n)\in ....$ to $f(k)\in ....$ and to take the "d" out of "pidgeon. ". English spelling is broken and needs repair. Very nice succinct answer. $\endgroup$ – DanielWainfleet Aug 8 '16 at 19:27

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.