Description
Tekintsük a következő gyepesedési problémát. Egy n×n mezőből álló
földterület néhány mezője gyepes. Egy üres mező pontosan akkor
gyepesedik be, ha van olyan t×t méretű ,,részmátrixa'' a földterületnek,
amely tartalmazza a szóban forgó üres mezőt, és a többi t^2 - 1 mezője
gyepes. Egy gyephalmazt perkolálónak nevezünk, ha az imént definiált
gyepesedési lépések ismételt végrehajtásával az egész földterület
begyepesedik. Célunk annak meghatározása, hogy egy perkoláló gyephalmaz
legkevesebb hány gyepes mezőből áll. A probléma természetes módon
általánosítható magasabb dimenzióra is.
Az extremális kérdésre pontos választ adott Balogh József, Bollobás
Béla, Robert Morris és Oliver Riordan 2012-ben, lineáris algebrai
eszközöket használva. A szeminárium első felében az ő elegáns
bizonyításukat ismertetem. (Kiderült, hogy Noga Alon már 1985-ben
bizonyította ugyanezt, más terminológiát használva, absztraktabb
algebrai eszközökkel.)
Süli Ákos BSc hallgató a tétel elemi bizonyításán dolgozik. A
szeminárium második felében az eddigi részeredményekről és ígéretesnek
tűnő észrevételekről / sejtésekről beszélek.