lemme des mariages

problème des mariages
théorème de Hall
théorème des mariages

COMBINATOIRE

Le lemme des mariages ou théorème de Hall, est un énoncé de théorie des ensembles formulé en 1935 par le mathématicien britannique Philip Hall (1904 – 1982).
Pour l’interprétation . matrimoniale, on se place dans une société où n’existe que la monogamie strictement hétérosexuée. De plus, dans cette société, les mariages sont décidés par un ordinateur central de façon centralisée sur la base d’informations qui lui sont données : chaque fille en âge de se marier donne la liste des garçons qui lui conviennent (ou l’inverse !). L’ordinateur associe à chaque fille le nom de l’un des garçons de sa liste. Chaque fille est mariée à un seul garçon, chaque garçon à une seule fille. Et personne ne doit rester célibataire.
On démontre facilement que la condition suivante, dite condition de mariage, est nécessaire. La réunion des listes d’un groupe quelconque de filles contient au moins autant de noms de garçons différents qu’il y a de filles dans le groupe.
Le lemme des Mariages énonce que cette condition est suffisante.
Lemme des mariages : Si la condition de mariage est satisfaite, alors il est possible de marier toutes les filles, chacune à l’un des garçons de sa liste.

L’énoncé, en vocabulaire de théorie des ensembles :
Lemme des mariages : Considérons deux ensembles finis F, G, et une application c de F dans l’ensemble des parties de G. Pour toute partie F0 de F, on note c(F0) la réunion des ensembles c(f) lorsque f parcourt F0. Supposons que l’hypothèse suivante est réalisée :
pour chaque partie F0 de F, l’ensemble c(0) contient au moins autant d’éléments que F0.
Alors il existe une application m de F dans G, injective et telle que, pour tout f dans F, m(f) appartient à c(f).

Ce théorème peut aussi être énoncé dans le cadre de la théorie des graphes.