bestimmte Farben finden

Question

Lassen $a\geq 2$ und $n\geq a.$ Lassen $K_n = (V,E)$ sei das komplette Diagramm auf $n$Eckpunkte. Eine Färbung von$E$ ist eine Funktion $f : E\to \{green, orange\}.$ Für eine a-Element-Teilmenge $S$ von $V$Sagen wir, eine Färbung ist schlecht für $S$ wenn alle Kanten mit beiden Enden in $S$werden die gleiche Farbe zugewiesen. Zeigen Sie das, wenn$n\leq \sqrt{2}^{a-1},$ es gibt eine Färbung von $E$ das ist für niemanden schlecht $S$, indem Sie zuerst die Anzahl der Färbungen für finden $E$ und eine Obergrenze für die Anzahl der Farben von $E$ das sind arm für manche $a$-element Teilmenge.

Die Anzahl der Färbungen für $E$ sollte sein $2^{{n\choose 2}}$. Aber ist das nicht auch eine Obergrenze für die Anzahl der Färbungen von$E$ das sind arm für manche $S$? Ich denke, ich muss eine bessere Obergrenze finden und die Tatsache nutzen, dass${n\choose a} < \dfrac{n^a}{a!} \leq \dfrac{n^a}2.$ Wenn ich zeigen könnte, dass die Obergrenze für die Anzahl der Färbungen von $E$ das sind arm für manche $S$ ist streng weniger als $2^{{n\choose 2}},$ dann muss es eindeutig etwas Färbung geben $E$ das ist für niemanden schlecht $S$.

Answer 1

Für eine feste $a$-Element gesetzt $S$ dass wir arm sein wollen, gibt es $2$ Möglichkeiten, die Kanten mit beiden Enden in zu färben $S$ und $2^{\binom n2 - \binom a2}$Möglichkeiten, die anderen Kanten zu färben. Multiplizieren Sie dies mit$\binom na$ und wir bekommen $$ \binom na 2^{\binom n2 - \binom a2 + 1} $$ als Obergrenze.

Wenn wir wollen, dass dies weniger als ist $2^{\binom n2}$dann wollen wir $2\binom na < 2^{\binom a2}$. Wir müssen uns nicht anstrengen: vorausgesetzt$a \ge 2$,

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

Also wenn $n \le \sqrt2^{a-1}$, dann $n^a \le 2^{\binom a2}$, woraus wir schließen $2 \binom na < 2^{\binom a2}$;; daher existiert eine Färbung, die für keine schlecht ist$S$.