2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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*}$$

$\endgroup$
  • $\begingroup$ Why is the floor function of (e*n!) equal to the sum of factorial series (1/k!) until n multiplied by n!? I get it's got something to do with e being the limit of that series but what about the floor function?? $\endgroup$ – Themistoklis Haris Oct 28 '15 at 16:50
  • 1
    $\begingroup$ @Themistoklis: I added the necessary computation. $\endgroup$ – Brian M. Scott Oct 28 '15 at 18:20

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.