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

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$ ^[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 $v_{j}$ a degré fini $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 $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^[3].

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^[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].

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Half graph » (voir la liste des auteurs).

↑ ^{a b et c} Paul Erdős, « Some combinatorial, geometric and set theoretic problems in measure theory », dans D. Kölzow et D. Maharam-Stone, Measure Theory Oberwolfach 1983, Springer, coll. « Lecture Notes in Mathematics » (n^o 1089), 1984, p. 321-327
↑ Jaroslav Nešetřil et Saharon Shelah, « On the order of countable graphs », European Journal of Combinatorics, vol. 24, n^o 6,‎ 2003, p. 649–663 (DOI 10.1016/S0195-6698(03)00064-7, MR 1995579, arXiv math/0404319)
↑ David Conlon et Jacob Fox, « Bounds for graph regularity and removal lemmas », Geometric and Functional Analysis, vol. 22, n^o 5,‎ 2012, p. 1191–1256 (DOI 10.1007/s00039-012-0171-x, MR 2989432, arXiv 1107.4829)
↑ C. D. Godsil, « Inverses of trees », Combinatorica, vol. 5, n^o 1,‎ 1985, p. 33–39 (DOI 10.1007/bf02579440). — En particulier Lemme 2.1.
↑ Paul Erdős et András Hajnal, « Chromatic number of finite and infinite graphs and hypergraphs », Discrete Mathematics, vol. 53,‎ 1985, p. 281–285 (DOI 10.1016/0012-365X(85)90148-7, MR 786496, lire en ligne). — Le résultat selon lequel les graphes de nombre chromatique non dénombrable contiennent un demi-graphe infini est attribué, dans cet article, à Hajnal, et cité dans un article de 1973 des mêmes auteurs avec Shelah ; toutefois, cet article n'énonce le résultat que sous la forme plus faible selon laquelle les graphes de nombre chromatique non dénombrable contiennent des graphes bipartite complets où un côté est fini et l'autre côté est infini.

Article lié

Demi-hypercube (graphe)

Portail des mathématiques

[e-1] {a b et c} Paul Erdős, « Some combinatorial, geometric and set theoretic problems in measure theory », dans D. Kölzow et D. Maharam-Stone, Measure Theory Oberwolfach 1983, Springer, coll. « Lecture Notes in Mathematics » (n^o 1089), 1984, p. 321-327

[ns-2] Jaroslav Nešetřil et Saharon Shelah, « On the order of countable graphs », European Journal of Combinatorics, vol. 24, n^o 6,‎ 2003, p. 649–663 (DOI 10.1016/S0195-6698(03)00064-7, MR 1995579, arXiv math/0404319)

[cf-3] David Conlon et Jacob Fox, « Bounds for graph regularity and removal lemmas », Geometric and Functional Analysis, vol. 22, n^o 5,‎ 2012, p. 1191–1256 (DOI 10.1007/s00039-012-0171-x, MR 2989432, arXiv 1107.4829)

[g-4] C. D. Godsil, « Inverses of trees », Combinatorica, vol. 5, n^o 1,‎ 1985, p. 33–39 (DOI 10.1007/bf02579440). — En particulier Lemme 2.1.

[eh-5] Paul Erdős et András Hajnal, « Chromatic number of finite and infinite graphs and hypergraphs », Discrete Mathematics, vol. 53,‎ 1985, p. 281–285 (DOI 10.1016/0012-365X(85)90148-7, MR 786496, lire en ligne). — Le résultat selon lequel les graphes de nombre chromatique non dénombrable contiennent un demi-graphe infini est attribué, dans cet article, à Hajnal, et cité dans un article de 1973 des mêmes auteurs avec Shelah ; toutefois, cet article n'énonce le résultat que sous la forme plus faible selon laquelle les graphes de nombre chromatique non dénombrable contiennent des graphes bipartite complets où un côté est fini et l'autre côté est infini.

[1]

[2]

[3]

[4]

[5]