Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

3. Felbontás teljes részgráfokra

3. Felbontás teljes részgráfokra

Egy teljes gráf triviálisan felbontható egyetlen teljes gráfra. A De Bruijn–Erdős tétel azt mutatja, hogy nem triviális felbontáshoz már sokkal több teljes részgráf kell.

3. tétel. Ha K n éleit m //>// 1 teljes részgráfra bontjuk fel, akkor m ? n .

Egy tömör bizonyítás Conwaytől: legyenek a felbontásban szereplő teljes részgráfok ponthalmazai A 1 , A 2 , , A m és tegyük fel, hogy n ? m . Jelöljük d ( i ) -vel az i pontot tartalmazó A j halmazok számát. Könnyű látni, hogy tetszőleges i ? A j esetén d ( i ) ? A j . Ez és az n ? m egyenlőtlenség adja, hogy n m - n d ( i ) ? n m - m A j , azaz

1 n ( m - d ( i ) ) ? 1 m ( n - A j ) .

(1)

Csak éppen az nem látszik, mire is jó ez. Arra, hogy összeadva őket minden i ? A j párra kapjuk

? i = 1 n ? A j ? i 1 n ( m - d ( i ) ) ? ? j = 1 m ? i ? A j 1 m ( n - A j ) ,

de mindkét oldal értéke 1! Ugyanis a belső összegek azonos mennyiségeket adnak össze, a baloldalon m - d ( i ) -szer, a jobboldalon n - A j -szer. Ezért az (1) egyenlőtlenség valójában egyenlőség, emiatt az n ? m (és mellesleg minden d ( i ) ? A j ) egyenlőség kell legyen.

4. Feladat. Lássuk be, hogy a 3. tételben egyenlőség ( m = n ) csak két esetben lehet: 1. A felbontás egy fix pontot tartalmazó párokból és a fix pontot elkerülő n - 1 -elemű halmazból áll. 2. Valamely q //>// 1 egészre n = q 2 + q + 1 , a felbontásban minden A i halmaz q + 1 elemű, minden pontot q + 1 halmaz tartalmaz, bármely két különböző halmaz metszi egymást ( q -rendű véges projektív sík).

A 3. tétel következő általánosítását Fisher-egyenlőtlenségnek nevezik.

4. tétel. Ha K n éleit m teljes részgráfra bontjuk fel úgy, hogy minden élt pontosan ? -szor fedünk és egyik fedő részgráf sem maga K n , akkor m ? n .

Ennek a tételnek csak lineáris algebrát használó bizonyításai ismeretesek. Mielőtt rátérnénk a bizonyításra tisztázzuk az ahhoz szükséges alapvető fogalmakat és tételt.

Ha adottak az x ¯ 1 , x ¯ 2 , x ¯ 3 vektorok, akkor kérdezhetjük, hogy vannak-e olyan ? 1 , ? 2 , ? 3 , számok, amelyek közül nem mindegyik 0, és teljesül a

? 1 · x ¯ 1 + ? 2 · x ¯ 2 + ? 3 · x ¯ 3 = 0 ¯

(2)

lineáris összefüggés. Ha vannak ilyen számok, akkor vektorainkat lineárisan összefüggőnek nevezzük. Ha a (2) összefüggés csak abban az esetben teljesül, amikor ? 1 = ? 2 = ? 3 = 0 , akkor a vektorok lineárisan függetlenek.

Ha x ¯ 1 , x ¯ 2 , x ¯ 3 a sík három vektora, akkor mindenképpen lineárisan összefüggőek (lásd az ábrát). Ha viszont x ¯ 1 , x ¯ 2 , x ¯ 3 a tér három nem egy síkba eső vektora, akkor lineárisan függetlenek.

5. ábra.

Ezek a fogalmak általánosíthatók: engedjük meg, hogy az x ¯ 1 , , x ¯ n vektoroknak m koordinátája legyen. Ebben az általános esetben is igaz, hogy az x ¯ 1 , , x ¯ n vektorok csak akkor lehetnek lineárisan függetlenek, ha n ? m . Ha ugyanis m //>// n , akkor a ? i = 1 n ? i · x ¯ i = 0 ¯ összefüggést koordinátánként felírva egy olyan homogén lineáris egyenletrendszert kapunk az ? i változókra, amelyben több az ismeretlen, mint az egyenlet, így biztosan van a triviális ? 1 = = ? m = 0 megoldástól különböző megoldása is.

Visszatérünk a 4. tétel igazolásához.

A 3. tétel jelöléseit használva feltehetjük, hogy minden i -re ( 1 ? i ? n ) d ( i ) = ? + ? i , ahol ? i //>// 0 . ? -nál kevesebb részgráf ugyanis nem tudja ? -szor lefedni az i -edik csúcsból kiinduló éleket; ? részgráf még éppen elegendő lenne, ha mindegyik tartalmazná az i -edik csúcsból induló összes élt, azaz ha mindegyik a teljes K n gráf lenne. Definiáljunk minden i ponthoz egy m komponensű x ¯ i vektort, melyben a j -edik koordináta aszerint 1 vagy 0, hogy az i pont benne van e A j -ben. Azt állítjuk, hogy vektoraink lineárisan függetlenek, amiből következik a tétel.

Bizonyítsunk indirekten! Tegyük fel, hogy valós ? i számokkal teljesül ? i = 1 n ? i x ¯ i = 0 . Képezzük az egyenlet mindkét oldalának x ¯ j -vel vett skaláris szorzatát. Megfigyelve, hogy x ¯ i x ¯ j = ? ha i ? j és x ¯ i x ¯ j = ? + ? i ha i = j , azt kapjuk, hogy minden j -re

? j = - ? ? j ? i = 1 n ? i .

Ha egyenleteinket összeadjuk, azt kapjuk, hogy

? j = 1 n ? j = - ? ? j = 1 n 1 ? j ? j = 1 n ? j

ami csak ? i = 1 n ? i = 0 esetén teljesülhet. Korábbi egyenletünkből következik, hogy ilyenkor mindegyik ? j együttható zérus, azaz vektoraink lineárisan függetlenek.