Demi-graphe

En théorie des graphes, une branche des mathématiques, un demi-graphe (en anglais half graph) est un type particulier de graphe biparti. Ces graphes sont appelés demi-graphes car ils possèdent environ la moitié des arêtes d'un graphe biparti complet sur les mêmes sommets. Leur nom a été donné à ces graphes par Paul Erdős et András Hajnal^[1].

Un demi-graphe à 14 sommets

Définition

Pour définir un demi-graphe sur ${\displaystyle 2n}$ sommets notés ${\displaystyle u_{1},\dots ,u_{n}}$ et ${\displaystyle v_{1},\dots ,v_{n}}$, on relie ${\displaystyle u_{i}}$ à ${\displaystyle v_{j}}$ par une arête chaque fois que ${\displaystyle i\leq j}$^[1].

La même notion peut aussi être défini, et de la même manière, pour des graphes infinis sur deux copies d'un ensemble ordonné de sommets^[1]. Le demi-graphe sur les entiers naturels (avec leur ordre habituel) a la propriété que chaque sommet ${\displaystyle v_{j}}$ a degré fini ${\displaystyle j}$. Les sommets de l'autre côté de la bipartition ont en revanche un degré infini^[2].

Irrégularité

Une des applications des demi-graphes est dans le lemme de régularité de Szemerédi, qui stipule que les sommets de tout graphe peuvent être partitionnés en un nombre constant de sous-ensembles de même taille, de sorte que la plupart des paires de sous-ensembles sont régulières (les arêtes reliant une paire se comportent d'une certaine manière comme un graphe aléatoire d'une densité particulière). Si le demi-graphe est partitionné de cette manière en ${\displaystyle k}$ sous-ensembles, le nombre de paires irrégulières est au moins proportionnel à ${\displaystyle k}$. Par conséquent, il n'est pas possible de renforcer le lemme de régularité pour montrer l'existence d'une partition pour laquelle toutes les paires sont régulières^[3].

Couplage

Un demi-graphe a un couplage parfait unique. C'est facile à vérifier par récurrence : ${\displaystyle u_{n}}$ doit être lié à son seul voisin ${\displaystyle v_{n}}$ et les sommets restants forment un autre demi-graphe. Réciproquement, tout graphe bipartite avec un couplage parfait unique est un sous-graphe d'un demi-graphe^[4].

Graphes à nombre chromatique non dénombrable

Si le nombre chromatique d'un graphe est non dénombrable, alors le graphe contient nécessairement comme sous-graphe un demi-graphe sur les entiers naturels. Ce demi-graphe, à son tour, contient tout graphe biparti complet dans lequel un côté de la bipartition est fini et l'autre côté est infini dénombrable^[5].