Grafy

Grafy.

1. K nigova lema.

Lema 1.1 (K nig).

V každom nekonečnom strome s konečným maximálnym stupňom vetvenia existuje nekonečná vetva.

Dôkaz.

Triviálne.

Veta 1.1.

Nech strom T má maximálny stupeň vetvenia k. Ak |T| > , tak existuje vetva dĺžky aspoň n+1.

Dôkaz.

Úplný k-árny strom hĺbky n má vrcholov.

2. Ramseyove císla.

Definícia.

Ramseyovým číslom pre m a n nazývame číslo R(m, n) = min.

Veta 2.1.

'2<m,nIN : R(m, n) Ł R(m, n - 1) + R(m - 1, n).

Dôkaz.

Indukciou na m+n. 2 = R(2,2) Ł R(1,2) + R(2,1) = 1 + 1. Majme teraz G o aspoň R(m - 1, n) + R(m, n - 1) vrcholoch. Nech vIG. Ak deg_G(v) ł R(m - 1, n), tak buď G[N(v)] alebo (G[N(v)])´ má m-1-kliku. Spolu s v je to m-klika. Ak deg_G(v) < R(m - 1, n), tak deg_G´(v) ł R(m, n - 1) a postupujeme vyššieuvedeným spôsobom.

Veta 2.2.

'm,nł2 : R(m, n) Ł .

Dôkaz.

1° R(m, 2) = 2 Ł= m. Rovnako R(2, n) = 2 Ł= n.

2° Podľa vety 2.1 R(m, n) Ł R(m, n - 1) + R(m - 1, n) Ł += .

Veta 2.3 (Ramsey).

'm,nł2 'rł R(m, n) 'rozklady na R₁ a R₂ buď R₁ obsahuje všetky alebo R₂ všetky .

Dôkaz.

Veta je iba preformulovaním definície Ramseyových čísel.

3. Systémy reprezentantov množín.

Definícia.

Nech S = . Vektor (a₁, .. , a_n), kde 'iI1..n : a_iIS_i nazývame systém reprezentantov množín S₁, .. , S_n, ak 'iąjI1..n : a_iąa_j.

Veta 3.1 (Hall).

Nech S = . Potom na S existuje systém reprezentantov práve vtedy, keď 'kI1..n 'i₁..i_kI1..n : ł k.

Dôkaz.

Uvažujme bipartitný graf G s partíciami A = S₁, .. , S_n) a B  . Na S existuje systém reprezentantov práve vtedy, keď na G existuje párenie pokrývajúce partíciu A. Ale podľa vety 5.2.2.3 (iná formulácia Hallovej vety) takéto párenie existuje práve vtedy, keď MA |N(M)|  |M|, čo je ekvivalentné nášmu tvrdeniu.

Definícia.

Stĺpce a riadky binárnej matice nazývame línie.

Veta 3.2 (König).

Maximálny počet nezávislých jednotiek každej binárnej matice je rovný minimálnemu počtu línií, ktoré maticu pokrývajú.

Dôkaz.

Túto vetu sme (podobne ako predchádzajúcu) dokázali v jej grafovej podobe ako vetu 5.2.2.2 teórie grafov. Skutočne každú binárnu maticu možno reprezentovať bipartitným grafom, kde partíciu A budú tvoriť riadky matice a B jej stĺpce, hrany budú medzi líniami, ktoré sa križujú v jednotke. Königova veta v tejto podobe hovorí, že mohutnosť maximálneho párenia bipartitného grafu je rovná mohutnosti jeho minimálneho vrcholového pokrytia. Párenie grafu pritom jednoznačne určuje množinu nezávislých jednotiek matice, zatiaľ čo vrcholové pokrytie množinu línií, takže tvrdenie platí.

4. Partície.

Definícia.

Čísla a₁..a_n nazývame partícia čísla aZ⁺, ak  a. Číslom p(n, k) označíme počet usporiadaných partícií čísla n o k sčítancoch. p(n) bude potom celkový počet usporiadaných partícií čísla n. Podobne číslom p´(n, k) označíme počet neusporiadaných partícií čísla n o k členoch a p´(n) bude označovať celkový počet neusporiadaných partícií čísla n.

Lema 4.1.

nZ⁺ kN : p(n, k)  .

Dôkaz.

Majme n za sebou idúcich jednotiek. Vložením k-1 núl medzi ne určím partíciu n. Medzier je n-1, takže počet možností je .

Dôsledok 4.1.

nZ⁺ : p(n)  2^n-1.

Dôkaz.

nZ⁺ : p(n)  2^n-1.

Lema 4.2.

nZ⁺ kN : p´(n, k)  .

Dôkaz.

Nech a₁..a_k je neusporiadaná partícia n. To znamená, že  n a teda  n - k, čo znamená, že a₁-1, .. , a_k-1 je neusporiadaná partícia n-k o najviac k členoch.

Dôsledok 4.2.

nZ⁺ : p´(n)  .

Dôkaz.

Vyplýva priamo z lemy 4.2.

5. Ferrersove diagramy.

Definícia.

Nech a₁..a_k je usporiadaná partícia n. Diagram nazývame Ferrersov diagram partície. Diagram je v normálnom tvare, ak sú všetky jeho riadky rôzne. Duálny diagram k Ferrersovmu diagramu vzniká zámenou jeho riadkov a stĺpcov.

Označenie.

R(m, n) je počet neusporiadaných partícií čísla m o najviac n sčítancoch. Q(m, n) je počet neusporiadaných partícií čísla m, ktorých sčítance sú menšie rovné n. Nemýliť si toto označenie s Ramseyovými číslami !

Veta 5.1.

m,n1 : R(m, n)  Q(m, n).

Dôkaz.

Dulány Ferrersov diagram každej partície z R(m, n) jednoznačne identifikuje partíciu z Q(m, n).

Veta 5.2.

1mnN : Q(n, m)  Q(n, m-1) + Q(n-m, m).

Dôkaz.

Q(n-m, m) sú partície, ktorých sčítance < m, takže pričítaním jednotky ku každému sčítancu dostávam partíciu z Q(n, m). Q(n, m-1) sú partície o menej sčítancoch.

Veta 5.3.

1mnN : R(n, m)  p´(m+n, m).

Dôkaz.

Pridaním stĺpca do Ferrersovho diagramu partície z R(m, n) sme jej jednoznačne priradili partíciu z p´(m+n, m).

Veta 5.4.

1mnN : R(n, m)  p´(n+, m), ktorých Ferrersove diagramy sú v normálnom tvare.

Dôkaz.

Nech a₁< .. < a_m je partícia n a je jej Ferrersov diagram. Potom je Ferrersov diagram v normálnom tvare, prislúchajúci partícii z p´(n+, m).

Veta 5.5.

Počet partícií na párne sčítance je rovný počtu partícií na sčítance, z ktorých každý sa vyskytuje párny počet krát.

Dôkaz.

Bijekciu tvoria duálne Ferrersove diagramy.

Veta 5.6.

Počet partícií na nepárne sčítance je rovný počtu partícií na sčítance, z ktorých každý sa vyskytuje párny počet krát a najväčší nepárny počet krát.

Dôkaz.

Detto.

6. Eulerova veta.

Definícia.

Riadky n až r_n+r_n+k Ferrersovho diagramu nazývame lichobežík, ak in..n+k : |r_i+1|  |r_i| + 1.

Poznámka.

Každý Ferrersov diagram v normálnom tvare sa skladá z pyramídy lichobežníkov.

Označenie.

Dĺžku prvého riadku Ferrersovho diagramu označíme s. Výšku spodného lichobežníka označíme r.

Veta 6.1 (Euler).

Nech xR. Potom v rade A tvaru A_n sú nenulové iba členy tvaru , kde kN.

Dôkaz.

Po roznásobení A_n dostávam rad, začínajúci (1 - x - x² + x⁵ + x⁷ - x¹² - x¹⁵ + x²²)(1 - x²³) . x^m sa v tomto rade nachádza toľko krát, koľko je párnych partícií na rôzne sčítance, -x^m toľko krát, koľko je nepárnych partícií m na rôzne sčítance. Ukážeme, že ak sa x nedá napísať v tvare , potom počet párnych partícií m na rôzne sčítance je rovnaký ako počet nepárnych partícií na rôzne sčítance. Uvažujme Ferrersov diagram nejakej párnej partície x na rôzne sčítance (takže diagram je v normálnom tvare). Môže nastať niekoľko situácií :

Diagram obsahuje viac ako jeden lichobežník a s  r. Potom transformáciou, pri ktorej odoberieme prvý riadok diagramu a pridáme ho k posledným s stĺpcom, jednoznačne určíme nepárnu partíciu x na rôzne sčítance.

Jediný lichobežník a s < r. Tá istá transformácia (ako v prípade 1.).

Viac lichobežníkov, s > r. Opačná transformácia (z každého z posledných s-1 stĺpcov odoberieme jeden prvok a vytvoríme z nich najvrchnejší riadok diagramu).

Jediný lichobežník, s > r+1. Opäť spätná transformácia (ako v prípade 3.).

Jedine v dvoch prípadoch nemožno uvedenú transformáciu použiť ani v jednom smere (nemožno vytvoriť bijekciu medzi párnymi a nepárnymi patríciami m a teda x^m bude v rade A s nenulovým koeficientom). Ale

Jediný lichobežník, s  r  r² +  a

Jediný lichobežník, s  r + 1  r(r + 1) +  , čo tvrdenie dokazuje.