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  sommets notés  et , on relie  à  par une arête chaque fois que .

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  a degré fini . 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  sous-ensembles, le nombre de paires irrégulières est au moins proportionnel à . 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 :  doit être lié à son seul voisin  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.

Notes et références

Article lié 
 Demi-hypercube (graphe)

Famille de graphes
Combinatoire