Fackligt slutna gissningar

Olöst problem i matematik :

Om några två mängder i någon ändlig familj av mängder har en förening som också tillhör familjen, måste något element tillhöra minst hälften av mängderna i familjen?

(fler olösta problem i matematik)

fackligt slutna uppsättningar är ett öppet problem inom kombinatorik som Péter Frankl ställde upp 1979. En familj av uppsättningar sägs vara fackligt slutna om föreningen av två uppsättningar från familjen tillhör familjen. Gissningen säger:

För varje ändlig fackligt sluten familj av mängder, förutom familjen som bara innehåller den tomma mängden , finns det ett element som tillhör minst hälften av mängderna i familjen.

Professor Timothy Gowers har kallat detta " ett av de mest kända öppna problemen inom kombinatorik " och har sagt att gissningarna " känns som om det borde vara lätt (och som ett resultat har lockat många falska bevis genom åren). ett bra sätt att förstå varför det inte är lätt är att spendera en eftermiddag på att försöka bevisa det. Det där smarta medelvärdesargumentet du hade i åtanke fungerar inte ... "

Exempel

Familjen av uppsättningar

$$\varnothing ,\{1\},\{1,2\},\ {2,3,4\},\{1,2,3,4\}$$

består av fem olika set och är förbundsstängd. Elementet $1$ ingår i tre av de fem uppsättningarna (och så är element $2$ ), så gissningen gäller i detta fall.

Grundläggande resultat

Det är lätt att visa att om en fackligt sluten familj innehåller en singleton $\{a\}$ (som i exemplet ovan), så måste elementet $a$ förekomma i minst hälften av familjens uppsättningar.

Om det finns ett motexempel till gissningen, så finns det också ett motexempel som endast består av ändliga mängder. Därför kommer vi, utan förlust av generalitet, att anta att alla mängder i den givna fackligt slutna familjen är ändliga.

Givet en ändlig icke-tom mängd ${\displaystyle U} är$ effektmängden $P(U)$ bestående av alla delmängder av $U$ unionssluten . Varje element i $U$ ingår i exakt hälften av delmängderna av $U$ . Därför kan vi i allmänhet inte begära ett element som finns i mer än hälften av familjens uppsättningar: gränsen för gissningen är skarp.

Likvärdiga former

Korsningsformulering

Den fackligt slutna uppsättningsförmodan är sann om och endast om ett uppsättningssystem $X$ som är korsningsslutet innehåller ett element av $U(X)$ i högst hälften av uppsättningarna av $X$ , där $U(X)$ är universummängden, dvs föreningen av alla medlemmar i systemet $X$ .

Följande fakta visar likvärdigheten.

För det första visar vi att ett uppsättningssystem är fackligt stängt om och endast om dess komplement är korsningsstängt.

Lemma 1. Om $X$ är en fackligt sluten familj av mängder med universum $U(X)$ stängs familjen av komplementmängder till mängder i ${\displaystyle X} under$ genomskärning.

Bevis. Vi definierar komplementet till uppsättningssystemet $X$ som $X^{c}:=\{U(X)-S: S\in X\}$ .

Låt $X_{1}$ , $X_{2}$ vara godtyckliga mängder i $X$ och så $U(X)-X_ {1}$ och $U(X)-X_{2}$ är båda i $X^{c}$ . Eftersom $X$ är fackligt sluten, är $X_{1}\cup X_{2}=X_{3}$ i $X$ , och därför komplementet till $X_{3}$ , $U(X)-X_{3}$ är i $X^{c}$ , elementen i varken $X_{1}$ eller $X_{2}$ .

Och detta är exakt skärningspunkten mellan komplementen av $X_{1}$ och $X_{2}$ , $(U(X)-X_{1})\cap (U(X)-X_{2})$ . Därför $X$ union-stängd om och endast om komplementet av $X$ , $X^{c}$ är skärningspunkten stängd.

För det andra visar vi att om ett mängdsystem innehåller ett element i minst hälften av mängderna, så har dess komplement ett element i högst hälften.

Lemma 2. Ett setsystem $X$ innehåller ett element i hälften av sina mängder om och endast om komplementmängdsystemet ${\displaystyle X} ,$ X $\displaystyle X^{*}}$ innehåller ett element i högst hälften av dess uppsättningar. Bevis. Trivial.

Därför, om $X$ är en fackligt sluten familj av uppsättningar, är familjen av komplementuppsättningar till mängder i $X$ relativt universum $U(X)$ , stängd under skärningspunkt, och ett element som tillhör minst hälften av uppsättningarna av $X$ tillhör högst hälften av komplementmängderna. Således är en likvärdig form av gissningen (den form som den ursprungligen angavs) att det för varje korsningssluten familj av mängder som innehåller mer än en mängd, det finns ett element som hör till högst hälften av mängderna i familjen.

Gitterformulering

Även om det anges ovan i termer av familjer av uppsättningar, har Frankls gissning också formulerats och studerats som en fråga inom gitterteorin . Ett gitter är en partiellt ordnad mängd där det för två element x och y finns ett unikt största element som är mindre än eller lika med dem båda (mötet mellan x och y ) och ett unikt minsta element större än eller lika med dem båda ( sammanfogningen av x och y ). Familjen av alla delmängder av en mängd S , ordnade efter inkludering av mängder, bildar ett gitter i vilket mötet representeras av den mängd-teoretiska skärningspunkten och sammanfogningen representeras av den mängd-teoretiska unionen; ett gitter som bildas på detta sätt kallas ett booleskt gitter . Den gitterteoretiska versionen av Frankls gissning är att det i vilket ändligt gitter som helst existerar ett element x som inte är sammanfogningen av två mindre element, och så att antalet element större än eller lika med x totalt är högst halva gittret, med jämlikhet endast om gittret är ett booleskt gitter. Som Abe (2000) visar är detta uttalande om gitter ekvivalent med Frankl-förmodan för fackligt slutna uppsättningar: varje gitter kan översättas till en fackligt sluten uppsättningsfamilj, och varje fackligt sluten uppsättningsfamilj kan översättas till ett gitter, så att sanningen i Frankl-förmodan för det översatta objektet antyder sanningen i antagandet för det ursprungliga objektet. Denna gitterteoretiska version av gissningen är känd för att vara sann för flera naturliga underklasser av gitter men förblir öppen i det allmänna fallet.

Grafteoretisk formulering

En annan likvärdig formulering av förmodan om fackligt slutna uppsättningar använder grafteori . I en oriktad graf är en oberoende uppsättning en uppsättning av hörn varav inte två ligger intill varandra; en oberoende mängd är maximal om den inte är en delmängd av en större oberoende mängd. I vilken graf som helst måste de "tunga" hörnen som förekommer i mer än hälften av de maximala oberoende uppsättningarna själva bilda en oberoende uppsättning. Så, om grafen inte är tom, finns det alltid minst en icke-tung vertex, en vertex som visas i högst hälften av de maximala oberoende uppsättningarna. Grafformuleringen av gissningarna med fackföreningsslutna uppsättningar säger att varje finit icke-tom graf innehåller två intilliggande icke-tunga hörn. Det är automatiskt sant när grafen innehåller en udda cykel, eftersom den oberoende uppsättningen av alla tunga hörn inte kan täcka alla kanter av cykeln. Därför är det mer intressanta fallet av gissningen för tvådelade grafer , som inte har några udda cykler. En annan likvärdig formulering av gissningen är att det i varje tvådelad graf finns två hörn, en på varje sida om bipartitionen, så att var och en av dessa två hörn hör till högst hälften av grafens maximala oberoende uppsättningar. Denna gissning är känd för att hålla för kordala tvådelade grafer , tvådelade serier-parallella grafer och tvådelade grafer av maximal grad tre.

Delvis resultat

Gissningen har bevisats för många specialfall av fackligt slutna familjer. I synnerhet är det känt att stämma för

• familjer på högst 46 uppsättningar.
• familjer av uppsättningar vars förening har högst 11 element.
• familjer av mängder där den minsta mängden har ett eller två element.
• familjer av minst $({\tfrac {1}{2}}-\varepsilon )2^{n}$ delmängder av en $n$ -elementuppsättning, för någon konstant ${\displaystyle \varepsilon >0} ,$ enligt ett opublicerat förtryck.

I november 2022 publicerades ett förtryck med krav på bevis på följande påstående:

För varje fackligt sluten familj, förutom familjen som bara innehåller den tomma mängden, finns det ett element som tillhör minst en bråkdel av 0,01 av mängderna i familjen.

Beviset använde probabilistiska och entropimetoder för att erhålla en sådan gräns. En gissning i denna artikel antydde en möjlig förbättring till en nedre gränsfraktion på $(3-{\sqrt {5}})/2\approx 0,38197$ . Själva gissningen med fackföreningsslutna uppsättningar motsvarar bråkdelen $0,5$ .

Några dagar senare postades tre förtryck som fastställde den nedre gränsfraktionen av $(3-{\sqrt {5}})/2$ . Dessa följdes kort av två andra förtryck som ökade den nedre gränsen till $0,38234$ .

Historia

Péter Frankl angav gissningen i termer av korsningsstängda uppsättningsfamiljer 1979, och därför tillskrivs gissningen vanligtvis honom och kallas ibland Frankl- förmodan . Den tidigaste publiceringen av den fackligt slutna versionen av gissningarna verkar vara av Duffus (1985) . En historia av arbetet med gissningarna fram till 2013 publicerades av Bruhn & Schaudt (2015) .

Anteckningar

•   Abe, Tetsuya (2000). "Starka semimodulära gitter och Frankls gissning". Algebra Universalis . 44 (3–4): 379–382. doi : 10.1007/s000120050195 . S2CID 120741780 .
• Alweiss, Ryan; Huang, Brice; Sellke, Mark (2022-11-21). "Förbättrad nedre gräns för antagandet om unionstängda set". arXiv : 2211.11731 [ math.CO ].
• Bošnjak, Ivica; Marković, Peter (2008). "The 11-element case of Frankls conjecture" . Electronic Journal of Combinatorics . 15 (1): R88. doi : 10.37236/812 .
•    Bruhn, Henning; Charbit, Pierre; Schaudt, Oliver; Telle, Jan Arne (2015). "Grafformeringen av de fackligt slutna uppsättningarnas gissningar". European Journal of Combinatorics . 43 : 210–219. arXiv : 1212.4175 . doi : 10.1016/j.ejc.2014.08.030 . MR 3266293 . S2CID 2373192 .
• Bruhn, Henning; Schaudt, Oliver (2015-11-01). "The Journey of the Union-Closed Sets gissningar" . Grafer och kombinatorik . 31 (6): 2043–2074. arXiv : 1309.3297 . doi : 10.1007/s00373-014-1515-0 .
• Chase, Zachary; Lovett, Shachar (2022-11-21). "Ungefärlig fackligt sluten gissning". arXiv : 2211.11689 [ math.CO ].
• Cambie, Stijn (2022-12-23). "Bättre gränser för de fackligt slutna gissningarna med entropimetoden". arXiv : 2212.12500 [ math.CO ].
• Duffus, D. (1985). Rival, I. (red.). Öppna problemsession . Grafer och ordning. D. Reidel. sid. 525.
• Gilmer, Justin (2022-11-16). "En konstant nedre gräns för de fackligt slutna gissningarna". arXiv : 2211.09055 [ math.CO ].
• Karpas, Ilan (2017). "Två resultat om fackligt slutna familjer". arXiv : 1708.01434 [ math.CO ].
•   Lo Faro, Giovanni (1994). "Fackligt slutna gissningar: förbättrade gränser". J. Combin. Matematik. Kombinera. Comput . 16 : 97–102. MR 1301213 .
•    Morris, Robert (2006). "FC-familjer och förbättrade gränser för Frankls gissningar". European Journal of Combinatorics . 27 (2): 269–282. arXiv : math/0702348 . doi : 10.1016/j.ejc.2004.07.012 . MR 2199779 . S2CID 17633023 .
•   Poonen, Björn (1992). "Fackligt slutna familjer" . Journal of Combinatorial Theory . Serie A. 59 (2): 253–268. doi : 10.1016/0097-3165(92)90068-6 . MR 1149898 .
•   Reinhold, Jürgen (2000). "Frankls gissning är sann för lägre semimodulära gitter". Grafer och kombinatorik . 16 (1): 115–116. doi : 10.1007/s003730050008 . S2CID 12660895 .
• Roberts, Ian; Simpson, Jamie (2010). "En anteckning om förmodan om fackligt slutna uppsättningar" (PDF) . Australas. J. Combin . 47 : 265-267.
•   Sarvate, GD; Renaud, J.-C. (1989). "På de fackligt slutna gissningarna". Ars Combin . 27 : 149–153. MR 0989460 .
• Sawin, Will (2022-11-21). "En förbättrad nedre gräns för den fackligt slutna uppsättningens gissning". arXiv : 2211.11504 [ math.CO ].
• Yu, Lei (2022-12-01). "Dimensionsfria gränser för antaganden om fackliga slutna uppsättningar". arXiv : 2212.00658 [ math.CO ].

externa länkar

• Frankls fackligt slutna gissningar, den öppna problemträdgården.
• Union-Closed Sets Conjecture (1979) . In Open Problems – Graph Theory and Combinatorics , samlad av DB West.