Théorème de Hall

En mathématiques, le théorème de Hall ou lemme des mariages est un résultat combinatoire qui donne une condition nécessaire et suffisante, sur une famille d'ensembles finis, pour qu'il soit possible de choisir des éléments distincts, un par ensemble. Il a été démontré par Philip Hall et a été à l'origine de la théorie du couplage dans les graphes.

On appelle système de représentants distincts d'une suite de n ensembles finis ${\displaystyle A_{1},\ldots ,A_{n}}$, toute suite de n éléments ${\displaystyle x_{1},\ldots ,x_{n}}$ distincts tels que pour tout ${\displaystyle k}$, ${\displaystyle x_{k}}$ appartienne à ${\displaystyle A_{k}}$.

La condition est clairement nécessaire. Parmi les diverses preuves qu'elle est suffisante, celle qui semble la plus naturelle^[1] est due à Easterfield^[2] et a été redécouverte par Halmos et Vaughan^[3].

Son nom folklorique de « lemme des mariages » est lié à l'interprétation suivante d'un système de représentants distincts : étant données n filles, si ${\displaystyle A_{k}}$ désigne l'ensemble des partis envisageables pour la k-ième, un système de représentants distincts correspond à un mariage collectif tenant compte de ces contraintes.

Un couplage parfait dans un graphe ayant un nombre pair 2n de sommets est un ensemble de n arêtes du graphe, deux-à-deux disjointes et telles que chaque sommet du graphe est incident à exactement une arête du couplage.

Théorème de Hall pour les graphes - Un graphe biparti G = (U,V;E) admet un couplage parfait si et seulement si pour tout sous-ensemble X de U (de V, respectivement), le nombre de sommets de V (de U, respectivement) adjacents à X est supérieur ou égal au cardinal de X.

Le théorème de Hall a été démontré par Philip Hall^[4] et a été à l'origine de la théorie du couplage dans les graphes^[1].

Ce résultat généralise le fait, déjà remarqué en 1914 par König, que les graphes bipartis réguliers admettent un couplage parfait. Par-ailleurs, le théorème de Tutte (en) généralise celui de Hall par une condition nécessaire et suffisante pour tous les graphes. Le théorème de Hall est en fait un cas particulier du théorème flot-max/coupe-min, dans les graphes constitués d'un graphe biparti G = (U,V;E) plus un sommet source et un sommet puits, la source étant reliée à tous les sommets de U, tandis que tous les sommets de V sont reliés au sommet puits.

Ce théorème de Hall n'est pas difficile à démontrer, il en existe au moins trois courtes démonstrations^[5],[6].

Nous disons qu'un graphe biparti ${\displaystyle G=(U,V;E)}$ respecte la condition des mariages si et seulement si pour tout sous-ensemble ${\displaystyle X}$ de ${\displaystyle U}$, ${\displaystyle |N_{G}(X)|\geq |X|}$ (avec ${\displaystyle |S|}$ la cardinalité de ${\displaystyle S}$ et ${\displaystyle N_{G}(S)}$ le nombre de voisins de ${\displaystyle S}$ dans le graphe ${\displaystyle G}$).

Soit ${\displaystyle G}$ un tel graphe biparti avec ${\displaystyle |U|=|V|}$ (condition évidemment nécessaire) et ${\displaystyle H}$ un sous-graphe de ${\displaystyle G}$ qui contient ${\displaystyle U}$, respecte la condition des mariages et tel qu'il n'existe pas d'arête ${\displaystyle (u,v)}$ de ${\displaystyle H}$ telle que ${\displaystyle H-uv}$ respecte aussi cette condition (${\displaystyle H}$ est arête-minimal pour cette condition).
Puisque ${\displaystyle H}$ respecte la condition des mariages, pour tout ${\displaystyle u\in U}$ nous avons ${\displaystyle |N_{H}(u)|\geq 1}$.
Nous allons donc montrer que les arêtes de ${\displaystyle H}$ forment un couplage parfait de ${\displaystyle G}$ en montrant que pour tout ${\displaystyle u\in U}$ nous avons ${\displaystyle |N_{H}(u)|=1}$.
Supposons que ${\displaystyle u\in U}$ a deux voisins distincts ${\displaystyle v_{1}}$ et ${\displaystyle v_{2}}$. Notons ${\displaystyle H_{1}=H-uv_{1}}$ et ${\displaystyle H_{2}=H-uv_{2}}$ Par minimalité de ${\displaystyle H}$, les graphes ${\displaystyle H_{1}}$ et ${\displaystyle H_{2}}$ ne respectent pas la condition des mariages. Autrement dit, il existe ${\displaystyle U_{1}\subseteq U}$ tel que ${\displaystyle |U_{1}|>|N_{H_{1}}(U_{1})|}$ et ${\displaystyle U_{2}\subseteq U}$ tel que ${\displaystyle |U_{2}|>|N_{H_{2}}(U_{2})|}$.

Supposons que ${\displaystyle u\notin U_{1}}$. Alors ${\displaystyle N_{H_{1}}(U_{1})=N_{H}(U_{1})}$, donc ${\displaystyle |U_{1}|>|N_{H}(U_{1})|}$, donc ${\displaystyle H}$ ne respecte pas la condition des mariages. Contradiction, donc ${\displaystyle u\in U_{1}}$. Similairement, ${\displaystyle u\in U_{2}}$.

Nous avons: ${\displaystyle {\begin{aligned}|N_{H}(U_{1}\cap U_{2}\backslash \{u\})|&\leq |N_{H}(U_{1}\backslash \{u\})\cap N_{H}(U_{2}\backslash \{u\})|\\&=|N_{H_{1}}(U_{1}\backslash \{u\})\cap N_{H_{2}}(U_{2}\backslash \{u\})|\\&\leq |N_{H_{1}}(U_{1})\cap N_{H_{2}}(U_{2})|\\&=|N_{H_{1}}(U_{1})|+|N_{H_{2}}(U_{2})|-|N_{H_{1}}(U_{1})\cup N_{H_{2}}(U_{2})|\end{aligned}}}$

Par définition de ${\displaystyle U_{1}}$ et ${\displaystyle U_{2}}$, ${\displaystyle |N_{H_{1}}(U_{1})|\leq |U_{1}|-1}$ et ${\displaystyle |N_{H_{2}}(U_{2})|\leq |U_{2}|-1}$.

D’autre part, ${\displaystyle N_{H_{1}}(U_{1})\cup \{v_{1}\}=N_{H}(U_{1})}$ et ${\displaystyle N_{H_{2}}(U_{2})\cup \{v_{2}\}=N_{H}(U_{2})}$. Puisque ${\displaystyle v_{2}\in N_{H_{1}}(u)\subseteq N_{H_{1}}(U_{1})}$ et ${\displaystyle v_{1}\in N_{H_{2}}(u)\subseteq N_{H_{2}}(U_{2})}$, nous avons: ${\displaystyle {\begin{aligned}N_{H_{1}}(U_{1})\cup N_{H_{2}}(U_{2})&=N_{H}(U_{1})\cup N_{H}(U_{2})\\&=N_{H}(U_{1}\cup U_{2})\end{aligned}}}$ ${\displaystyle H}$ respecte la condition des mariages donc ${\displaystyle |N_{H}(U_{1}\cup U_{2})|\geq |U_{1}\cup U_{2}|}$.

Nous avons donc: ${\displaystyle {\begin{aligned}|N_{H_{1}}(U_{1})|+|N_{H_{2}}(U_{2})|-|N_{H_{1}}(U_{1})\cup N_{H_{2}}(U_{2})|&\leq |U_{1}|-1+|U_{2}|-1-|U_{1}\cup U_{2}|\\&=|U_{1}\cap U_{2}|-2\\&=|U_{1}\cap U_{2}\backslash \{u\}|-1\end{aligned}}}$ D’où ${\displaystyle |N_{H}(U_{1}\cap U_{2}\backslash \{u\})|<|U_{1}\cap U_{2}\backslash \{u\}|}$, donc ${\displaystyle H}$ ne respecte pas la condition des mariages, ce qui est une contradiction avec l'hypothèse de départ.

Ainsi, tout ${\displaystyle u\in U}$ a exactement un voisin dans le sous-graphe ${\displaystyle H}$. Les arêtes de ${\displaystyle H}$ forment donc un couplage parfait de ${\displaystyle G}$.

Le problème qui consiste à savoir, étant donné un graphe biparti, s'il existe un couplage parfait peut-être résolu en temps polynomial. Mais même sans connaître ce fait, on sait qu'il appartient à la classe NP et d'après le théorème de Hall, à la classe co-NP puisqu'à l'aide d'un ensemble X violant la condition, on peut vérifier en temps polynomial que son voisinage N(X) est tel que |N(X)| < |X|, et donc convaincre que la réponse au problème de décision est négative.

• Théorème de Birkhoff-von Neumann
• Théorème de Dilworth
• Théorème flot-max/coupe-min
• Théorème de Kőnig (théorie des graphes)
• Théorème de Menger

• « Le lemme des mariages », sur Images des Maths, 20 mars 2011 (consulté le 23 juin 2014)

• Portail des mathématiques
• Portail de l'informatique théorique