TITLE: finding certain colourings
QUESTION [0 upvotes]: Let $a\geq 2$ and $n\geq a.$ Let $K_n = (V,E)$ be the complete graph on $n$ vertices. A colouring of $E$ is a function $f : E\to \{green, orange\}.$ For an a-element subset $S$ of $V$, say a colouring is poor for $S$ if all edges with both ends in $S$ are assigned the same colour. Show that if $n\leq \sqrt{2}^{a-1},$ there is a colouring of $E$ that is not poor for any $S$, by first finding the number of colourings for $E$ and an upper bound for the number of colours of $E$ that are poor for some $a$-element subset.

The number of colourings for $E$ should be $2^{{n\choose 2}}$. But isn't this also an upper bound for the number of colourings of $E$ that are poor for some $S$? I think I need to find a better upper bound and use the fact that ${n\choose a} < \dfrac{n^a}{a!} \leq \dfrac{n^a}2.$ If I could show that the upper bound for the number of colourings of $E$ that are poor for some $S$ is strictly less than $2^{{n\choose 2}},$ then clearly there must be some colouring of $E$ that isn't poor for any $S$.

REPLY [0 votes]: For a fixed $a$-element set $S$ that we want to be poor, there are $2$ ways to color the edges with both ends in $S$ and $2^{\binom n2 - \binom a2}$ ways to color the other edges. Multiply this by $\binom na$ and we get
$$
   \binom na 2^{\binom n2 - \binom a2 + 1}
$$
as an upper bound.
If we want this to be less than $2^{\binom n2}$, then we want $2\binom na < 2^{\binom a2}$. We don't have to try hard: assuming $a \ge 2$,

$2\binom na < \frac{2n^a}{a!} \le n^a$.
$2^{\binom a2} = (\sqrt2^{a-1})^a$.

So if $n \le \sqrt2^{a-1}$, then $n^a \le 2^{\binom a2}$, from which we conclude $2 \binom na < 2^{\binom a2}$; therefore a coloring exists that is not poor for any $S$.
{"set_name": "stack_exchange", "score": 0, "question_id": 3887037}