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

4. Felbontás teljes páros részgráfokra

4. Felbontás teljes páros részgráfokra

Teljes páros gráfnak nevezzük azokat a gráfokat melyeknek ponthalmaza két diszjunkt halmaz, A , B egyesítése és élei azon párok, melyeknek egyik pontja A -ban másik pontja B -ben van. Jelöljük [ A , B ] -vel a teljes páros gráfot.

5. tétel. Ha K n éleit m teljes páros részgráfra bontjuk fel, akkor m ? n - 1 .

Erre a tételre is csak lineáris algebrát használó bizonyítások ismeretesek. Talán a következő bizonyítás a legfrappánsabb, ez Tverbergtől származik. Legyenek [ A i , B i ] a felbontásban szereplő teljes páros gráfok, i = 1 , 2 , , m és legyenek x 1 , x 2 , , x n a K n pontjaihoz rendelt valós változók. Ekkor a következő azonosság teljesül:

? i = 1 m ? j ? A i x j ? j ? B i x j = ? 1 ? i //<// j ? n x i x j = 1 2 ? i = 1 n x i 2 - ? i = 1 n x i 2 .

Tekintsük a következő m + 1 egyenletből álló homogén lineáris egyenletrendszert: ? j ? A i x j = 0 ahol i = 1 , 2 , , m és ? i = 1 n x i = 0 . Ennek nem létezhet nem triviális megoldása, mert a megoldást behelyettesítve az azonosságba a baloldalon nullát, a jobboldalon negatív számot kapnánk. Ez azt jelenti, hogy a változók száma nem nagyobb az egyenletek számánál, azaz n ? m + 1 .

Az 5. tétel háttere egy kódelméleti kérdés. A kódelméletben két m hosszúságú 0 - 1 sorozat Hamming távolságának nevezik azon koordináták számát amelyben a két sorozat különbözik. Ennek egy általánosítását Pierce vetette fel a 1972-ben. Tekintsünk m hosszúságú sorozatokat, ahol 0, 1 mellett * szimbólumot is használhatunk, amit gyakran dzsókernek neveznek. Két ilyen sorozat Hamming távolságának azon koordináták számát nevezzük, ahol az egyik sorozat 0, a másik pedig 1. Például 01 * 10 és 101 * 0 Hamming-távolsága 2. Ez azért hasznos, mert bármely összefüggő gráf pontjaihoz hozzá lehet rendelni (valamilyen m -re) m hosszúságú 0 – 1 – * sorozatokat úgy, hogy bármely két pont között a Hamming-távolság és a gráf-távolság megegyezik. (Gráf-távolság: a két pont közötti legrövidebb út éleinek száma.) Próbáljuk ezt bebizonyítani, nem nehéz! Az viszont nehéz probléma, hogy egy adott gráfhoz mi a legkisebb m , amelyre ilyen hozzárendelés (kódolás) lehetséges.

Az 5. tétel azzal ekvivalens, hogy K n teljes gráf esetén legalább n - 1 hosszúságú 0 – 1 – * sorozatokat kell használni a hozzárendeléshez (kódoláshoz).

5. feladat. Bizonyítsuk be az ekvivalenciát, valamint azt is, hogy n - 1 hosszúságú sorozatokkal meg is lehet oldani a hozzárendelést, azaz az 5. tételben m = n - 1 lehetséges. (Például a 0 * , 10, 11 sorozatok jók K 3 esetén.)

Az 5. tételnek irányított változata is van, próbáljuk meg igazolni, Tverberg módszere most is segíthet:

6. feladat. Mutassuk meg, hogy a szimmetrikusan irányított K n -et (minden él két irányt kap) nem lehet n -nél kevesebb irányított teljes páros gráfra felbontani.

Két könyvet ajánlunk az olvasóknak:

J. H. van Lint–R. M. Wilson: A course in Combinatorics, Cambridge University Press.

M. Aigner–G., M. Ziegler: Proofs from the BOOK, Springer Verlag.