Kneserovsky greve

En Kneser-graf er en urettet graf, der beskriver forholdet mellem ikke-skærende -element- undersæt af et -elementsæt til hinanden. ${\displaystyle KG_{n,k))$ $k$ $n$

Formel definition

Lad . Så er Kneser-grafen defineret som et par sæt af hjørner og 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)\midt A\in V,B\in V,A\cap B=\varnothing \))$

Særlige tilfælde

For er en Kneser-graf en tom graf (ingen kanter). $k>{\frac {n}{2}}$

For er Kneser-grafen en matchning. Det er naturligvis kun sagen, der behandles $k={\frac {n}{2))$ $n\equiv 0{\pmod {2}}$

Når en Kneser-graf er en komplet graf . $k=1$

Greven er greve af Petersen . $KG_{{5,2}}$

Af hovedinteresse er Kneser-grafer med parameterværdier i intervallet . $k$ $[2;{\frac {n}{2)))$

Kromatisk tal

Kneser-grafen kan blandt andet bruges til at illustrere et særligt tilfælde af upraktiskheden af trivielle estimater af en grafs kromatiske tal i form af kliknummeret og uafhængighedstallet.

Generelle trivielle skøn

Uafhængighedstallet er størrelsen af det mest uafhængige sæt af hjørner i en graf . Definitionen af en farve betyder, at den definerer det maksimale antal hjørner, der kan farves med samme farve. Baseret på en modifikation af Dirichlets princip kan det kromatiske antal af en graf estimeres som $\alpha (G)$ $G$ $\alpha (G)$ $\chi (G)\geq {\frac {|V|}{\alpha (G)))$

På samme måde er kliktallet defineret som størrelsen af den maksimale klike. Dette tal evaluerer $\omega (G)$ $\chi (G)\geq \omega (G)$

Som regel er det første estimat bedre end det andet - nemlig for en tilfældig graf på hjørner, sandsynligheden, der har en tendens til at forene med stigende . Ud fra det faktum, at hver klike af grafen kan associeres med et uafhængigt sæt af grafen , kan vi konkludere, at det samme gælder for . $G$ $n$ ${\displaystyle \alpha (G)<2\log _{2}{n))$ $n$ $G$ $\ikke G$ $\omega (G)$

Kneser-grafen giver dog en klar illustration af en hel klasse af grafer, der miskrediterer ovenstående estimater (i det generelle tilfælde ikke for tilfældige grafer).

Klik nummer

Uden tab af generalitet antager vi, at den kommer ind i kliken som et toppunkt. Så, ud fra definitionen af en klike, bør intet andet toppunkt i sin delmængde indeholde noget element fra . Ved yderligere lignende analyse giver dette naturligvis $\{1,\dots ,k\}$ $\{1,\dots ,k\}$ $\omega (KG_{n,k})=\venstre\lgulv {\frac {n}{k))\højre\rgulv$

Uafhængighedsnummer

Det er indlysende ud fra kombinatoriske overvejelser, at . For at konstruere et uafhængigt sæt af denne størrelse, er det tilstrækkeligt at fiksere et toppunkt og opregne alle -element undersæt, der indeholder det. Per definition vil der ikke være nogen kant mellem et par af sådanne sæt. $\alpha (KG_{n,k})\geq {\binom {n-1}{k-1))$ $k$

Erdős , Co og Rado offentliggjorde i 1961 et bevis på en sætning, der hævder lighed i estimatet ovenfor. Ifølge matematikerne fandt de et bevis flere årtier tidligere, men på det tidspunkt gav det ikke mening at udgive det, for ingen var interesseret i sætningen. I øvrigt var Kneser-grafen endnu ikke kendt på det tidspunkt, så Erdős, Co og Rado beviste sætningen i den elementære formulering af det maksimale antal parvis skærende -elementdelmængder af -elementmængder. $k$ $n$

Ved hjælp af et trivielt skøn kan kun , det vil sige, fås ud fra den givne værdi af uafhængighedstallet . Dette estimat er næsten det samme som estimatet gennem kliknummeret. $\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$

Præcis betydning

Formuleret i 1955 af Martin Kneser og bevist i 1977 af Laszlo Lovas , siger teoremet, at $\chi (KG_{n,k})=n-2k+2$

Konstruktion af en optimal farvelægning

For en hvilken som helst , lad os farvelægge den -te farve for hver delmængde, hvis minimumselement er tallet . Lad os farvelægge hver delmængde i sættet . Da der er et element i det angivne sæt, så skærer to af dets -element-undersæt, det vil sige, at der ikke er nogen kant mellem de tilsvarende hjørner. Derfor er den konstruerede farvning 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 også

Kilder

Populærvidenskabeligt fysisk og matematisk tidsskrift "Kvant", 2011, "Knesers hypotese og den topologiske metode i kombinatorik" (A. Raigorodsky)