Frankl-sejtés

Ha egy halmazrendszer bármely két halmazának az uniója is eleme a halmazrendszernek, akkor léteznie kell olyan elemnek, amely a halmazok legalább felében megtalálható?

A kombinatorikában az unióképzésre zárt halmazok sejtése egy alapvető probléma, ami a magyar Frankl Péter nevéhez fűződik 1979-ből és még azóta is megoldatlan.

Halmazrendszernek nevezzük egy előre adott alaphalmaz hatványhalmazának részhalmazaiból álló rendszert. Egy halmazrendszert unióképzésre zártnak (röviden unióra-zártnak) nevezünk, hogyha bármely két halmazának uniója is benne van a rendszerben. Természetesen ebből következik, hogy véges sok halmazának uniója is benne marad a rendszerben (ezt a tulajdonságot nevezzük véges unióra-zártságnak). Frankl Péter sejtése azt mondja ki, hogy tetszőleges véges unióra-zárt véges halmazokból álló halmazrendszerre - amely nem az üres halmaz – létezik olyan eleme az alaphalmaznak, amely legalább a halmazok felének eleme.

Ekvivalens alakok

Ha F egy unióra-zárt halmazrendszer, akkor az F-beli halmazok komplementereire teljesül, hogy azok zártak a metszetképzésre. Továbbá, ha egy elem a halmazok legalább feléhez tartozik F-ben, akkor ez pontosan akkor teljesül, ha ez az elem a komplementer halmazok legfeljebb feléhez tartozik. Így tehát egy ekvivalens formáját kapjuk a sejtésnek (eredetileg ebben az alakban mondta ki Frankl Péter): Bármely metszetképzésre-zárt nemüres halmazrendszerben létezik olyan elem, amely a halmazok legfeljebb feléhez tartozik.

Bár a fentiekben a Frankl-sejtést halmazrendszerekre mondtuk ki, ez az állítás megfogalmazható és vizsgálható a hálóelmélet szemszögéből is. A háló egy részben rendezett halmaz (vagyis poset), amelynek tetszőleges x és y eleméhez létezik egy egyértelmű legnagyobb elem (ahol x és y „találkozik”), ami egyikőjüknél sem nagyobb, illetve létezik egy egyértelmű legkisebb elem (ahol x és y „egyesül”), ami egyikőjüknél sem kisebb. Egy S halmaz összes részhalmazából álló rendszerben a halmazelméleti tartalmazás ad egy rendezést, tehát ez egy háló, ahol a „találkozás” a halmazelméleti metszetképzéssel, az „egyesülés” pedig a halmazelméleti unióképzéssel reprezentálható. Az ilyen típusú hálók a Boole-hálók.

A hálóelméleti megfogalmazása a Frankl-sejtésnek az, hogy bármely véges hálónak létezik olyan x eleme, amely nem áll elő két másik egyesüléseként, és az x-nél nem kisebb elemek száma legfeljebb a háló elemszámának a fele, ahol az egyenlőség csak a Boole-hálónál vétetik fel. Ahogy Abe (2000) megmutatta, ez a hálókra vonatkozó állítás ekvivalens az unióra-zárt halmazrendszerekre vonatkozó Frankl-sejtéssel, hiszen mindegyik háló megfeleltethető egy unióra-zárt halmazrendszernek és fordítva: minden unióra-zárt halmazrendszer megfeleltethető egy hálónak. Ez pedig azt jelenti, hogyha a megfeleltetett esetben igaz a Frankl-sejtés, akkor az eredeti esetben is igaz lesz. A sejtésnek ez a hálóelméleti megfogalmazása már bizonyított számos hálóosztályra (Abe 2000; Poonen 1992; Reinhold 2000), de még máig megoldatlan általános esetben.

Olyan halmazrendszerek, amelyekre áll a sejtés

A sejtés már sokféle halmazrendszer esetén bebizonyosodott. Például az alábbi esetekben:

• olyan halmazrendszerek esetén, amelyek legfeljebb 36 halmazból állnak;
• olyan halmazrendszerekre, amelyek uniója legfeljebb 11 elemű;
• olyan halmazrendszerekre, amelyekben a legkisebb halmaz elemszáma legfeljebb kettő

Előzmények

Frankl Péter 1979-ben metszetképzésre-zárt halmazrendszerekre mondta ki a sejtést és így a sejtést általában az ő nevéhez csatolják: Frankl-sejtés. A legelső publikáció a sejtés unióra-zárt formájáról Dwight Albert Duffus nevéhez fűződik (1985).

Kapcsolódó gondolatok, eredmények

A Frankl-sejtést főként két oldalról közelítik meg a mai matematikusok. Az nagyobb tábor tisztán kombinatorikai eszközökkel fogalmazza meg az állításait, tételeit és jellemzően ezek segítségével oldják is meg őket (Morris 2006, Lo Faro 1994, Roberts 1992, Gao és Yu 1998). A másik tábor képviselői pedig a hálóelméletet hívják segítségül (Reinhold 2000, Abe 2000, Poonen 1992). Amint látható mindkét hozzáállás további eredményeket szolgáltat manapság is. Az első csoportba tartozók igyekeznek az eredeti problémát plusz feltételekkel kiegészítve teljesen megoldani, újabb sejtéseket fogalmaznak meg még általánosabb esetekben. Például Roberts igazolta a sejtést „kicsi halmazrendszerekre”, vagyis ahol $n<4m-1$ (itt n jelöli a halmazrendszer elemszámát, míg m jelöli az alaphalmaz elemszámát). Később Gao és Yu igazolta „nagy halmazrendszerekre”, vagyis ahol teljesül a következő egyenlőtlenség: $n\geq 2^{m}-12\left({\frac {3}{2}}\right)^{\left[{\frac {m}{3}}\right]}-{\frac {1}{2}}{{m} \choose {3}}-{\frac {5}{3}}m+44,5$. Azóta 2007-ben pedig Czédli Gábor továbbfejlesztette Gao és Yu eredményét. Ennek megértéséhez definiáljunk néhány fogalmat!

Jelölje A az alaphalmazt, F pedig a halmazrendszert (n és m szerepe maradt). Legyen az alaphalmaz tetszőleges a eleme esetén s(a) az az érték, ahány F-beli halmaznak eleme a. A Frankl-sejtés tehát tetszőleges A és F esetén azt állítja, hogy létezik olyan a, hogy $n-2s(a)\leq 0$. Azt mondjuk, hogy F kielégíti az átlagolt Frankl-sejtést is, hogy igaz az, hogy a fenti kifejezést az alaphalmaz minden elemére összeadjuk még úgy is nempozitív az összeg (ebből nyilvánvalóan következik a Frankl-sejtés). Tehát Czédli erősebb állítása azt mondja ki, hogyha $n\geq 2^{m}-2^{\frac {m}{2}}$, akkor F kielégíti még az átlagolt Frankl-sejtést is. Vagyis erősebb az állítás, mert az átlagolt Frankl-sejtéssel dolgozik, és több halmazrendszerre vonatkozik adott alaphalmaz mellett.

Hivatkozások

• Abe, Tetsuya (2000). „Strong semimodular lattices and Frankl's conjecture”. Algebra Universalis 44 (3–4), 379–382. o. DOI:10.1007/s000120050195.  
• Bošnjak, Ivica; Marković, Peter (2008). „The 11-element case of Frankl's conjecture”. Electronic Journal of Combinatorics 15 (1), R88. o.  
• Dwight, Duffus (1985). „Open problem session”. Rival, I. Graphs and Order: 525, D. Reidel. 
• Lo Faro, Giovanni (1994). „Union-closed sets conjecture: improved bounds”. J. Combin. Math. Combin. Comput. 16, 97–102. o.  
• Morris, Robert (2006). „FC-families and improved bounds for Frankl's conjecture”. European Journal of Combinatorics 27 (2), 269–282. o. DOI:10.1016/j.ejc.2004.07.012.  
• Poonen, Bjorn (1992). „Union-closed families”. Journal of Combinatorial Theory, Series A 59 (2), 253–268. o. DOI:10.1016/0097-3165(92)90068-6.  
• Reinhold, Jürgen (2000). „Frankl's conjecture is true for lower semimodular lattices”. Graphs Combin. 16 (1), 115–116. o. DOI:10.1007/s003730050008.  
• Roberts, I. (1992. április 26.). „Tech. Rep. No. 2/92”, Kiadó: School Math. Stat., Curtin Univ. Tech., Perth.  
• Sarvate, D. G.; Renaud, J.-C. (1989). „On the union-closed sets conjecture”. Ars Combin. 27, 149–153. o.  

Kapcsolódó linkek

• Hálókkal a Frankl-sejtésről, Czédli Gábor, Maróti Miklós, Schmidt E. Tamás előadása
• Union-Closed Sets Conjecture, az Open Problem Garden.
• Union-Closed Sets Conjecture (1979). In Open Problems - Graph Theory and Combinatorics, D. B. West összefoglalója.
• Weisstein, Eric W.: Union-Closed Sets Conjecture (angol nyelven). Wolfram MathWorld