Ú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
2. Felbontás faktorokra

2. Felbontás faktorokra

Tegyük fel, hogy n páros, nevezzük faktornak az n / 2 páronként közös pont nélküli élből álló gráfot. Talán a legrégebben ismert felbontási tétel a következő.

1. tétel. Minden páros n esetén K n felbontható n - 1 faktorra.

A tétel egy gyakorlati alkalmazása, hogy páros n esetén körmérkőzés szervezhető n játékos számára n - 1 fordulóban úgy, hogy mindenki mindenkivel pontosan egyszer játszik. A felbontás faktorai a fordulók párosítását jelentik. A tétel legegyszerűbb bizonyítása a következő: i = 1 , 2 , , n - 1 esetén az i -edik faktor álljon a ( 0 , i ) élből és az ( i - j , i + j ) ( mod n - 1 ) élekből, ahol j = 1 , 2 , , n 2 - 1 .

3. ábra. Körmérkőzéses bajnokság 8 csapat között. Az i -edik forduló ( i = 1 , 2, 3, 4, 5, 6 és 7) mérkőzései mod 7 értve: ( 0 , i ) , ( i - 1 , i + 1 ) , ( i - 2 , i + 2 ) és ( i - 3 , i + 3 )

Nem is olyan könnyű ettől különböző megoldásokat találni, melyek minden páros n -re működnek… Ha n = 2 k , akkor egy másik szellemes megoldást kaphatunk úgy, hogy a pontokat bináris formában írjuk ( k hosszúságú 0 - 1 vektorként) és két pont közötti élt pontosan akkor tesszük ugyanabba a faktorba, ha a pontok koordinátánként vett mod 2 összegvektora ugyanaz.

4. ábra. Körmérkőzéses bajnokság 8 csapat között. Ha i = A B C 2 , akkor az i -edik fordulóban a b c 2 azzal az a ' b ' c 2 ' csapattal játszik, amelyikre a + a ' ? A , b + b ' ? B , c + c ' ? C ( mod 2 )

A két megoldás közti alapvető különbséget jól megfigyelhetjük n = 8 esetén: az elsőnél bármely két faktor egyesítése nyolcpontú kört alkot, a másodiknál ez nem igaz.

Az 1. tételt már a tizenkilencedik században ismerték, de kézenfekvő általánosítását csak 1975-ben bizonyította Baranyai Zsolt. A Baranyai-tételben K n helyett K n r szerepel, ami n pont összes r elemű részhalmazát jelenti, a faktor pedig páronként diszjunkt r elemű halmazokat jelent.

Például n = 16 , r = 4 esetén a „Baranyai-faktorizáció” azt jelenti, hogy 16 elem négyesei 16 4 : 16 4 = 15 3 = 455 csoportba oszthatók, minden csoportban négy diszjunkt négyessel. Tehát 16 bridzselő négy asztalnál 455 napig játszhat úgy, hogy bármely négy pontosan egyszer ül közös asztalnál. Ha csak azt akarjuk, hogy bármely két játékos pontosan egyszer üljön közös asztalnál, akkor 5 nap is elég – ezt taglalja Montágh Balázs cikke – bridzsezők helyett motorversenyzőkkel…

2. tétel. Ha n osztható r -rel, akkor K n r felbontható n - 1 r - 1 faktorra.

A faktorok száma abból adódik, hogy összesen n r darab r -elemű részhalmaz van, egy faktoron belül pedig n r , és n r : n r = n - 1 r - 1 . A tétel az r = 2 speciális esetben az 1. tételt adja. Viszont (ellentétben az 1. tétellel) algebrai jellegű bizonyítása nem ismeretes. A 2. tétel bizonyításának hátterében hálózati folyamok állnak, de elég egy önmagában is igen érdekes speciális eset a bizonyításhoz, nevezetesen Baranyai kerekítési lemmája.

1. lemma. Tegyük fel, hogy egy A mátrix sor és oszlopösszegei egész számok. Ekkor a mátrix elemei kicserélhetők alsó vagy felső egész részeikkel úgy, hogy olyan B mátrixot kapunk, melynek sor és oszlopösszegei ugyanazok mint az A mátrixé.

Bizonyítás. Az A mátrix egy elemét nevezzük rossz elemnek, ha nem egész. Ha A -ban nincs rossz elem, akkor A = B máris megfelel. Egyébként a következő algoritmus csökkenti a rossz elemek számát a sor és oszlopösszegek és az egész részek változtatása nélkül. Válasszunk egy r 1 rossz elemet, ennek sorában van egy másik rossz elem is, r 2 , mivel a sorösszeg egész. Ezután r 2 oszlopában választhatunk egy r 3 rossz elemet, majd r 3 sorában egy r 4 rossz elemet… Az eljárás során előbb utóbb visszajutunk ugyanahhoz az elemhez (nem feltétlenül r 1 -hez). Mindenesetre kapunk páros számú rossz elemet melyek között a ciklikusan egymásra következők felváltva ugyanabban a sorban, illetve oszlopban vannak. Nevezzük ezt rossz körnek. A rossz kör minden egyes elemének tekintsük az alsó és felső egész részétől vett távolság kisebbikét (egyenlőség esetén valamelyiket) aztán ezen távolságok legkisebbikét a rossz körön jelöljük ? -nal. Nyilvánvaló, hogy a rossz kör elemeihez váltakozva ? -t hozzáadva, illetve kivonva a mátrix sor és oszlopösszegei és az elemek egész részei nem változnak, viszont legalább egy rossz elem megszűnik.

A fenti algoritmust elég sokszor alkalmazva kapjuk a kívánt B mátrixot.

Igen meglepő, hogy az előbbi lemmán alapszik a 2. tétel bizonyítása, mégpedig indukcióval. A bizonyítás annyiban trükkös, hogy a 2. tételnél látszólag erősebb tételt lehet indukcióval bizonyítani. Vezessünk be néhány jelölést. Legyen n és r a 2. tétel szerint, M : = n - 1 r - 1 (a faktorok száma) és m : = n / r (az r -elemű halmazok száma a faktorokban). Használni fogjuk a [ k ] jelölést az { 1 , 2 , , k } halmazra, [ 0 ] az üres halmaz – azaz Ø .

K n r egy faktora a csúcsok [ n ] halmazát m darab diszjunkt r elemű részhalmazra bontja. Tekintsük [ n ] egy tetszőleges [ k ] ( 0 ? k ? n ) részhalmazát. A faktor tagjainak [ k ] -val való metszetei egymástól diszjunktak és uniójuk [ k ] , azaz [ k ] egy m részhalmazra való felbontását, úgynevezett m - partícióját adják. Míg a faktor minden tagjának elemszáma r , addig a partíció tagjai nem feltétlenül azonos elemszámúak.

Példa: n = 6 , r = 2 , k = 2 ekkor m = 3 . K n r egy faktora a

{ { 5 , 6 } , { 1 , 3 } , { 2 , 4 } }

halmazrendszer. Ennek [ k ] = [ 2 ] -vel vett metszetei

{ Ø , { 1 } , { 2 } } .

Az

{ { 5 , 6 } , { 3 , 4 } , { 1 , 2 } }

faktorból pedig [ 2 ] -nek a

{ Ø , Ø , [ 2 ] }

3-partícióját kapjuk.

Ha K n r -t felbontottuk M faktorra, akkor azok mindegyikéből kaphatunk egy m partíciót [ k ] -ra. [ k ] egy S részhalmaza ( S ? r ) annyiszor szerepel, ahányféleképpen a kimaradt k + 1 , , n elemekből kiválasztható r - S darab. Ezért a 2. tételből következik az alábbi állítás.

2.* tétel. Legyen r osztója n -nek. Ekkor bármely 0 ? k ? n esetén van M darab olyan m -partíciója [ k ] -nak amelyben minden S ? [ k ] pontosan n - k r - S számú partícióban fordul elő.

Az előző példában M = 5 . Az első négy partíció lehet

{ Ø , { 1 } , { 2 } } ,

az ötödik pedig

{ Ø , Ø , [ 2 ] } .

A 2 * tétel k = n esetén trükkösen adja a 2. tételt: bármely S ? [ k ] pontosan 0 r - S partícióban fordul elő. Ez a szám azonban csak S = r esetén nem nulla (ekkor 1) ami pontosan azt jelenti, hogy csak az r elemű halmazok szerepelnek a partíciókban és mindegyik pontosan egyben.

A 2 * tétel előnye, hogy k szerinti indukcióval bizonyíthatjuk. Ha k = 0 , akkor az M partíció mindegyike csupa üres halmazból állhat. Tegyük fel, hogy valamely k //<// n -re megvannak az A 1 , , A M m -partíciók. Most mindegyik partíció egy és csak egy halmazát ki kell bővítenünk a k + 1 elemmel úgy, hogy bármely S ? [ k ] halmaznak n - k - 1 r - S - 1 példányát bővítsük, n - k - 1 r - S példányát pedig ne bővítsük ki k + 1 -gyel. Első lépésben bízzuk a választást a véletlenre! Az S halmazt n - k - 1 r - S - 1 / n - k r - S = r - S n - k valószínűséggel kell kibővíteni. A véletlent Baranyai kerekítési módszerével küszöböljük ki.

Írjuk ezeket a kibővítési valószínűségeket egy M × 2 k -as A mátrixba! A oszlopai [ k ] részhalmazainak felelnek meg, a sorok pedig a partícióknak (lásd a 3. ábrát). Az A mátrix A i sorában és S ? [ k ] oszlopában álló elem tehát 0 lesz, ha S nem szerepel A i -ben, ha pedig szerepel, akkor értéke r - S n - k , illetve az üres halmaz esetén, amely többször is szerepelhet ugyanabban a partícióban, ez az érték t · r n - k , ahol t jelöli az üres halmaz multiplicitását A i -ben.

Érdemes ellenőrizni, hogy a példa esetén az A mátrix első négy sora [ 1 / 2 , 1 / 4 , 1 / 4 , 0 ] és az ötödik sora [ 1 , 0 , 0 , 0 ] ha az első oszlop az üres halmaznak, a negyedik oszlop meg [ 2 ] = { 1 , 2 } -nek felel meg.

Nem nehéz belátni, hogy az A mátrix minden sorösszege 1 és az S -hez tartozó ( S ? [ k ] ) oszlopösszeg n - k - 1 r - S - 1 .

Ezután a kerekítő lemmát alkalmazzuk az A mátrixra ami adja a B mátrixot. A B mátrix A i -hez tartozó sorában egyetlen egyes van, ennek oszlopa egy S i ? A i blokkot definiál.

Példánkban:

Ezután definiálunk új m -partíciókat [ k + 1 ] -en úgy, hogy (minden i -re) A i -ben S i -t kicseréljük S i ? { k + 1 } -re, A i többi blokkját változatlanul hagyva. Az új partíciók kielégítik a 2* tételt k + 1 -gyel, ennek ellenőrzését is az olvasóra bízzuk. Példánkban a [ 3 ] halmaz megfelelő partíciói:

Ø , { 1 } , { 2 , 3 } ; Ø , { 1 , 3 } , { 2 } ; { 3 } , { 1 } , { 2 } ; { 3 } , { 1 } , { 2 } ; { 3 } , Ø , { 1 , 2 } .