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