Famille intersectante

En mathématiques, une famille intersectante sur un ensemble E est une famille de parties de E deux à deux non disjointes, c'est-à-dire telle que l'intersection de deux quelconques de ces parties soit non vide.

Exemples
  • Si n < 2r, les parties de l'ensemble {1, 2, … , n} qui ont un cardinal supérieur ou égal à r forment une famille intersectante sur cet ensemble (et sur tout sur-ensemble).
  • Toute sous-famille d'une famille intersectante est intersectante.
  • Tout filtre est une famille intersectante.

Propriétés
  • Le cardinal d'une famille intersectante sur un ensemble à n éléments est trivialement[1] inférieur ou égal à 2n – 1.
  • Une famille intersectante à n éléments maximale (dont la cardinalité est 2n – 1) est une section commençante et l'ensemble des compléments des éléments de la famille forme une section finissante.
  • On appelle k-famille intersectante[1] une famille intersectante dont toutes les parties ont k éléments. Le théorème d'Erdős-Ko-Rado précise le cardinal maximum d'une k-famille intersectante, sur un ensemble à n éléments.
  • D'après un théorème de Daniel Kleitman[2], la réunion de m familles intersectantes, sur un ensemble à n éléments, contient au plus 2n – 2n – m parties[3].

Notes et références
(de) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en allemand intitulé « Schnittfamilie » (voir la liste des auteurs).
  1. Martin Aigner et Günter M. Ziegler, Raisonnements divins, p. 164
  2. (en) D. J. Kleitman, « Families of non-disjoint subsets », JCT, vol. 1,‎ , p. 153-155
  3. Démonstration dans (en) « Intersecting families of sets », sur le site Uniformly at Random
  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.