Demi-graphe
# 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.

## Définition

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

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. Le demi-graphe sur les entiers naturels (avec leur ordre habituel) a la propriété que chaque sommet $v_{j}$ a degré fini $j$. Les sommets de l'autre côté de la bipartition ont en revanche un degré infini.

## 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 $k$ sous-ensembles, le nombre de paires irrégulières est au moins proportionnel à $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.

## Couplage

Un demi-graphe a un couplage parfait unique. C'est facile à vérifier par récurrence : $u_{n}$ doit être lié à son seul voisin $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.

## 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.

