Lineáris algebrai módszerek a kombinatorikában

Lineáris algebrai módszerek a kombinatorikában Nagy V. Gábor SZTE Bolyai Intézet

Eötvös Loránd Kollégium, Matematika Műhely Szeged, 2013. október 25.

ELK’13

A Gyárfás–Lehel-sejtés

1/21

Definíció. A G1 , . . . , Gk gráfok pakolhatók a H gráfba, ha ezen gráfok éldiszjunkt példányai megtalálhatók H-ban részgráfként.

ELK’13


1/21


ELK’13


1/21


ELK’13


1/21

Definíció. A G1 , . . . , Gk gráfok pakolhatók a H gráfba, ha ezen gráfok éldiszjunkt példányai megtalálhatók H-ban részgráfként. Sejtés (Gyárfás–Lehel, 1976). Legyen T1 , . . . , Tn−1 fák tetszőleges olyan rendszere, amelyben Ti -nek i éle van. Ekkor T1 , . . . , Tn−1 pakolható a Kn teljes gráfba.

ELK’13


1/21

Definíció. A G1 , . . . , Gk gráfok pakolhatók a H gráfba, ha ezen gráfok éldiszjunkt példányai megtalálhatók H-ban részgráfként. Sejtés (Gyárfás–Lehel, 1976). Legyen T1 , . . . , Tn−1 fák tetszőleges olyan rendszere, amelyben Ti -nek i éle van. Ekkor T1 , . . . , Tn−1 pakolható a Kn teljes gráfba.

Ez egy nagyon nehéz sejtés.

ELK’13

A Gyárfás–Lehel-sejtés egy speciális esete

2/21

Tétel (Gyárfás–Lehel, 1976). Ha a sejtésben szereplő fák mindegyike út vagy csillag, akkor teljesül az állítás.

ELK’13


2/21

Tétel (Gyárfás–Lehel, 1976). Ha a sejtésben szereplő fák mindegyike út vagy csillag, akkor teljesül az állítás. Bizonyítás (Zaks–Liu, 1977). Dolgozzunk a szomszédsági mátrixszal!

ELK’13


2/21


v1 v5

v2

v4

v3

v1 v2 v3 v4 v5

v1 v2 v3 v4 v5 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0

) )

ELK’13


2/21


v1 v5

v2

v4

v3

v1 v2 v3 v4 v5

v1 v2 v3 v4 v5 1 1 1 1 1 1 1 1 1 1

ELK’13


2/21


v1 v5

v2

v4

v3

v1 v2 v3 v4 v5

v1 v2 v3 v4 v5 1 1 1 1 1 1 1 1 1 1

ELK’13


2/21


v1 v1 v2 v3 v4 v5 v5

v2

v4

v3

v1 v2 v3 v4 v5

ELK’13


2/21


v1 v1 v2 v3 v4 v5 v5

v2

v4

v1 v2 v3 v4 v5

v3

Olyan út, illetve csillag „parkettákat” fogunk használni, amelyek könnyen áttekinthetők a szomszédsági mátrixban.

ELK’13

Speciális utak és csillagok

3/21

v1 v3 v2 v3 v4 v5 v6 v7 v8 v9 v10 v1 v2 v3 v4 v5 v6 v7 v8 v9

v7

v4 v6 v5 v9

v7

v4 v6 v5

v6

v4

v7

v3

v8

v2

v9

ELK’13

A bizonyítás

4/21

v2 v3 v4 v5 v6 v7 v8 v9 v10 v1 v2 v3 v4 v5 v6 v7 v8 v9

T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :

csillag csillag út út csillag út út csillag csillag

ELK’13

A bizonyítás

4/21


T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :


ELK’13

A bizonyítás

4/21


T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :


ELK’13

A bizonyítás

4/21


T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :


ELK’13

A bizonyítás

4/21


T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :


ELK’13

A bizonyítás

4/21


T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :


ELK’13

A bizonyítás

4/21


T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :


ELK’13

A bizonyítás

4/21


T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :


ELK’13

A bizonyítás

4/21


T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :


ELK’13

A bizonyítás

4/21


T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :


ELK’13

A bizonyítás

4/21


T9 : T8 : T7 : T6 : T5 : T4 : T3 : T2 : T1 :

Páratlan n esetén hasonlóan járhatunk el.


ELK’13

Halmazok uniói

5/21

Feladat. A H1 , . . . , Hn+1 halmazok az {1, . . . , n} alaphalmaz tetszőleges nemüres részhalmazai. Igazoljuk, hogy a halmazrendszerből kiválaszthatók olyan Hi1 , . . . , Hir ; Hj1 , . . . , Hjs különböző halmazok (r, s ≥ 1), melyekre Hi1 ∪ · · · ∪ Hir = Hj1 ∪ · · · ∪ Hjs .

ELK’13

Halmazok uniói

5/21

Feladat. A H1 , . . . , Hn+1 halmazok az {1, . . . , n} alaphalmaz tetszőleges nemüres részhalmazai. Igazoljuk, hogy a halmazrendszerből kiválaszthatók olyan Hi1 , . . . , Hir ; Hj1 , . . . , Hjs különböző halmazok (r, s ≥ 1), melyekre Hi1 ∪ · · · ∪ Hir = Hj1 ∪ · · · ∪ Hjs . Megoldás. Tekintsük a halmazok karakterisztikus vektorait: Hi = {2, 3, 6} ←→ vi = (0, 1, 1, 0, 0, 1) (itt n = 6)

ELK’13

Halmazok uniói

5/21

Feladat. A H1 , . . . , Hn+1 halmazok az {1, . . . , n} alaphalmaz tetszőleges nemüres részhalmazai. Igazoljuk, hogy a halmazrendszerből kiválaszthatók olyan Hi1 , . . . , Hir ; Hj1 , . . . , Hjs különböző halmazok (r, s ≥ 1), melyekre Hi1 ∪ · · · ∪ Hir = Hj1 ∪ · · · ∪ Hjs . Megoldás. Tekintsük a halmazok karakterisztikus vektorait: Hi = {2, 3, 6} ←→ vi = (0, 1, 1, 0, 0, 1) (itt n = 6) n A v1 , . . . , vn+1 vektorok lineárisan függők az R vektortérben, azaz a nullvektor nemtriviális módon kikombinálható belőlük: α1 v1 + · · · + αn+1 vn+1 = 0

ELK’13

Halmazok uniói

5/21

Feladat. A H1 , . . . , Hn+1 halmazok az {1, . . . , n} alaphalmaz tetszőleges nemüres részhalmazai. Igazoljuk, hogy a halmazrendszerből kiválaszthatók olyan Hi1 , . . . , Hir ; Hj1 , . . . , Hjs különböző halmazok (r, s ≥ 1), melyekre Hi1 ∪ · · · ∪ Hir = Hj1 ∪ · · · ∪ Hjs . Megoldás. Tekintsük a halmazok karakterisztikus vektorait: Hi = {2, 3, 6} ←→ vi = (0, 1, 1, 0, 0, 1) (itt n = 6) n A v1 , . . . , vn+1 vektorok lineárisan függők az R vektortérben, azaz a nullvektor nemtriviális módon kikombinálható belőlük: α1 v1 + · · · + αn+1 vn+1 = 0 Vigyük át a negatív együtthatójú tagokat a jobb oldalra: β1 vi1 + · · · + βr vir = γ1 vj1 + · · · + γs vjs (β∗ , γ∗ > 0)

ELK’13

Halmazok uniói

5/21

Feladat. A H1 , . . . , Hn+1 halmazok az {1, . . . , n} alaphalmaz tetszőleges nemüres részhalmazai. Igazoljuk, hogy a halmazrendszerből kiválaszthatók olyan Hi1 , . . . , Hir ; Hj1 , . . . , Hjs különböző halmazok (r, s ≥ 1), melyekre Hi1 ∪ · · · ∪ Hir = Hj1 ∪ · · · ∪ Hjs . Megoldás. Tekintsük a halmazok karakterisztikus vektorait: Hi = {2, 3, 6} ←→ vi = (0, 1, 1, 0, 0, 1) (itt n = 6) n A v1 , . . . , vn+1 vektorok lineárisan függők az R vektortérben, azaz a nullvektor nemtriviális módon kikombinálható belőlük: α1 v1 + · · · + αn+1 vn+1 = 0 Vigyük át a negatív együtthatójú tagokat a jobb oldalra: β1 vi1 + · · · + βr vir = γ1 vj1 + · · · + γs vjs (β∗ , γ∗ > 0) A bal oldalon szereplő vektor pozitív komponensei által kijelölt halmaz Hi1 ∪ · · · ∪ Hir , a jobb oldalon pedig Hj1 ∪ · · · ∪ Hjs .

ELK’13

Odd/even town

6/21

Tétel (Berlekamp, 1969) Az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesülnek a következők: • mindegyik halmaz páratlan elemszámú; • bármely két különböző halmaz metszete páros elemszámú. Ekkor m ≤ n.

ELK’13

Odd/even town

6/21

Tétel (Berlekamp, 1969) Az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesülnek a következők: • mindegyik halmaz páratlan elemszámú; • bármely két különböző halmaz metszete páros elemszámú. Ekkor m ≤ n. Megjegyzés I. Az egyelemű halmazok mutatják, hogy a felső korlát elérhető. Megjegyzés II. A páros elemszám / páros metszet probléma esetén a halmazok száma akár 2bn/2c is lehet. (Ennél több nem.) Megjegyzés III. A páros elemszám / páratlan metszet probléma esetén is n a felső korlát.

ELK’13

Odd/even town

6/21

Tétel (Berlekamp, 1969) Az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesülnek a következők: • mindegyik halmaz páratlan elemszámú; • bármely két különböző halmaz metszete páros elemszámú. Ekkor m ≤ n. Bizonyítás. A tételben szereplő H1 , . . . , Hm halmazokat ismét a karakterisztikus vektoraikkal reprezentáljuk: v1 , . . . , vm .

ELK’13

Odd/even town

6/21

Tétel (Berlekamp, 1969) Az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesülnek a következők: • mindegyik halmaz páratlan elemszámú; • bármely két különböző halmaz metszete páros elemszámú. Ekkor m ≤ n. Bizonyítás. A tételben szereplő H1 , . . . , Hm halmazokat ismét a karakterisztikus vektoraikkal reprezentáljuk: v1 , . . . , vm . A metszetek elemszámai kifejezhetők skaláris szorzatként: n X T |Hi ∩ Hj | = hvi , vj i , ahol hx, yi = xy = xk y k . k=1

ELK’13

Odd/even town

6/21

Tétel (Berlekamp, 1969) Az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesülnek a következők: • mindegyik halmaz páratlan elemszámú; • bármely két különböző halmaz metszete páros elemszámú. Ekkor m ≤ n. Bizonyítás. A tételben szereplő H1 , . . . , Hm halmazokat ismét a karakterisztikus vektoraikkal reprezentáljuk: v1 , . . . , vm . A metszetek elemszámai kifejezhetők skaláris szorzatként: n X T |Hi ∩ Hj | = hvi , vj i , ahol hx, yi = xy = xk y k . k=1

Eszerint feltételeink a következő alakban is megfogalmazhatók: hvi , vi i páratlan (minden i-re), hvi , vj i páros

(minden i 6= j-re).

ELK’13

Odd/even town

hvi , vi i páratlan (minden i-re), hvi , vj i páros

(minden i 6= j-re).

6/21

ELK’13

Odd/even town


(minden i 6= j-re).

Dolgozzunk a Z2 kételemű test felett! Ekkor hvi , vi i = 1 (minden i-re), hvi , vj i = 0 (minden i 6= j-re).

6/21

ELK’13

Odd/even town

6/21


(minden i 6= j-re).

Dolgozzunk a Z2 kételemű test felett! Ekkor hvi , vi i = 1 (minden i-re), hvi , vj i = 0 (minden i 6= j-re). A {v1 , . . . , vm } tehát egy ortonormált rendszerre emlékeztet bennünket, és a standard bizonyítással következik ezen vektorok lineáris függetlensége a Zn2 vektortérben is:

ELK’13

Odd/even town

6/21


(minden i 6= j-re).

Dolgozzunk a Z2 kételemű test felett! Ekkor hvi , vi i = 1 (minden i-re), hvi , vj i = 0 (minden i 6= j-re). A {v1 , . . . , vm } tehát egy ortonormált rendszerre emlékeztet bennünket, és a standard bizonyítással következik ezen vektorok lineáris függetlensége a Zn2 vektortérben is: α1 v1 + · · · + αm vm = 0

ELK’13

Odd/even town

6/21


(minden i 6= j-re).

Dolgozzunk a Z2 kételemű test felett! Ekkor hvi , vi i = 1 (minden i-re), hvi , vj i = 0 (minden i 6= j-re). A {v1 , . . . , vm } tehát egy ortonormált rendszerre emlékeztet bennünket, és a standard bizonyítással következik ezen vektorok lineáris függetlensége a Zn2 vektortérben is: α1 v1 + · · · + αm vm = 0 ⇓ m X αi hvi , vj i = hα1 v1 + · · · + αm vm , vj i = h0, vj i = 0 αj = i=1

teljesül minden αj együtthatóra. Tehát valóban m ≤ n.

ELK’13

Gyepesedés

7/21

Feladat. Egy négyzet alakú földterület n × n kisebb négyzetre van felosztva. Ha egy négyzetnek legalább két oldalszomszédja füves, akkor ez a terület is befüvesedik (de csak ekkor). Mutassuk meg, hogy ahhoz, hogy az egész terület befüvesedjen, kezdetben legalább n négyzetnek füvesnek kell lennie!

ELK’13

Gyepesedés

7/21


ELK’13

Gyepesedés

7/21


ELK’13

Gyepesedés

7/21


ELK’13

Gyepesedés

7/21


ELK’13

Gyepesedés

7/21


Megjegyzés. n kezdeti füves négyzettel (pl. az egyik átló mezőit választva) megoldható a füvesítés.

ELK’13

Gyepesedés a Marson

8/21

Feladat. Egy négyzet alakú földterület n × n kisebb négyzetre van felosztva. Ha egy négyzet egy olyan rácstéglalap „csúcsa”, melynek másik három csúcsa már füves, akkor ő is befüvesedik. Mutassuk meg, hogy ahhoz, hogy az egész terület befüvesedjen, kezdetben legalább 2n − 1 négyzetnek füvesnek kell lennie!

ELK’13


8/21


ELK’13


8/21


ELK’13


8/21


ELK’13


8/21


ELK’13


8/21


Megjegyzés. 2n − 1 kezdeti füves négyzettel (ld. ábra) megoldható a füvesítés.

ELK’13


9/21

Bizonyítás (Balogh–Bollobás–Morris–Riordan, 2012). Tekintsünk egy tetszőleges (2n − 1)-dimenziós valós V vektorteret, és abban egy {e, x2 , . . . , xn , y2 , . . . , yn } bázist. Az N négyzethez rendeljük hozzá a vN := xi + yj ∈ V elemet, ahol (i, j) a négyzet sor-oszlop pozíciója, és élünk az x1 = y1 = e jelöléssel.

ELK’13


9/21

Bizonyítás (Balogh–Bollobás–Morris–Riordan, 2012). Tekintsünk egy tetszőleges (2n − 1)-dimenziós valós V vektorteret, és abban egy {e, x2 , . . . , xn , y2 , . . . , yn } bázist. Az N négyzethez rendeljük hozzá a vN := xi + yj ∈ V elemet, ahol (i, j) a négyzet sor-oszlop pozíciója, és élünk az x1 = y1 = e jelöléssel. Kulcsészrevétel. A füves négyzetekhez rendelt V -beli elemek által generált U altér invariáns a gyepesedési folyamat során.

ELK’13


9/21

Bizonyítás (Balogh–Bollobás–Morris–Riordan, 2012). Tekintsünk egy tetszőleges (2n − 1)-dimenziós valós V vektorteret, és abban egy {e, x2 , . . . , xn , y2 , . . . , yn } bázist. Az N négyzethez rendeljük hozzá a vN := xi + yj ∈ V elemet, ahol (i, j) a négyzet sor-oszlop pozíciója, és élünk az x1 = y1 = e jelöléssel. Kulcsészrevétel. A füves négyzetekhez rendelt V -beli elemek által generált U altér invariáns a gyepesedési folyamat során. Oka. Csak azt kell megmutatni, hogy U nem bővülhet. Nézzünk meg egy gyepesedési lépést. Tegyük fel, hogy az ABCD téglalap A csúcsa füvesedik be (és B, C, D már füvesek).

ELK’13


9/21

Bizonyítás (Balogh–Bollobás–Morris–Riordan, 2012). Tekintsünk egy tetszőleges (2n − 1)-dimenziós valós V vektorteret, és abban egy {e, x2 , . . . , xn , y2 , . . . , yn } bázist. Az N négyzethez rendeljük hozzá a vN := xi + yj ∈ V elemet, ahol (i, j) a négyzet sor-oszlop pozíciója, és élünk az x1 = y1 = e jelöléssel. Kulcsészrevétel. A füves négyzetekhez rendelt V -beli elemek által generált U altér invariáns a gyepesedési folyamat során. Oka. Csak azt kell megmutatni, hogy U nem bővülhet. Nézzünk meg egy gyepesedési lépést. Tegyük fel, hogy az ABCD téglalap A csúcsa füvesedik be (és B, C, D már füvesek). Mivel vA = vB + vD − vC , ezért az új altér generátorelemei közé olyan elemet választunk be, amely előáll U -ban lévő elemek lineáris kombinációjaként. Tehát az altér valóban nem bővül.

ELK’13


9/21

Tekintsünk egy tetszőleges (2n − 1)-dimenziós valós V vektorteret, és abban egy {e, x2 , . . . , xn , y2 , . . . , yn } bázist. Az N négyzethez rendeljük hozzá a vN := xi + yj ∈ V elemet, ahol (i, j) a négyzet sor-oszlop pozíciója, és élünk az x1 = y1 = e jelöléssel. Kulcsészrevétel. A füves négyzetekhez rendelt V -beli elemek által generált U altér invariáns a gyepesedési folyamat során. Oka. Csak azt kell megmutatni, hogy U nem bővülhet. Nézzünk meg egy gyepesedési lépést. Tegyük fel, hogy az ABCD téglalap A csúcsa füvesedik be (és B, C, D már füvesek). Mivel vA = vB + vD − vC , ezért az új altér generátorelemei közé olyan elemet választunk be, amely előáll U -ban lévő elemek lineáris kombinációjaként. Tehát az altér valóban nem bővül. QED. 2n − 1-nél kevesebb füves négyzet V -nél szűkebb U -t generál, tehát nem érhető a cél, ui. ahhoz U = V tartozik. (Miért?)

ELK’13

Gráfok felbontása

10/21

Definíció. A H gráf felbontható a G1 , . . . , Gk gráfokra, ha H élhalmaza előáll a Gi gráfok élhalmazainak diszjunkt uniójaként.

Megjegyzés. A gráffelbontás tulajdonképpen egy minden élt felhasználó pakolás.

ELK’13

Gráfok felbontása

10/21

Definíció. A H gráf felbontható a G1 , . . . , Gk gráfokra, ha H élhalmaza előáll a Gi gráfok élhalmazainak diszjunkt uniójaként.

Megjegyzés. A gráffelbontás tulajdonképpen egy minden élt felhasználó pakolás. Probléma. Szeretnénk a teljes gráfot minél kevesebb teljes páros gráfra felbontani.

ELK’13

Teljes gráfok felbontása teljes páros gráfokra

11/21

Tétel (Graham–Pollak, 1971). Az n pontú teljes gráf nem bontható fel (n − 1)-nél kevesebb teljes páros gráfra.

Megjegyzés. Kn mindig felbontható n − 1 csillagra.

ELK’13


12/21

Tétel (Graham–Pollak, 1971). Az n pontú teljes gráf nem bontható fel (n − 1)-nél kevesebb teljes páros gráfra. Bizonyítás. Tegyük fel, hogy felbontottuk Kn -et a G1 , . . . , Gm teljes páros gráfokra. Ismét dolgozzunk szomszédsági mátrixokkal: Kn ←→ A Gi ←→ Bi . A felbontás a mátrixok nyelvén azt jelenti, hogy A = B1 + · · · + Bm .

ELK’13


12/21

Tétel (Graham–Pollak, 1971). Az n pontú teljes gráf nem bontható fel (n − 1)-nél kevesebb teljes páros gráfra. Bizonyítás. Tegyük fel, hogy felbontottuk Kn -et a G1 , . . . , Gm teljes páros gráfokra. Ismét dolgozzunk szomszédsági mátrixokkal: Kn ←→ A Gi ←→ Bi . A felbontás a mátrixok nyelvén azt jelenti, hogy A = B1 + · · · + Bm .

0 1 1 1

1 0 1 1

1 1 0 1

0 0 1 1 = 0 0 1 1 1 0 1 1

1 1 0 0

0 1 1 1 + 1 0 0 0 0 0 0 0

0 0 0 0

0 0 0 0 + 0 0 0 0 0 0 0 0

0 0 0 1

0 0 1 0

) )) )) )) )

ELK’13


12/21

Tétel (Graham–Pollak, 1971). Az n pontú teljes gráf nem bontható fel (n − 1)-nél kevesebb teljes páros gráfra. Bizonyítás. Tegyük fel, hogy felbontottuk Kn -et a G1 , . . . , Gm teljes páros gráfokra. Ismét dolgozzunk szomszédsági mátrixokkal: Kn ←→ A Gi ←→ Bi . A felbontás a mátrixok nyelvén azt jelenti, hogy A = B1 + · · · + Bm . A = J − I, ahol J az n×n-es csupa-1 mátrix, I az egységmátrix. Nem nehéz látni, hogy a Bi mátrixok pedig előállnak Ci + CiT alakban, ahol mindegyik Ci mátrix a nullmátrixból kapható egy almátrixának összes elemét 1-esre változtatva.

ELK’13


12/21

Tétel (Graham–Pollak, 1971). Az n pontú teljes gráf nem bontható fel (n − 1)-nél kevesebb teljes páros gráfra. Bizonyítás. Tegyük fel, hogy felbontottuk Kn -et a G1 , . . . , Gm teljes páros gráfokra. Ismét dolgozzunk szomszédsági mátrixokkal: Kn ←→ A Gi ←→ Bi . A felbontás a mátrixok nyelvén azt jelenti, hogy A = B1 + · · · + Bm . A = J − I, ahol J az n×n-es csupa-1 mátrix, I az egységmátrix. Nem nehéz látni, hogy a Bi mátrixok pedig előállnak Ci + CiT alakban, ahol mindegyik Ci mátrix a nullmátrixból kapható egy almátrixának összes elemét 1-esre változtatva. Kaptuk, hogy T J − I = (C1 + C1T ) + · · · + (Cm + Cm ) = S + ST , ahol

S := C1 + · · · + Cm .

ELK’13

(1) (2)


J − I = S + ST S = C1 + · · · + Cm ,

ahol rk(Ci ) = 1.

13/21

ELK’13

(1) (2)


13/21

J − I = S + ST S = C1 + · · · + Cm ,

ahol rk(Ci ) = 1.

Ebből (2) alapján rk(S) = rk(C1 + · · · + Cm ) ≤ rk(C1 ) + · · · + rk(Cm ) = m. Megmutatjuk, hogy (1)-ből pedig rk(S) ≥ n − 1 következik, ami a bizonyítandót adja.

ELK’13

(1) (2)


13/21

J − I = S + ST S = C1 + · · · + Cm ,

ahol rk(Ci ) = 1.

Ebből (2) alapján rk(S) = rk(C1 + · · · + Cm ) ≤ rk(C1 ) + · · · + rk(Cm ) = m. Megmutatjuk, hogy (1)-ből pedig rk(S) ≥ n − 1 következik, ami a bizonyítandót adja. Indirekt tfh. rk(S) ≤ n − 2. Ekkor az Sx = 0 Jx = 0 egyenletrendszernek létezik egy nemtriviális x = (x1 , . . . , xn )T megoldása.

ELK’13

(1) (2)


13/21

J − I = S + ST S = C1 + · · · + Cm ,

ahol rk(Ci ) = 1.

Ebből (2) alapján rk(S) = rk(C1 + · · · + Cm ) ≤ rk(C1 ) + · · · + rk(Cm ) = m. Megmutatjuk, hogy (1)-ből pedig rk(S) ≥ n − 1 következik, ami a bizonyítandót adja. Indirekt tfh. rk(S) ≤ n − 2. Ekkor az Sx = 0 Jx = 0 egyenletrendszernek létezik egy nemtriviális x = (x1 , . . . , xn )T megoldása. Erre az x-re (1) szerint fennáll, hogy −x = Jx − Ix = Sx + S T x = S T x ⇒ ||x||2 = xT x = −xT S T x = −(Sx)T x = −0T x = 0, ami ellentmondás (hiszen x nemtriviális).

ELK’13

Még egy gráffelbontási/pakolási példa

Tétel. K10 nem bontható fel három Petersen-gráfra.

14/21

ELK’13


14/21

Tétel. K10 nem bontható fel három Petersen-gráfra. Bizonyítás. Indirekt tfh. létezik ilyen felbontás, és legyenek a bepakolt Petersen-gráfok szomszédsági mátrixai A, B és C, azaz J − I = A + B + C.

ELK’13


14/21

Tétel. K10 nem bontható fel három Petersen-gráfra. Bizonyítás. Indirekt tfh. létezik ilyen felbontás, és legyenek a bepakolt Petersen-gráfok szomszédsági mátrixai A, B és C, azaz J − I = A + B + C. A Petersen-gráf szomszédsági mátrixának sajátértékei (akárhogy is pakoljuk be): 3, 1, 1, 1, 1, 1, −2, −2, −2, −2.

ELK’13


14/21

Tétel. K10 nem bontható fel három Petersen-gráfra. Bizonyítás. Indirekt tfh. létezik ilyen felbontás, és legyenek a bepakolt Petersen-gráfok szomszédsági mátrixai A, B és C, azaz J − I = A + B + C. A Petersen-gráf szomszédsági mátrixának sajátértékei (akárhogy is pakoljuk be): 3, 1, 1, 1, 1, 1, −2, −2, −2, −2. Spektráltétel. Bármely Rn×n -beli szimmetrikus M mátrixhoz létezik olyan Q ortogonális mátrix, amelyre Q−1 M Q diagonális. Tehát M sajátértékei valósak, és létezik olyan ortonormált bázis Rn -ben, amelynek bázisvektorai sajátvektorai M -nek. Továbbá M sajátalterei merőlegesek egymásra, és dimenziójuk a hozzájuk tartozó sajátérték multiplicitásával egyezik meg. Megjegyzés. A Petersen-gráf 3-regularitása miatt a λ = 3 sajátértékhez tartozó sajátaltér mindig [(1, . . . , 1)].

ELK’13


15/21

• J −I =A+B+C • A, B, C sajátértékei: 3, 1, 1, 1, 1, 1, −2, −2, −2, −2 • mindhárom mátrixnak sajátaltere az U := [(1, . . . , 1)] altér.

ELK’13


15/21

• J −I =A+B+C • A, B, C sajátértékei: 3, 1, 1, 1, 1, 1, −2, −2, −2, −2 • mindhárom mátrixnak sajátaltere az U := [(1, . . . , 1)] altér. Tekintsük az A, B mátrixok λ = 1 sajátértékhez tartozó sajátaltereit, VA -t és VB -t. Ez két 5-dimenziós altér az U ⊥ 9-dimenziós altérben (VA , VB ⊥ U ), tehát metszetük nemtriviális.

ELK’13


15/21

• J −I =A+B+C • A, B, C sajátértékei: 3, 1, 1, 1, 1, 1, −2, −2, −2, −2 • mindhárom mátrixnak sajátaltere az U := [(1, . . . , 1)] altér. Tekintsük az A, B mátrixok λ = 1 sajátértékhez tartozó sajátaltereit, VA -t és VB -t. Ez két 5-dimenziós altér az U ⊥ 9-dimenziós altérben (VA , VB ⊥ U ), tehát metszetük nemtriviális. Válasszunk egy v nem-nullvektort a metszetből, azaz olyan vektort, melyre Av = Bv = v. (v-re oszlopvektorként tekintünk.) Mivel v merőleges (1, . . . , 1)-re, ezért Jv = 0 is teljesül.

ELK’13


15/21

• J −I =A+B+C • A, B, C sajátértékei: 3, 1, 1, 1, 1, 1, −2, −2, −2, −2 • mindhárom mátrixnak sajátaltere az U := [(1, . . . , 1)] altér. Tekintsük az A, B mátrixok λ = 1 sajátértékhez tartozó sajátaltereit, VA -t és VB -t. Ez két 5-dimenziós altér az U ⊥ 9-dimenziós altérben (VA , VB ⊥ U ), tehát metszetük nemtriviális. Válasszunk egy v nem-nullvektort a metszetből, azaz olyan vektort, melyre Av = Bv = v. (v-re oszlopvektorként tekintünk.) Mivel v merőleges (1, . . . , 1)-re, ezért Jv = 0 is teljesül. Ezekből Cv = (J − I − A − B)v = 0 − v − v − v = −3v következik, ami ellentmondás, mert C-nek nem sajátértéke a −3.

ELK’13

A Petersen-gráf sajátértékei

16/21

A Petersen-gráf sajátértékei: 3, 1, 1, 1, 1, 1, −2, −2, −2, −2. 1. A Petersen-gráf 3-reguláris =⇒ a 3 sajátérték (az 1 s.v.).

ELK’13


16/21

A Petersen-gráf sajátértékei: 3, 1, 1, 1, 1, 1, −2, −2, −2, −2. 1. A Petersen-gráf 3-reguláris =⇒ a 3 sajátérték (az 1 s.v.). 2. A Petersen-gráf összefüggő =⇒ a 3 egyszeres sajátérték.

ELK’13


16/21

A Petersen-gráf sajátértékei: 3, 1, 1, 1, 1, 1, −2, −2, −2, −2. 1. A Petersen-gráf 3-reguláris =⇒ a 3 sajátérték (az 1 s.v.). 2. A Petersen-gráf összefüggő =⇒ a 3 egyszeres sajátérték. 3. Egy λ 6= 3 sajátértékhez tartozó v sajátvektor merőleges 1-re.

ELK’13


16/21

A Petersen-gráf sajátértékei: 3, 1, 1, 1, 1, 1, −2, −2, −2, −2. 1. A Petersen-gráf 3-reguláris =⇒ a 3 sajátérték (az 1 s.v.). 2. A Petersen-gráf összefüggő =⇒ a 3 egyszeres sajátérték. 3. Egy λ 6= 3 sajátértékhez tartozó v sajátvektor merőleges 1-re. 4. A Petersen-gráfban bármely két összekötött pontnak nincs közös szomszédja, és bármely két nem összekötött pontnak pontosan egy közös szomszédja van, emiatt A2 + A − 2I = J.

ELK’13


16/21

A Petersen-gráf sajátértékei: 3, 1, 1, 1, 1, 1, −2, −2, −2, −2. 1. A Petersen-gráf 3-reguláris =⇒ a 3 sajátérték (az 1 s.v.). 2. A Petersen-gráf összefüggő =⇒ a 3 egyszeres sajátérték. 3. Egy λ 6= 3 sajátértékhez tartozó v sajátvektor merőleges 1-re. 4. A Petersen-gráfban bármely két összekötött pontnak nincs közös szomszédja, és bármely két nem összekötött pontnak pontosan egy közös szomszédja van, emiatt A2 + A − 2I = J. 5. Egy λ 6= 3 sajátértékhez tartozó v sajátvektorra (λ2 + λ − 2)v = (A2 + A − 2I)v = Jv = 0. Tehát minden 3-tól különböző sajátérték gyöke az x2 + x − 2 polinomnak, azaz −2 vagy 1.

ELK’13


16/21

A Petersen-gráf sajátértékei: 3, 1, 1, 1, 1, 1, −2, −2, −2, −2. 1. A Petersen-gráf 3-reguláris =⇒ a 3 sajátérték (az 1 s.v.). 2. A Petersen-gráf összefüggő =⇒ a 3 egyszeres sajátérték. 3. Egy λ 6= 3 sajátértékhez tartozó v sajátvektor merőleges 1-re. 4. A Petersen-gráfban bármely két összekötött pontnak nincs közös szomszédja, és bármely két nem összekötött pontnak pontosan egy közös szomszédja van, emiatt A2 + A − 2I = J. 5. Egy λ 6= 3 sajátértékhez tartozó v sajátvektorra (λ2 + λ − 2)v = (A2 + A − 2I)v = Jv = 0. Tehát minden 3-tól különböző sajátérték gyöke az x2 + x − 2 polinomnak, azaz −2 vagy 1. 6. A sajátértékek összege a mátrix nyoma, vagyis esetünkben 0. Ebből kitalálhatók a multiplicitások.

ELK’13

Gráfok sajátértékeinek további alkalmazásai I.

17/21

Barátság-tétel (Erdős–Rényi–T. Sós, 1966). Ha egy G egyszerű gráfban bármely két pontnak pontosan egy közös szomszédja van, akkor van olyan csúcs, mely az összes többi csúccsal össze van kötve. Sőt, G csak egy szélmalom-gráf lehet.

ELK’13

Gráfok sajátértékeinek további alkalmazásai II.

18/21

Észrevétel. Ha egy d-reguláris gráfban nincs 5-nél rövidebb kör, akkor a gráfnak legalább 1 + d + d(d − 1) = d2 + 1 csúcsa van.

ELK’13


18/21

Észrevétel. Ha egy d-reguláris gráfban nincs 5-nél rövidebb kör, akkor a gráfnak legalább 1 + d + d(d − 1) = d2 + 1 csúcsa van. Hoffman–Singleton-tétel (1960). „Beauty is rare.” Ha egy d-reguláris gráfban nincs 5-nél rövidebb kör, és a gráfnak d2 + 1 csúcsa van, akkor d ∈ {2, 3, 7, 57} lehet csak.

ELK’13


18/21

Észrevétel. Ha egy d-reguláris gráfban nincs 5-nél rövidebb kör, akkor a gráfnak legalább 1 + d + d(d − 1) = d2 + 1 csúcsa van. Hoffman–Singleton-tétel (1960). „Beauty is rare.” Ha egy d-reguláris gráfban nincs 5-nél rövidebb kör, és a gráfnak d2 + 1 csúcsa van, akkor d ∈ {2, 3, 7, 57} lehet csak.

d=2 C5

d=3 Petersen-gráf

ELK’13


18/21

Hoffman–Singleton-tétel (1960). „Beauty is rare.” Ha egy d-reguláris gráfban nincs 5-nél rövidebb kör, és a gráfnak d2 + 1 csúcsa van, akkor d ∈ {2, 3, 7, 57} lehet csak.

d=7 Hoffman–Singleton-gráf

ELK’13


18/21

Hoffman–Singleton-tétel (1960). „Beauty is rare.” Ha egy d-reguláris gráfban nincs 5-nél rövidebb kör, és a gráfnak d2 + 1 csúcsa van, akkor d ∈ {2, 3, 7, 57} lehet csak.

d=7 Hoffman–Singleton-gráf

d = 57

ELK’13

Egy kombinatorikus geometriai példa

19/21

Fisher-egyenlőtlenség. Ha az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesül, hogy bármely kettő metszetének elemszáma ugyanaz a µ 6= 0 szám, akkor m ≤ n.

ELK’13


19/21

Fisher-egyenlőtlenség. Ha az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesül, hogy bármely kettő metszetének elemszáma ugyanaz a µ 6= 0 szám, akkor m ≤ n. Megjegyzés. A Fisher-egyenlőtlenségre adott Bose-féle bizonyítás (1948) indította el a lineáris algebrai módszerek használatát a halmazrendszerek vizsgálatában.

ELK’13


19/21

Fisher-egyenlőtlenség. Ha az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesül, hogy bármely kettő metszetének elemszáma ugyanaz a µ 6= 0 szám, akkor m ≤ n. Következmény. A sík m nem kollineáris pontja legalább m egyenest határoz meg.

ELK’13


19/21

Fisher-egyenlőtlenség. Ha az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesül, hogy bármely kettő metszetének elemszáma ugyanaz a µ 6= 0 szám, akkor m ≤ n. Következmény. A sík m nem kollineáris pontja legalább m egyenest határoz meg. Bizonyítás. Legyen P1 , . . . , Pm egy nem kollineáris ponthalmaz, és legyenek e1 , . . . , en az általuk meghatározott egyenesek. Minden Pi ponthoz hozzárendelünk egy Hi ⊆ {1, . . . , n} halmazt, amely a ponton átmenő e∗ egyenesek indexeit tartalmazza.

ELK’13


19/21

Fisher-egyenlőtlenség. Ha az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesül, hogy bármely kettő metszetének elemszáma ugyanaz a µ 6= 0 szám, akkor m ≤ n. Következmény. A sík m nem kollineáris pontja legalább m egyenest határoz meg. Bizonyítás. Legyen P1 , . . . , Pm egy nem kollineáris ponthalmaz, és legyenek e1 , . . . , en az általuk meghatározott egyenesek. Minden Pi ponthoz hozzárendelünk egy Hi ⊆ {1, . . . , n} halmazt, amely a ponton átmenő e∗ egyenesek indexeit tartalmazza. 1. Különböző pontokhoz különböző halmazokat rendelünk. (Mivel nem kollineárisak a pontok.)

ELK’13


19/21

Fisher-egyenlőtlenség. Ha az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesül, hogy bármely kettő metszetének elemszáma ugyanaz a µ 6= 0 szám, akkor m ≤ n. Következmény. A sík m nem kollineáris pontja legalább m egyenest határoz meg. Bizonyítás. Legyen P1 , . . . , Pm egy nem kollineáris ponthalmaz, és legyenek e1 , . . . , en az általuk meghatározott egyenesek. Minden Pi ponthoz hozzárendelünk egy Hi ⊆ {1, . . . , n} halmazt, amely a ponton átmenő e∗ egyenesek indexeit tartalmazza. 1. Különböző pontokhoz különböző halmazokat rendelünk. (Mivel nem kollineárisak a pontok.) 2. |Hi ∩ Hj | = 1 tetszőleges i 6= j esetén. (Hi ∩ Hj a Pi Pj egyenes indexét tartalmazza.)

ELK’13


19/21

Fisher-egyenlőtlenség. Ha az {1, . . . , n} alaphalmaz m darab különböző részhalmazára teljesül, hogy bármely kettő metszetének elemszáma ugyanaz a µ 6= 0 szám, akkor m ≤ n. Következmény. A sík m nem kollineáris pontja legalább m egyenest határoz meg. Bizonyítás. Legyen P1 , . . . , Pm egy nem kollineáris ponthalmaz, és legyenek e1 , . . . , en az általuk meghatározott egyenesek. Minden Pi ponthoz hozzárendelünk egy Hi ⊆ {1, . . . , n} halmazt, amely a ponton átmenő e∗ egyenesek indexeit tartalmazza. 1. Különböző pontokhoz különböző halmazokat rendelünk. (Mivel nem kollineárisak a pontok.) 2. |Hi ∩ Hj | = 1 tetszőleges i 6= j esetén. (Hi ∩ Hj a Pi Pj egyenes indexét tartalmazza.) 3. Fisher-egyenlőtlenség =⇒ m ≤ n.

ELK’13

Ajánlott irodalom

20/21

Babai L., Frankl P.: Linear Algebra Methods in Combinatorics

Babai László

Frankl Péter

ELK’13

THE END

Köszönöm a figyelmet!

21/21

Lineáris algebrai módszerek a kombinatorikában

Recommend Documents