— — Počítání dvěma způsoby

Počítání dvěma způsoby

Princip sudosti

∀G = (V, E) : ∑_{v∈V} degv = 2|E|

DŮKAZ:

Dvojím způsobem spočítáme počet dvojic (v, e), kde v ∈ V, e ∈ E, v ∈ e. — jednou podle vrcholů a pak podle hran.

∑_{v∈V} degv = \underbrace{∑_{e∈E} 2}_{2|E|}

Q.E.D.

Nezávislý systém množin

Definice:

Mějme množinu X, M ⊆ P (x) nazýváme nezávislý systém množin, pokud

∀A, B ∈ M : A ≠ B ⇒ A ⊄ B

VĚTA (Spernerova):

X buď množina velikosti n. Potom maximální velikost nezávislého systému množin 𝕄 ⊆ P (x) je rovna \binom{n}{⌊\frac{n}{2}⌋} (např. v Pascalově △ je to v řádku, jehož součet je 2^{n}, největší číslo).

Příklady:

(i) n = 3:

\begin{aligned}X & = \{1, 2, 3\} \\ M_{1} & = \{\{1, 2\}, \{1, 3\}, \{2, 3\}\} \\ M_{2} & = \{\{1\}, \{2\}, \{3\}\} \end{aligned}

jsou nezávislé systémy množin velikosti

\binom{3}{1} = 3

(ii) obecné n:

M := množina ⌊n/2⌋ -prvkových podmnožin množiny X = {1, 2, …, n}. Pak M bude nezávislý systém velikosti \binom{n}{⌊n/2⌋}.

DŮKAZ:

(1) Maximální velikost ≥ \binom{n}{⌊\frac{n}{2}⌋}: z předchozího příkladu.
(2) Maximální velikost ≤ \binom{n}{⌊\frac{n}{2}⌋}:

X, M podle předpokladů.

Maximální řetězec: R = \{0, \{x_{1}\}, \{x_{1}, x_{2}\}, …, \underbrace{\{x_{1}, x_{2}, …, x_{n}\}}_{X}\} kde x_{1}, …,

x_{n} je libovolná permutace prvků X. Maximálních řetězců je n!, navíc kdykoliv si vezmeme libovolné dvě množiny z maximálního řetězce, jedna bude vždy podmnožinou druhé.

Spočítáme dvěma způsoby počet dvojic (R, M) takových, že M ∈ R. R buď maximální řetězec, M pak množina z M.

Tento počet je:

(a) ≤ (#maximálních řetězců) = n! Kdyby do jednoho R patřily dvě M, nepatřily by obě do nezávislého systému množin.

(b) = ∑_{M∈M} \underbrace{|M|!(n − |M|)!}_{# max. řetězců obsahujících M}.

Tedy:

n! ≥ ∑_{M∈M} |M|!(n − |M|)!

1 ≥ ∑_{M∈M} \frac{|M|!(n − |M|)!}{n!} = ∑_{M∈M} \frac{1}{\binom{n}{|M|}} ≥ ∑_{M∈M} \frac{1}{\binom{n}{⌊\frac{n}{2}⌋}} = |M|\frac{1}{\binom{n}{⌊\frac{n}{2}⌋}}

|M| ≤ \binom{n}{⌊\frac{n}{2}⌋}

Q.E.D.

Grafy bez K_{2,2} (C_{4})

VĚTA (o počtu hran na n vrcholech):

Nechť G = (V, E) je graf na n vrcholech neobsahující K_{2,2}. Potom

|E| ≤ \frac{n\sqrt{n} + n}{2}

DŮKAZ:

Využijeme Cauchy-Schwarzovu nerovnost:

∑_{i=1}^{n}x_{i}y_{i} ≤ \sqrt{∑_{i=1}^{n}x_{i}^{2}} · \sqrt{∑_{i=1}^{n}y_{i}^{2}}

pro libovolné x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ ℝ. Počítáme dvěma způsoby počet podgrafů (cest) u - v - u’. Tento počet je:

(a) ≤ \binom{n}{2}: pro ∀u, u′ ∈ V, u ≠ u′ existuje nejvýše jeden v ∈ V takový, že {u, v}, {u′, v} ∈ E — jinak dostaneme K_{2,2}:

*-* u X *-* u’

(b) = ∑_{v∈V} \binom{deg v}{2}: pro ∀v ∈ V máme právě \binom{deg v}{2} vidliček * - v - *.

— — Počítání dvěma způsoby

Tedy:

∑_{n∈V} \binom{degv}{2} ≤  \binom{n}{2}  ≤ \frac{1}{2}n^{2}
\frac{1}{2} ∑_{n∈V}((degv) − 1)^{2} ≤  ∑_{v∈V} \binom{degv}{2}  ≤ \frac{1}{2}n^{2}
\underbrace{∑_{v∈V}((degv) − 1) · 1}_{2|E|−n} ≤ \underbrace{\sqrt{∑_{v∈V}((degv) − 1)^{2}}}_{≤\sqrt{n^{2}}}· \underbrace{\sqrt{∑_{v∈V} 1^{2}}}_{\sqrt{n}} ≤n\sqrt{n}

|E| ≤ \frac{1}{2}(n\sqrt{n} + n)

Q.E.D.