Contele Kneserovsky

Un graf Kneser este un graf nedirecționat care descrie relația dintre submulțile de elemente neintersectate ale unui set de elemente unul cu celălalt. $KG_{n,k)$ $k$ $n$

Definiție formală

Lasă . Apoi, graficul Kneser este definit ca o pereche de seturi de vârfuri și muchii $R_{n}=\{1,2,\cdots ,n\}$ $KG_{n,k}=(V,E)$ $V=\{S\mid S\subset R_{n},|S|=k\)$ $E=\{(A,B)\mid A\in V,B\in V,A\cap B=\varnothing \)$

Cazuri speciale

Pentru , un grafic Kneser este un grafic gol (fără muchii). $k>{\frac {n}{2)}$

Pentru , graficul Kneser este o potrivire. Desigur, este luat în considerare doar cazul $k={\frac {n}{2)}$ $n\equiv 0{\pmod {2}}$

Când un grafic Kneser este un grafic complet . $k=1$

Contele este contele lui Petersen . $KG_{{5,2}}$

De interes principal sunt graficele Kneser cu valori ale parametrilor în intervalul . $k$ $[2;{\frac {n}{2)})$

Număr cromatic

Graficul Kneser, printre altele, poate fi folosit pentru a ilustra un caz special de impracticabilitate a estimărilor triviale ale numărului cromatic al unui grafic în ceea ce privește numărul clicei și numărul de independență.

Estimări generale banale

Numărul de independență este dimensiunea celui mai independent set de vârfuri dintr-un grafic . Definiția unei colorări înseamnă că definește numărul maxim de vârfuri care pot fi colorate cu aceeași culoare. Pe baza unor modificări ale principiului lui Dirichlet , numărul cromatic al unui grafic poate fi estimat ca $\alpha (G)$ $G$ $\alpha (G)$ $\chi (G)\geq {\frac {|V|}{\alpha (G)))$

În mod similar, numărul clicurilor este definit ca dimensiunea clicei maxime. Acest număr evaluează $\omega (G)$ $\chi (G)\geq \omega (G)$

De regulă, prima estimare este mai bună decât a doua - și anume, pentru un grafic aleatoriu pe vârfuri, probabilitatea care tinde la unitate cu creșterea . Din faptul că fiecare clică a graficului poate fi asociată cu o mulțime independentă a graficului , putem concluziona că același lucru este valabil și pentru . $G$ $n$ $\alpha (G)<2\log _{2}{n)$ $n$ $G$ $\nu G$ $\omega (G)$

Cu toate acestea, graficul Kneser oferă o ilustrare clară a unei întregi clase de grafice care discreditează estimările de mai sus (în cazul general, nu pentru graficele aleatoare).

Faceți clic pe numărul

Fără a pierde generalitatea, presupunem că intră în clică ca un vârf. Apoi, din definiția unei clici, niciun alt vârf nu ar trebui să conțină în submulțimea lui vreun element din . După o analiză similară ulterioară, acest lucru dă evident $\{1,\dots ,k\)$ $\{1,\dots ,k\)$ $\omega (KG_{n,k})=\left\lfloor {\frac {n}{k)}\right\rfloor$

Numărul de independență

Este evident din considerente combinatorii ca . Pentru a construi o mulțime independentă de această dimensiune, este suficient să fixați un vârf și să enumerați toate subseturile de elemente care îl conțin. Prin definiție, nu va exista margine între nicio pereche de astfel de seturi. $\alpha (KG_{n,k})\geq {\binom {n-1}{k-1)}$ $k$

Erdős , Co, și Rado au publicat în 1961 o dovadă a unei teoreme care afirmă egalitatea în estimarea de mai sus. Potrivit matematicienilor, ei au găsit o dovadă cu câteva decenii mai devreme, dar la acel moment nu avea sens să o publice, pentru că nimeni nu era interesat de teoremă. Apropo, graficul Kneser nu era încă cunoscut la acel moment, așa că Erdős, Co și Rado au demonstrat teorema în formularea elementară a numărului maxim de submulțimi de elemente care se intersectează în perechi ale mulțimilor de elemente. $k$ $n$

Folosind o estimare trivială, numai , adică poate fi obținut din valoarea dată a numărului de independență . Această estimare este aproape aceeași cu estimarea prin numărul de clic. $\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$

Sensul exact

Formulată în 1955 de Martin Kneser și demonstrată în 1977 de Laszlo Lovas , teorema afirmă că $\chi (KG_{n,k})=n-2k+2$

Construirea unei colorări optime

Pentru orice , haideți să colorăm în -a culoare fiecare subset al cărui element minim este numărul . Să colorăm fiecare subset conținut în set . Deoarece există un element în mulțimea specificată, atunci oricare dintre subseturile sale de -element se intersectează, adică nu există nicio margine între vârfurile corespunzătoare. Prin urmare, colorarea construită este corectă. $j=1,2,\ldots ,n-2k+1$ $j$ $j$ $n-2k+2$ $\{n-2k+2,n-2k+3,\ldots, n\)$ $2k-1$ $k$

Vezi și

Surse

Jurnal științific popular de fizică și matematică „Kvant”, 2011, „Ipoteza lui Kneser și metoda topologică în combinatorică” (A. Raigorodsky)