Kneserovsky greve

En Kneser-graf är en oriktad graf som beskriver förhållandet mellan icke-korsande -elementundergrupper av en -elementuppsättning till varandra. ${\displaystyle KG_{n,k))$ $k$ $n$

Formell definition

Låt . Då definieras Kneser-grafen som ett par uppsättningar av hörn och kanter $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 \))$

Specialfall

För är en Kneser-graf en tom graf (inga kanter). $k>{\frac {n}{2}}$

För , Kneser-grafen är en matchning. Naturligtvis behandlas bara fallet $k={\frac {n}{2}}$ $n\equiv 0{\pmod {2}}$

När en Kneser-graf är en komplett graf . $k=1$

Greven är greven av Petersen . $KG_{{5,2}}$

Av huvudintresse är Kneser-grafer med parametervärden i intervallet . $k$ $[2;{\frac {n}{2)))$

Kromatiskt nummer

Kneser-grafen kan bland annat användas för att illustrera ett specialfall av det opraktiska i triviala uppskattningar av en grafs kromatiska tal i termer av klicknumret och oberoendetalet.

Allmänna triviala uppskattningar

Oberoendetalet är storleken på den mest oberoende uppsättningen av hörn i en graf . Definitionen av en färgning innebär att den definierar det maximala antalet hörn som kan färgas med samma färg. Baserat på någon modifiering av Dirichlets princip kan det kromatiska numret för en graf uppskattas som $\alpha (G)$ $G$ $\alpha (G)$ $\chi (G)\geq {\frac {|V|}{\alpha (G)))$

På samma sätt definieras klicknumret som storleken på den maximala klicken. Detta nummer utvärderar $\omega (G)$ $\chi (G)\geq \omega (G)$

Som regel är den första uppskattningen bättre än den andra - nämligen för en slumpmässig graf på hörn, sannolikheten som tenderar att förenas med ökande . Från det faktum att varje klick i grafen kan associeras med en oberoende uppsättning av grafen , kan vi dra slutsatsen att detsamma gäller för . $G$ $n$ ${\displaystyle \alpha (G)<2\log _{2}{n))$ $n$ $G$ $\not G$ $\omega (G)$

Kneser-grafen ger dock en tydlig illustration av en hel klass av grafer som misskrediterar ovanstående uppskattningar (i det allmänna fallet, inte för slumpmässiga grafer).

Klicka på nummer

Utan förlust av generalitet antar vi att den kommer in i klicken som en vertex. Sedan, från definitionen av en klick, bör ingen annan vertex innehålla i sin delmängd något element från . Vid ytterligare liknande analys ger detta uppenbarligen $\{1,\dots ,k\}$ $\{1,\dots ,k\}$ $\omega (KG_{n,k})=\vänster\lgolv {\frac {n}{k))\höger\rgolv$

Independence Number

Det är uppenbart från kombinatoriska överväganden att . För att konstruera en oberoende uppsättning av denna storlek räcker det med att fixera en vertex och räkna upp alla -elementsubset som innehåller den. Per definition kommer det inte att finnas någon kant mellan något par av sådana uppsättningar. $\alpha (KG_{n,k})\geq {\binom {n-1}{k-1))$ $k$

Erdős , Co och Rado publicerade 1961 ett bevis på ett teorem som hävdar likhet i uppskattningen ovan. Enligt matematikerna hittade de ett bevis flera decennier tidigare, men på den tiden var det inte vettigt att publicera det, eftersom ingen var intresserad av satsen. Förresten, Kneser-grafen var ännu inte känd vid den tiden, så Erdős, Co och Rado bevisade satsen i den elementära formuleringen av det maximala antalet parvis skärande -elementdelmängder av -elementmängder. $k$ $n$

Med hjälp av en trivial uppskattning kan endast , det vill säga , erhållas från det givna värdet på oberoendetalet . Denna uppskattning är nästan densamma som uppskattningen genom klicknumret. $\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$

Exakt betydelse

Teoremet formulerades 1955 av Martin Kneser och bevisades 1977 av Laszlo Lovas . $\chi (KG_{n,k})=n-2k+2$

Konstruktion av en optimal färgläggning

För alla , låt oss färglägga den -: e färgen för varje delmängd vars minsta element är numret . Låt oss färglägga varje delmängd som finns i uppsättningen . Eftersom det finns ett element i den angivna mängden, så skär två av dess -element-delmängder varandra, det vill säga det finns ingen kant mellan motsvarande hörn. Därför är den konstruerade färgningen korrekt. $j=1,2,\ldots ,n-2k+1$ $j$ $j$ $n-2k+2$ ${\displaystyle \{n-2k+2,n-2k+3,\ldots,n\))$ $2k-1$ $k$

Se även

Källor

Populärvetenskaplig fysikalisk och matematisk tidskrift "Kvant", 2011, "Knesers hypotes och den topologiska metoden i kombinatorik" (A. Raigorodsky)