Demi-graphe

Un demi-graphe à 14 sommets

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 HajnalModèle:Références multiples.

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\le j$Modèle:Références multiples.

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 sommetsModèle:Références multiples. 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é infiniModèle:Références multiples.

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èresModèle:Références multiples.

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-grapheModèle:Références multiples.

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énombrableModèle:Références multiples.

Article lié

• Demi-hypercube (graphe)