Use of pigeonhole principle in ramsey-theorem about monochromatic triangles.

Question

Im trying to prove that for any number n the complete graph with $p(n)$ vertices whose edges have been colored with n colors in some way has a monochromatic triangle (a triplet of nodes that are connected with edges of the same color) regardless of the way the coloring has been made.

$$p(n) = \lfloor (e*n!) \rfloor+1$$

I have proven the statement using pigeonhole principle for $n=1,2,3$.

For $n=2$, $p(n) = 6$. We pick a node and it has $5$ outgoing edges. From pigeonhole principle at least $3$ are colored the same, say red. Now let $A,B,C$ be the receiving vertices of these edges. If there is at least one red edge in $ABC$ were done. If not were still done.

For $n=3$, $p(n) = 17$. Same logic. Pick a node, $16$ edges spawn from it. At least $6$ (notice that this is $p(2)$) have the same color and the receiving nodes of these 6 edges form a complete graph with $p(2)$ nodes. The problem is recursively transformed into something we have already solved. For the general case i try to apply the same logic: pick a node. From there $p(n)-1$ edges are left.

$\lceil (p(n)-1)/n\rceil$ of those edges are the same color, say red. If in that smaller graph a red edge exists we're done. If not, we have $n-1$ colors to paint the edges of a complete graph with $\lceil(p(n)-1)/n \rceil$ nodes. This can be done if $ \lceil(p(n)-1)/n \rceil = p(n-1)$. From here i want to transform this recursion into the formula i gave in the problem description. Any ideas?

Answer 1

You’ve shown that your argument will work provided that $p$ satisfies the inequality

$$\left\lceil\frac{p(n)-1}n\right\rceil\ge p(n-1)\tag{1}$$

for each $n$. Recall that $e=\sum_{k\ge 0}\frac1{k!}$, so that $\lfloor en!\rfloor=\sum_{k=0}^n\frac{n!}{k!}$.

Assume that

$$p(n-1)=\lfloor e(n-1)!\rfloor+1=1+\sum_{k=0}^{n-1}\frac{(n-1)!}{k!}\;;$$

then $(1)$ holds if and only if

$$\frac{p(n)-1}n>p(n-1)-1\;,$$

i.e., if and only if

$$\frac{p(n)-1}n>\sum_{k=0}^{n-1}\frac{(n-1)!}{k!}\;.$$

This is equivalent to

$$p(n)>1+\sum_{k=0}^{n-1}\frac{n!}{k!}=\sum_{k=0}^n\frac{n!}{k!}\;,$$

which is satisfied if we set

$$p(n)=1+\sum_{k=0}^n\frac{n!}{k!}=\lfloor en!\rfloor+1\;.$$

The result now follows by induction.

Added: To see that $\lfloor en!\rfloor=\sum_{k=0}^n\frac{n!}{k!}$ for $n\ge 1$, it suffices to show that $\sum_{k\ge n+1}\frac{n!}{k!}<1$. But

$$\begin{align*} \sum_{k\ge n+1}\frac{n!}{k!}&=\sum_{k\ge n+1}\frac1{\prod_{i=n+1}^ki}\\ &=\sum_{k\ge 1}\frac1{\prod_{i=1}^k(n+i)}\\ &\le\sum_{k\ge 1}\frac1{\prod_{i=1}^k(1+i)}\\ &=\sum_{k\ge 1}\frac1{(k+1)!}\\ &=\sum_{k\ge 2}\frac1{k!}\\ &=e-2\\ &<1\;. \end{align*}$$