Kneserovsky hrabě

Kneserův graf je neorientovaný graf, který popisuje vzájemný vztah neprotínajících se -prvkových podmnožin -prvkové množiny. ${\displaystyle KG_{n,k))$ $k$ $n$

Formální definice

Nechte _ Potom je Kneserův graf definován jako dvojice množin vrcholů a hran $R_{n}=\{1,2,\cdots ,n\}$ $KG_{n,k}=(V,E)$ $V=\{S\mid S\subset R_{n},|S|=k\}$ ${\displaystyle E=\{(A,B)\mid A\in V,B\in V,A\cap B=\varnothing \))$

Speciální případy

Pro , Kneserův graf je prázdný graf (bez hran). $k>{\frac {n}{2))$

Pro , Kneserův graf je odpovídající. Samozřejmě se bere v úvahu pouze případ $k={\frac {n}{2))$ $n\equiv 0{\pmod {2}}$

Když Kneserův graf je úplný graf . $k=1$

Hrabě je hrabě Petersen . $KG_{{5,2}}$

Hlavní zajímavostí jsou Kneserovy grafy s hodnotami parametrů v intervalu . $k$ $[2;{\frac {n}{2)))$

Chromatické číslo

Kneserův graf lze mimo jiné použít pro ilustraci speciálního případu nepraktičnosti triviálních odhadů chromatického čísla grafu z hlediska počtu kliky a čísla nezávislosti.

Obecné triviální odhady

Číslo nezávislosti je velikost nejnezávislejší sady vrcholů v grafu . Definice zbarvení znamená, že definuje maximální počet vrcholů, které lze obarvit stejnou barvou. Na základě určité modifikace Dirichletova principu lze chromatické číslo grafu odhadnout jako $\alpha (G)$ $G$ $\alpha (G)$ $\chi (G)\geq {\frac {|V|}{\alpha (G)))$

Podobně je počet kliknutí definován jako velikost maximálního kliknutí. Toto číslo se hodnotí $\omega (G)$ $\chi (G)\geq \omega (G)$

Zpravidla je první odhad lepší než druhý - totiž u náhodného grafu na vrcholech pravděpodobnost, která má tendenci k jednotě s rostoucí . Ze skutečnosti, že každá klika grafu může být spojena s nezávislou množinou grafu , můžeme usoudit, že totéž platí pro . $G$ $n$ ${\displaystyle \alpha (G)<2\log _{2}{n))$ $n$ $G$ $\not G$ $\omega (G)$

Kneserův graf však poskytuje jasnou ilustraci celé třídy grafů, které diskreditují výše uvedené odhady (v obecném případě ne pro náhodné grafy).

Klikněte na číslo

Bez ztráty obecnosti předpokládáme, že vstupuje do kliky jako vrchol. Z definice kliky by pak žádný jiný vrchol neměl obsahovat ve své podmnožině žádný prvek z . Po další podobné analýze to zjevně dává ${\displaystyle \{1,\tečky ,k\))$ ${\displaystyle \{1,\tečky ,k\))$ $\omega (KG_{n,k})=\left\lpatro {\frac {n}{k))\right\rfloor$

Číslo nezávislosti

Z kombinatorických úvah je zřejmé, že . K vytvoření nezávislé množiny této velikosti postačí opravit jeden vrchol a vyjmenovat všechny podmnožiny -prvků, které jej obsahují. Podle definice mezi žádnou dvojicí takových množin nebude žádná hrana. $\alpha (KG_{n,k})\geq {\binom {n-1}{k-1))$ $k$

Erdős , Co a Rado publikovali v roce 1961 důkaz teorému prosazujícího rovnost v odhadu výše. Podle matematiků našli důkaz o několik desítek let dříve, ale v té době nemělo smysl jej zveřejňovat, protože věta nikoho nezajímala. Mimochodem, Kneserův graf v té době ještě nebyl znám, takže Erdős, Co a Rado dokázali v elementární formulaci větu o maximálním počtu párově se protínajících -prvkových podmnožin -prvkových množin. $k$ $n$

Pomocí triviálního odhadu lze z dané hodnoty čísla nezávislosti získat pouze . Tento odhad je téměř stejný jako odhad prostřednictvím počtu kliknutí. $\chi (KG_{n,k})\geq {\frac {\binom {n}{k}}{\binom {n-1}{k-1}}}={\frac {n} {k}}$ $\chi (KG_{n,k})\geq \left\lceil {\frac {n}{k))\right\rceil$

Přesný význam

Věta, kterou formuloval v roce 1955 Martin Kneser a v roce 1977 dokázal Laszlo Lovas , říká, že $\chi (KG_{n,k})=n-2k+2$

Konstrukce optimálního zbarvení

Pro libovolné obarvíme -tou barvou každou podmnožinu, jejíž minimálním prvkem je číslo . Pojďme vybarvit každou podmnožinu obsaženou v sadě . Protože v zadané množině je prvek, pak se libovolné dvě jeho podmnožiny -prvků protínají, to znamená, že mezi odpovídajícími vrcholy není žádná hrana. Konstruované zbarvení je tedy správné. $j=1,2,\ldots ,n-2k+1$ $j$ $j$ $n-2k+2$ ${\displaystyle \{n-2k+2,n-2k+3,\ldots ,n\))$ $2k-1$ $k$

Viz také

Zdroje

Populární vědecký fyzikální a matematický časopis "Kvant", 2011, "Kneserova hypotéza a topologická metoda v kombinatorice" (A. Raigorodsky)