Graphe distance-unité

En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe pouvant être représenté par un ensemble de points du plan euclidien en reliant par une arête uniquement des paires de points distants d'une unité ; s'il existe une représentation où toutes les paires de points à distance 1 sont reliées, on parle de graphe distance-unité strict^[1].

Les arêtes peuvent se croiser, si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. Si une représentation est sans croisement entre les arêtes, toutes de longueur 1, alors le graphe est qualifié de graphe-allumettes.

Exemples

Les graphes chaine, les graphes grille, les graphes cycle, les graphes étoile.
Les graphes prisme, dont le graphe cube, et les graphes hypercube, dont le graphe tesseract.
- Graphe prisme triangulaire.
- Graphe cube, à la fois graphe prisme et graphe hypercube.
- Graphe prisme pentagonal.
- Graphe hypercube Q₄ ou graphe tesseract, à 16 sommets et 32 arêtes.

Le graphe de Petersen ainsi que ceux de Moser, de Harborth et de Golomb.
- Graphe de Petersen.
- Graphe de Moser.
- Graphe de Harborth, graphe-allumettes.
- Graphe de Golomb.
à 4 sommets : le graphe diamant, le graphe griffe, le graphe patte.
à 5 sommets : le graphe papillon, le graphe taureau, le graphe criquet, le graphe fléchette, le graphe cerf-volant, le graphe fourche, le graphe maison, le graphe bannière.
à 6 sommets : le graphe poisson, le graphe croix, le graphe mite.
à 7 sommets : le graphe roue W₇ (c'est le seul graphe roue à être distance-unité), le graphe longhorn.

Dénombrements

Classement par nombre de sommets

Le nombre $a(n)$ de graphes distance-unités connexes à $n$ sommets à isomorphisme près est donné par la suite A059103 de l'OEIS^[2].


$n$	1	2	3	4	5	6
$a(n)$	1	1	2	5	13	51

Nombre maximal d'arêtes

Le graphe roue W₇ est un graphe distance-unité à 7 sommets ayant un maximum d'arêtes (12).

Paul Erdős posa le problème suivant en 1946 : quel est le nombre maximal $g(n)$ d'occurrences d'une distance donnée (pouvant être prise égale à 1) déterminée par $n$ points dans le plan ?^[3] En d'autres termes quel est le nombre maximal d'arêtes d'un graphe distance-unité à $n$ sommets ?

Les valeurs de $g(n)$ sont connues jusqu'à $n=14$ (suite A186705 de l'OEIS) :

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$g(n)$	0	1	3	5	7	9	12	14	18	20	23	27	30	33

Jusqu'à $n=8$ , les graphes correspondants peuvent être tracés dans le réseau hexagonal, mais ce n'est plus le cas ensuite^[4].

Le graphe hypercube fournit un minorant de $g(n)$ proportionnel à $n\ln n$ .

En considérant des points dans une grille carrée avec un espacement soigneusement choisi, Erdős a trouvé un meilleur minorant égal à : $n^{1+c/\ln \ln n}$ pour une constante $c$ ^[3], et a offert 500 $ pour une preuve montrant que le nombre $g(n)$ peut également être majoré par une fonction de cette forme^[5].

Ce problème est très lié au théorème de Szemerédi-Trotter.

Application au nombre chromatique du plan

Le problème de Hadwiger-Nelson, introduit en 1944 par Hugo Hadwiger et Edward Nelson, concerne le nombre minimal de couleurs qu'il faut pour colorier le plan de façon que deux points à une distance de 1 ne soient jamais de la même couleur^[6]. Il peut être formalisé en théorie des graphes de la façon suivante : quel est le nombre chromatique maximal d'un graphe distance-unité ? Le problème est toujours ouvert mais le graphe de Golomb, avec son nombre chromatique égal à 4, fournit une borne inférieure^[7]. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser^[8]. Cependant, en avril 2018, des graphes de nombre chromatique 5 (comportant plusieurs milliers de sommets, le plus petit a 1581 sommets) ont été découverts par Aubrey de Grey et contrôlés par ordinateur^[9]^,^[10].

Généralisation

La notion de dimension d'un graphe reprend l'idée d'un graphe tracé avec des arêtes de longueur 1, mais ne se restreint pas au plan.

Références

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

↑ (en) Severino Gervacio, Yvette Lim, Hiroshi Maehara, « Planar unit-distance graphs having planar unit-distance complement », Discrete Mathematics, vol. 308, n^o 10,‎ 2008, p. 1973–1984 (lire en ligne)
↑ (en) « Matchstick Graph », sur Mathworld
1 2 (en) Paul Erdős, « On sets of distances of n points », Amer. Math. Monthly, vol. 53,‎ 1946, p. 248-250 (lire en ligne)
↑ Jean-Paul Delahaye, « Les graphes-allumettes », Pour la Science, n^o 445,‎ novembre 2014, p. 112 (lire en ligne )
↑ (en) Paul Erdős, Some of my favourite unsolved problems", in Baker, A.; Bollobás, B.; Hajnal, A. (eds.), A tribute to Paul Erdős,, Cambridge University Press, 1990 (ISBN 0-521-38101-0), p. 475
↑ (en) Joseph O'Rourke, « Problem 57: Chromatic Number of the Plane », sur The Open Problems Project.
↑ (en) A. Soifer, The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, New York, Springer, 2008, p. 19-20.
↑ (en) L. Moser et W. Moser, « Problem 10 », dans Canad. Math. Bull., n^o 4, 1961, p. 187-189.
↑ (en) Aubrey de Grey, The chromatic number of the plane is at least 5.
↑ David Madore, Le progrès récent sur le problème de Hadwiger-Nelson.

Voir aussi

Graphe-allumettes

Portail des mathématiques
Portail de l'informatique théorique

[1] (en) Severino Gervacio, Yvette Lim, Hiroshi Maehara, « Planar unit-distance graphs having planar unit-distance complement », Discrete Mathematics, vol. 308, n^o 10,‎ 2008, p. 1973–1984 (lire en ligne)

[2] (en) « Matchstick Graph », sur Mathworld

[:0-3] 1 2 (en) Paul Erdős, « On sets of distances of n points », Amer. Math. Monthly, vol. 53,‎ 1946, p. 248-250 (lire en ligne)

[4] Jean-Paul Delahaye, « Les graphes-allumettes », Pour la Science, n^o 445,‎ novembre 2014, p. 112 (lire en ligne )

[5] (en) Paul Erdős, Some of my favourite unsolved problems", in Baker, A.; Bollobás, B.; Hajnal, A. (eds.), A tribute to Paul Erdős,, Cambridge University Press, 1990 (ISBN 0-521-38101-0), p. 475

[6] (en) Joseph O'Rourke, « Problem 57: Chromatic Number of the Plane », sur The Open Problems Project.

[7] (en) A. Soifer, The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, New York, Springer, 2008, p. 19-20.

[8] (en) L. Moser et W. Moser, « Problem 10 », dans Canad. Math. Bull., n^o 4, 1961, p. 187-189.

[9] (en) Aubrey de Grey, The chromatic number of the plane is at least 5.

[10] David Madore, Le progrès récent sur le problème de Hadwiger-Nelson.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]