Lemme des mariages
Théorème : Soit $F$ et $G$ deux ensembles finis, et soit $c$ une application de $G$ dans $\mathcal P(F)$,
l'ensemble des parties de $F$.
On suppose que pour toute partie $X$ de $G$, le nombre d'éléments de $\bigcup_{x\in X}c(x)$
est supérieur ou égal à celui de $X$.
Alors il existe une application injective $M$ de $G$ dans $F$ tel que $M(g)$ est élément de $c(g)$ pour tout $g\in G$.
Ce théorème s'appelle lemme des mariages en raison de l'interprétation suivante : $G$ désigne un ensemble de garçons, $F$ désigne un ensemble de filles, et $c$ est l'application qui à chaque garçon associe l'ensemble des filles qui lui plaisent. Alors, si pour chaque sous-groupe de garçons, il y a plus de filles qui plait à au moins l'un d'entre eux que le nombre de garçons de ce sous-groupe, on peut marier chaque garçon à une fille différente qui lui plait. Bien sûr, on peut échanger le rôle des filles et des garçons!
Recherche alphabétique
Recherche thématique