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

2. Zarankiewicz problémája

2. Zarankiewicz problémája

Második ártalmatlannak tűnő kérdésünk az alábbi:

Zarankiewicz problémája. Tekintsük az n × m -es négyzetrácsot, azaz az

{ ( i , j ) : i = 1 , n , j = 1 , , m }

alakú rácspontokat. Válasszunk ki ezek közül minél többet úgy, hogy a kiválasztott pontok között ne legyen négy olyan pont, amelyek a koordináta-tengelyekkel párhuzamos oldalú téglalap csúcsai! Hány pontot választhatunk ki ilyen módon?

Szimmetria okokból feltehető, hogy n ? m . Ezt a fejezet hátralevő részében mi is feltesszük. Ha n = 1 , akkor a feladat triviális, a válasz m . A következő néhány esettel érdemes először önállóan próbálkozni.

4. feladat Oldjuk meg Zarankiewicz problémáját n = 2 , 3, és 4 esetén!

Az n = 2 esetben könnyű a megoldás, hisz csak egyetlen oszlopban lehet két kiválasztott pont, a többiben legfeljebb egy. Ilymódon a kiválasztott pontok száma legfeljebb m + 1 .

Érdemes megjegyezni, hogy ha két oszlopot vagy sort felcserélünk (vagy általánosabban a sorokat és az oszlopokat tetszőlegesen permutáljuk), akkor a megkívánt tulajdonság érvényben marad és persze a kiválasztott pontok száma is változatlan. Ez a megoldással kapcsolatos diszkussziót, illetve a megoldás lerajzolását könnyíti meg.

n = 3 -ra két aleset lehetséges. Ha van olyan oszlop, amelyben mindhárom pontot kiválasztottuk, akkor az összes további oszlopban legfeljebb egy pontot választhattunk ki, azaz összesen legfeljebb m + 2 pontot. Ha minden oszlopban legfeljebb két kiválasztott pont található, akkor legfeljebb három olyan oszlop lehet, amelyben két kiválasztott pont is van. Valóban, három sorból három sorpár választható ki, így ha négy olyan oszlop lenne, amelyben két kiválasztott pont van, akkor lenne két olyan oszlop, amelyekben a kiválasztott pontok ugyanabban a sorpárban vannak, azaz keletkezne tiltott téglalap. Három ilyen oszlop viszont lehet is, mindegyikben a három sorpár egyikében találhatók a kiválasztott pontok. Eszerint ebben az esetben ezen három oszlopban hat, a többiekben egy-egy, vagyis összesen m + 3 pont lehet.

Az egyik Kalmár verseny feladata a Zarankiewicz probléma n = 3 esetének „Ramsey típusú[5] változata”:

5. feladat A 3 × 7 -es négyzetrács mind a 21 rácspontját pirosra vagy kékre színezzük. Mutassuk meg, hogy biztosan keletkezik olyan, tengelyekkel párhuzamos helyzetű téglalap, amelynek mindegyik csúcsa azonos színű.

Az eddigiekben láttuk, hogy az azonos oszlopban lévő kiválasztott pontokat érdemes a megfelelő sorok halmazával azonosítani. Indexeljük a sorokat az 1 , 2 , , n számokkal, az oszlopokat pedig az 1 , , m számokkal. Minden oszlopot az { 1 , , n } halmaz bizonyos részhalmazaival azonosíthatunk, mégpedig azokkal, amely indexű sorokban a kiválasztott pontok elhelyezkednek. Feltételünk éppen az, hogy ezeknek a kiválasztott részhalmazoknak páronként legfeljebb egy közös eleme legyen. A kiválasztott pontok száma megfelel a halmazok elemszámai összegének. A két terminológiát (rácspontos illetve halmazos) egyszerre fogjuk használni a későbbiekben.

Zarankiewicz problémája halmazokkal. Válasszuk ki az { 1 , n } halmaz néhány részhalmazát, A 1 , , A m -et az alábbi ( * ) feltételnek megfelelően.

( * ) Bármely két különböző részhalmaz metszete legfeljebb egyelemű, azaz A i ? A j ? 1 , ha i j , i , j = 1 , , m .

Mekkora lehet A 1 + A 2 + + A m maximuma?

Az is világos, hogy igazából csak azokkal a halmazokkal kell foglalkozzunk, amelyeknek legalább két eleme van (az eredetiben csak azokat az oszlopokat kell néznünk, amelyekben legalább két kiválasztott pont van). Még az is előfordulhat, hogy valamely halmaz többször fordul elő, akkor azonban szükségképpen egyelemű kell legyen. Ha legalább kételemű halmaz m -nél kevesebb van, mondjuk csak s , akkor ezek elemszámainak összegéhez még hozzá kell adjunk ( m - s ) -et.

Folytassuk a 4. feladat megoldását az n = 4 esettel! Most is növekszik az alesetek száma. Ha van négy pontú halmaz, akkor az összes többi csak egypontú lehet, azaz a keresett elemszámösszeg legfeljebb m + 3 . Ha ilyen halmaz nincs, de van háromelemű, akkor csak egy ilyen lehet. A két pontú halmazok mindegyike egy pontot tartalmaz halmazunkból és tartalmazza a háromelemű halmazból kimaradó pontot. Ez azt mutatja, hogy legfeljebb három kételemű halmaz lehet. Így ebben az alesetben összesen legfeljebb m + 5 a halmazok elemszámának összege. Végül, ha minden halmaz legfeljebb kételemű, akkor legfeljebb 4 2 = 6 kételemű halmaz lehet, vagyis m ? 6 -ra összesen legfeljebb m + 6 a keresett maximum, azaz a kiválasztott rácspontok száma.

2. ábra.

Ha m = 4 , akkor a korábbi eljárás (egy háromelemű, három kételemű halmaz) adja a legtöbb kiválasztott pontot, 9-et.

Ha m = 5 , akkor a két utóbbi eljárás egyaránt 10 pontot ad meg. Az eddigiek alapján érezhető, hogy ha rögzített n esetén nagy m -ekre szeretnénk a kiválasztott pontok számának maximumát meghatározni, akkor a legalább két pontot tartalmazó oszlopokban kiválasztott pontok számát lenne jó meghatározni, a halmazos átfogalmazásnak megfelelően. Ebben a megfogalmazásban világos, hogy m = n 2 esetén az összes kételemű részhalmazt kiválasztva n ( n - 1 ) -et kapunk az elemszámok összegeként. Eszerint m = s + n ( n - 1 ) / 2 -re Zarankiewicz feladatában a keresett maximum legalább n ( n - 1 ) + s . Az persze nem világos, hogy ennél jobbat nem is tehetünk, de a következő feladatban éppen ezt kell belátnunk.

6. feladat Oldjuk meg Zarankiewicz problémáját m ? n ( n - 1 ) 2 esetén!

Most Zarankiewicz feladatának másik végletét vizsgáljuk, nevezetesen azt, amikor m = n . Ehhez a probléma alábbi megfogalmazását használjuk.

Zarankiewicz problémája mátrixszal. Egy m × n -es mátrix minden eleme 0 vagy 1. Legfeljebb hány egyes lehet mátrixunkban, ha két sor és két oszlop négy keresztezési mezejében soha nem állhat mindenütt egyes?

Ez a megfogalmazás nyilvánvalóan azonos a rácspontossal, előnye viszont, hogy a mátrix sorai (ill. oszlopai) vektorok, amelyekkel vektorműveleteket végezhetünk. Célunk az lesz, hogy ebben a megfogalmazásban felülről megbecsüljük az egyesek számát. A most következő bizonyítás Reiman Istvántól származik, megtalálható [K]-ban a 201–203. oldalon és [R]-ben a 334–336. oldalon. Mi most csak az m = n esetet vizsgáljuk.

A két- illetve háromdimenziós koordinátageometriában tanultakhoz hasonlóan az ( x 1 , x 2 , , x n ) valós számokból álló n -eseket ( n -dimenziós) vektoroknak szokás nevezni. A v = ( x 1 , x 2 , , x n ) és w = ( y 1 , y 2 , , y n ) vektor összege, illetve skaláris szorzata a v + w = ( x 1 + y 1 , x 2 + y 2 , , x n + y n ) , illetve a v w = x 1 y 1 + x 2 y 2 + + x n y n képletekkel definiálható. A v = ( x 1 , x 2 , , x n ) vektor ? számmal való szorzata a ? v = ( ? x 1 , ? x 2 , , ? x n ) vektor. Két vektor összege tehát vektor, két vektor skaláris szorzata viszont (valós) szám. A skaláris szorzást egyszerűen a vektorok egymás mellé írásával jelöljük, fent már használtuk is ezt a jelölést. Nem nehéz ellenőrizni, hogy a skaláris szorzás két- és három-dimenzióban megismert műveleti szabályai (pl. disztributivitás) itt is alkalmazhatók.

Mátrixunk sorait felfoghatjuk n -dimenziós vektoroknak (amelyeknek minden koordinátája 0 vagy 1), legyenek ezek a 1 , a 2 , , a n . Vegyük észre, hogy i ? j esetén a i a j éppen az a i és a j azonos helyen álló 1-eseinek száma, és így a i a j = 0 vagy 1, hiszen különben lenne két-két sor és oszlop, amelyek keresztezési mezőiben négy egyes állna. Tehát:

( a 1 + a 2 + + a n ) 2 = ? i = 1 n a i 2 + 2 ? i //<// j a i a j ? E + n ( n - 1 ) ,

(A)

ahol E az 1-esek száma a mátrixban. Jelölje a k -adik oszlopban lévő 1-esek számát ? k . Ekkor nyilván E = ? 1 + ? 2 + + ? n , és a 1 + a 2 + + a n = ? 1 , ? 2 , , ? n . Így

( a 1 + a 2 + + a n ) (  a 1 + a 2 + + a n ) = ? 1 2 + ? 2 2 + + ? n 2 .

A számtani és négyzetes közép közti egyenlőtlenséget felhasználva:

E 2 n = ? 1 + ? 2 + + ? n 2 n ? ? 1 2 + ? 2 2 + + ? n 2 = = a 1 + a 2 + + a n 2 ? E + n ( n - 1 ) ;

vagyis E 2 - E n - n 2 ( n - 1 ) ? 0 , ahonnan

E ? n + n 2 + 4 n 2 ( n - 1 ) 2 = n 2 1 + 4 n - 3

(Z)

következik. Ez azt jelenti, hogy nagyjából E ? n n egyes lehet mátrixunkban. Beláttuk tehát az alábbi tételt.

1. Tétel. (Reiman) n × n -es 0-1 mátrixban legfeljebb n 2 ( 1 + 4 n - 3 ) egyes lehet, ha nincs két-két olyan sor és oszlop, amelyek keresztezési mezőiben mind a négy helyen egyes áll.

Most arra vagyunk kíváncsiak, hogy mikor állhat (Z)-ben egyenlőség: tehát n ( 1 + 4 n - 3 ) / 2 darab 1-es milyen n -re és hogyan helyezkedhet el az n × n -es mátrixban. Ehhez először is a 4 n - 3 számnak (páratlan) egésznek kell lennie, így 4 n - 3 = ( 2 k + 1 ) 2 , amiből n = k 2 + k + 1 . Másrészt a számtani és négyzetes közép egyenlő, ha ? 1 = ? 2 = = ? n , illetve (A)-ban egyenlőség van, ha a i a j = 1 (minden i ? j -re). Mivel a sorok és oszlopok szerepe szimmetrikus, az utóbbi két feltételnek az oszlopokra is teljesülnie kell.

2. Állítás. Az 1. Tételben az egyenlőség szükséges feltételei az alábbiak:

I. n = k 2 + k + 1 ;

II. minden oszlopban ugyanannyi, mégpedig k + 1 darab 1-es szerepel;

III. minden sorban ugyanannyi, mégpedig k + 1 darab 1-es szerepel;

IV. a i a j = 1 minden i ? j -re;

V. ha b i jelöli az i . oszlopvektort, akkor b i b j = 1 minden i ? j -re.

Természetesen adódik feladatként a legkisebb, azaz a k = 2 , 3 esetek vizsgálata. Az 1. tételben adott felső becslés itt 21, illetve 52. Ezekben az esetekben el is érhetők ezek a felső korlátok, a példák Zarankiewicz problémájának megoldását jelentik az n = m = 7 és n = m = 13 esetekben.

7. feladat Keressünk olyan 7 × 7 -es és 13 × 13 -as 0–1 mátrixot, amelyekben 21 illetve 52 egyes található és amelyekben nincs két-két olyan sor és oszlop, amelyek keresztezési mezőiben mind a négy helyen egyes áll!

Valószínűleg a 13 és 7 számok gyanúsak az olvasónak, hiszen az 1. feladatban éppen 13-szög szerepelt, a 2. feladat előtti felsorolás pedig épp a szabályos hétszöggel kezdődött. Ahhoz, hogy a kapcsolat világossá váljon, érdemes összehasonlítani a Zarankiewicz probléma halmazos változatát a 2. feladattal. A Zarankiewicz probléma halmazos változatában szereplő { 1 , , n } , ( n = k 2 + k + 1 ), halmaz elemeit feleltessük meg a 2. feladat n -szögének csúcsainak, az A 1 részhalmaz legyen egy teljesen szabálytalan részsokszög csúcsainak halmaza, A 2 , , A n pedig e részsokszög elforgatottjai. A halmazos Zarankiewicz probléma ( * ) feltétele most a 2. feladat állítása révén erősebben teljesül: egyenlőséggel. Az A 1 , , A n halmazok most mind k + 1 eleműek, elemszámaik összege tehát ( k 2 + k + 1 ) ( k + 1 ) , ami az 1. tételben említett felső korláttal egyezik meg. A keresett mátrixok (Gyárfás András cikkének 2. ábráján láthatjuk a hétszöget az elforgatott háromszögekkel, a 13-szöget pedig ebben a cikkben az 1. ábrán):

1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 1

3. ábra.

Gondolatmenetünk általános volt: mindazokban az esetekben, amelyekben az n = k 2 + k + 1 csúcsú szabályos sokszögnek van teljesen szabálytalan rész- ( k + 1 ) -szöge – például a 2. feladat előtt felsorolt n = 7 , 13 , 21 , 31 esetben – az n × n -es négyzetrácsból ki lehet választani ( k 2 + k + 1 ) ( k + 1 ) pontot úgy, hogy ne keletkezzen téglalap. Így a (Z) egyenlőtlenség egyenlőséggel teljesül. Akkor viszont az egyenlőség 2. állításban felsorolt szükséges feltételei is teljesülnek, speciálisan bármely két oszlopban is pontosan egy közös sorban van rácspont, ami azt jelenti, hogy a tsz. részsokszög bármely két elforgatottja pontosan egy pontban metszi egymást. Ezt érdemes közvetlenül is végiggondolni.

8. feladat Mutassukmeg közvetlenül, hogy a szabályos ( k 2 + k + 1 ) -szög tsz. rész- ( k + 1 ) -szögének bármely két elforgatottja pontosan egy csúcsban metszi egymást (a forgásszög 360 ° k 2 + k + 1 többszöröse)!

Emeljük ki még egyszer, hogy a halmazos megfogalmazásban n elemű halmaz olyan részhalmazait kellett megadnunk, hogy bármely két halmaznak legfeljebb egy közös eleme legyen. Gondoljunk vissza Montágh Balázs cikkére, ahol a salakmotorversenyek kapcsán bevezette a véges affin síkokat! Az affin sík egyenesei is olyan részhalmazok, amelyek teljesítik ezt a feltételt, így segítségükkel az n = k 2 , m = k 2 + k esetben megfelelő mátrixokat (ill. rácspont-kiválasztást) kaphatunk. Mivel ezek is elég szabályos struktúrák, remélhetjük, hogy az n = k 2 , m = k 2 + k esetben ezek adják a lehető legtöbb egyest mátrixunkban. Ezt feladatnak hagyjuk, a fenti m = n -re vonatkozó bizonyítást nem nehéz módosítani. Az utána következő feladat további segítséget jelent.

9. feladat Mutassukmeg, hogy Zarankiewicz problémájában n = k 2 , m = k 2 + k esetén legfeljebb k 2 ( k + 1 ) rácspontot jelölhetünk ki!

10. feladat Mutassukmeg, hogy Zarankiewicz problémájában legfeljebb

1 2 n + n 2 + 4 n m ( m - 1 )

rácspontot választhattunk ki.

Ez a feladat tehát általános felső becslést ad Zarankiewicz problémájára. A becslés n és m felcserélésével kapható változata is érvényes. Érdemes eltöprengeni az egyenlőség feltételein is. m = n esetén a (Z) fölső korlátot kapjuk vissza.

Ha eljátszunk a Zarankiewicz feladat kis eseteinek vizsgálatával, akkor láthatjuk, hogy az egymáshoz közeli paraméterek esetében a maximumot adó konfigurációk részei lehetnek egymásnak. Ilyen például a 4 × 6 -os, valamint a 7 × 7 -es eset is, mint azt az alábbi ábra mutatja.

4. ábra.

11. feladat Oldjuk meg Zarankiewicz problémáját az

a) n = m = 8 ,

b) n = m = 6 esetben!



[5] lásd könyvünkben Tóth Géza cikkét