encontrando certas cores

Question

Deixei $a\geq 2$ e $n\geq a.$ Deixei $K_n = (V,E)$ seja o gráfico completo em $n$vértices. Uma coloração de$E$ é uma função $f : E\to \{green, orange\}.$ Para um subconjunto de um elemento $S$ do $V$, digamos que uma coloração seja ruim para $S$ se todas as arestas com ambas as extremidades em $S$são atribuídos à mesma cor. Mostre que se$n\leq \sqrt{2}^{a-1},$ há uma coloração de $E$ isso não é pobre para ninguém $S$, encontrando primeiro o número de colorações para $E$ e um limite superior para o número de cores de $E$ que são pobres para alguns $a$subconjunto de elementos.

O número de cores para $E$ deveria estar $2^{{n\choose 2}}$. Mas este também não é um limite superior para o número de cores de$E$ que são pobres para alguns $S$? Acho que preciso encontrar um limite superior melhor e usar o fato de que${n\choose a} < \dfrac{n^a}{a!} \leq \dfrac{n^a}2.$ Se eu pudesse mostrar que o limite superior para o número de cores de $E$ que são pobres para alguns $S$ é estritamente menor que $2^{{n\choose 2}},$ então claramente deve haver alguma coloração de $E$ isso não é pobre para ninguém $S$.

Answer 1

Para um fixo $a$- conjunto de elementos $S$ que queremos ser pobres, existem $2$ maneiras de colorir as bordas com ambas as extremidades em $S$ e $2^{\binom n2 - \binom a2}$maneiras de colorir as outras bordas. Multiplique isso por$\binom na$ e nós temos $$ \binom na 2^{\binom n2 - \binom a2 + 1} $$ como um limite superior.

Se quisermos que seja menor que $2^{\binom n2}$, então nós queremos $2\binom na < 2^{\binom a2}$. Não temos que tentar muito: assumindo$a \ge 2$,

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

Então se $n \le \sqrt2^{a-1}$, então $n^a \le 2^{\binom a2}$, do qual concluímos $2 \binom na < 2^{\binom a2}$; portanto, existe uma coloração que não é pobre para nenhum$S$.