Conjecture des familles stables par unions

En mathématiques, et plus précisément en combinatoire, la conjecture des familles stables par unions est un problème d'énoncé élémentaire posé par Péter Frankl en 1979 et toujours ouvert. Une famille d'ensembles est dite stable par unions si l'union de deux ensembles quelconque de la famille est encore dans la famille. La conjecture affirme que pour toute famille finie d'ensembles finis (non vides), stable par unions, il existe un élément appartenant à au moins la moitié des ensembles de la famille.

Formes équivalentes

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).

Résultats partiels

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].

Historique

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).

Notes

↑ Bošnjak et Marković (2008), améliorant des bornes précédentes dues à Morris (2006) et Lo Faro (1994)
↑ Sarvate et Renaud (1989). En fait, s'il existe un ensemble S de la famille ayant un ou deux éléments, un des éléments de S appartient à au moins la moitié des éléments de la famille, mais cette propriété ne se généralise pas à des ensembles à trois éléments, comme l'ont montré des contre-exemples construits par Sarvate, Renaud, et Ronald Graham.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Union-closed sets conjecture » (voir la liste des auteurs).

(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

Liens externes

(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

Portail des mathématiques

[1] Bošnjak et Marković (2008), améliorant des bornes précédentes dues à Morris (2006) et Lo Faro (1994)

[2] Sarvate et Renaud (1989). En fait, s'il existe un ensemble S de la famille ayant un ou deux éléments, un des éléments de S appartient à au moins la moitié des éléments de la famille, mais cette propriété ne se généralise pas à des ensembles à trois éléments, comme l'ont montré des contre-exemples construits par Sarvate, Renaud, et Ronald Graham.

[1]

[2]