Conjecture des familles stables par unions

Si F est une famille d'ensembles stable par unions, la famille des ensembles complémentaires de ceux de F est stable par intersections, et un élément appartenant à au moins la moitié des ensembles de F appartiendra à au plus la moitié de leurs complémentaires. La forme duale de la conjecture (c'est d'ailleurs la forme sous laquelle elle fut énoncée initialement) est donc que, pour toute famille stable par intersections (contenant plus d'un ensemble), il existe un élément appartenant au plus à la moitié des ensembles de la famille.

Un treillis est un ensemble partiellement ordonné dans lequel chaque couple d'éléments admet une borne supérieure et une borne inférieure. L'ensemble des parties d'un ensemble S muni de l'inclusion forme un treillis où la borne supérieure est l'union et la borne inférieure l'intersection ; ce treillis (qui possède aussi une opération de complémentaire) peut être muni d'une structure d'algèbre de Boole ; on parle alors de treillis booléen. La conjecture de Frankl peut aussi se formuler en termes de théorie des treillis : elle affirme que dans tout treillis fini, il existe un élément x qui n'est pas la borne supérieure de deux éléments plus petits, et tel que le nombre d'éléments supérieurs ou égaux à x est au plus la moitié du nombre d'éléments du treillis (l'égalité n'étant atteinte que si le treillis est booléen). Abe a montré en 2000 l'équivalence des deux formulations ; on sait que la conjecture est vraie pour différentes classes naturelles de treillis (Abe 2000 ; Poonen 1992 ; Reinhold 2000).

La conjecture a été démontrée dans de nombreux cas particuliers ; ainsi, elle est vraie pour

• les familles ayant au plus 46 ensembles (Roberts et Simpson 2010) ;
• les familles dont l'union a au plus 11 éléments[1] ;
• les familles dont le plus petit ensemble a un ou deux éléments[2].

Péter Frankl a énoncé la conjecture en 1979 pour des familles stables par intersections, c'est pourquoi on l'appelle parfois la conjecture de Frankl. La forme correspondant aux familles stables par unions semble être due à Dwight Duffus (1985).

• (en) Abe, Tetsuya, « Strong semimodular lattices and Frankl's conjecture », Algebra Universalis, vol. 44, n^os 3–4,‎ 2000, p. 379–382 (DOI 10.1007/s000120050195)
• (en) Bošnjak, Ivica; Marković, Peter, « The 11-element case of Frankl's conjecture », Electronic Journal of Combinatorics, vol. 15, n^o 1,‎ 2008, R88 (lire en ligne)
• (en) D. Duffus et Ivan Rival (dir.), « Open problem session », Graphs and Order, D. Reidel,‎ 1985, p. 525
• (en) Lo Faro, Giovanni, « Union-closed sets conjecture: improved bounds », J. Combin. Math. Combin. Comput., vol. 16,‎ 1994, p. 97–102
• (en) Morris, Robert, « FC-families and improved bounds for Frankl's conjecture », European Journal of Combinatorics, vol. 27, n^o 2,‎ 2006, p. 269–282 (DOI 10.1016/j.ejc.2004.07.012)
• (en) Poonen, Bjorn, « Union-closed families », Journal of Combinatorial Theory, Series A, vol. 59, n^o 2,‎ 1992, p. 253–268 (DOI 10.1016/0097-3165(92)90068-6)
• (en) Reinhold, Jürgen, « Frankl's conjecture is true for lower semimodular lattices », Graphs Combin., vol. 16, n^o 1,‎ 2000, p. 115–116 (DOI 10.1007/s003730050008)
• (en) Ian Roberts et Jamie Simpson, « A note on the union-closed sets conjecture », Australas. J. Combin., vol. 47,‎ 2010, p. 265–267 (lire en ligne)
• (en) Sarvate, D. G.; Renaud, J.-C., « On the union-closed sets conjecture », Ars Combin., vol. 27,‎ 1989, p. 149–153

• (en) Frankl's union-closed sets conjecture, dans le Open Problem Garden.
• (en) Union-Closed Sets Conjecture (1979). Dans Open Problems - Graph Theory and Combinatorics, réunis par D. B. West.
• (en) Eric W. Weisstein, « Union-Closed Sets Conjecture », sur MathWorld