septembre | 2014 | Quentin Fortier

Pour inaugurer ce magnifique blog, je vais parler du problème suivant (Unit distance problem), posé par Erdős en 1946:

On place $n$ points distincts dans le plan. Quel est le nombre maximum de couples de points à distance un?

Appelons $u(n)$ ce nombre.

Il s’agit de l’un des problèmes les plus connus en géométrie discrète, et, comme beaucoup de problèmes dans ce domaine, la difficulté de sa résolution est en contraste avec la simplicité de son énoncé.

On peut l’énoncer en terme de théorie des graphes: en mettant une arête entre chaque couple de points à distance un, on obtient un graphe. On appelle graphe distance-unité un graphe qui peut être obtenu de cette façon là. La question devient: quel est le nombre maximum d’arêtes d’un graphe distance-unité?

Par exemple le graphe de Moser (le plus petit graphe distance-unité qui n’est pas 3-coloriable, qui montre donc que le nombre chromatique du plan est au moins 4) et le graphe de Petersen sont distance-unité.

150px-Petersen_graph,_unit_distance.svg — Graphe de Petersen

On peut encore formuler le problème de façon légèrement différente: si on trace un cercle de rayon 1 autour de chaque point, on cherche alors à maximiser la somme, sur tout point $p$ , du nombre de cercles contenant $p$ .

On peut calculer les valeurs exactes des premiers $u(n)$ et les graphes distance-unité correspondant:

valeur

Bien évidemment, $u(n) \leq \binom{n}{2}$ .

De plus, en considérant une grille, on s’aperçoit que $u(n) \geq \Theta(n)$ . Dans cet exemple, 1 est aussi la distance la plus courte réalisée parmi toutes les distances possibles entre les points. On ne peut pas espérer mieux que ${\Theta(n)}$ dans ce cas car le graphe est alors planaire (facile à vérifier) et le nombre d’arêtes d’un graphe planaire est au plus $3n - 6$ .

Bornes supérieures

La première borne supérieure pour $u(n)$ , proposé par Erdős, est $O(n^{3/2})$ , i.e qu’un sommet ait en moyenne au plus $O(\sqrt{n})$ voisins. Montrons $u(n) \leq 2 n^{3/2}$ par récurrence sur $n$ :

Supposons que notre graphe distance-unité $G$ à $n$ sommets ait $m$ arêtes. Si il existe un sommet de degré au plus $\sqrt{n}$ alors en enlevant ce sommet on obtient un graphe à $n-1$ sommets et au moins ${m - \sqrt{n}}$ arêtes. On en déduit par récurrence que ${m - \sqrt{n} \leq 2(n-1)\sqrt{n-1} \leq 2(n-1)\sqrt{n}}$ et donc que $m \leq 2n^{3/2}$ .

Si maintenant tous les sommets ont un degré supérieur à $\sqrt{n}$ , choisissons-en un $p$ . Considérons un ensemble $P$ de $\sqrt{n}$ voisins $p$ . Combien d’arêtes enlève t-on lorsqu’on enlève $P$ du graphe? Déjà les $\sqrt{n}$ arêtes entre $p$ et les éléments de $P$ . Mais, un sommet $v$ différent de $p$ est contenu dans au plus deux cercles-unité issus des points de $P$ (pour s’en convaincre, regarder la figure ci-dessous).

Donc en enlevant $P$ on enlève au plus 2 $n$ arêtes, i.e le nouveau graphe a $n-\sqrt{n}$ sommets et au moins $m-2n-\sqrt{n}$ arêtes. Ainsi ${m-2n-\sqrt{n} \leq 2(n- \sqrt{n}) \sqrt{n- \sqrt{n}}} \leq 2(n \sqrt{n} - n)(1-\frac{1}{2 \sqrt{n}})$ , en utilisant $(1+x)^{\alpha} \leq 1 + \alpha x$ .

D’où $m \leq 2n \sqrt{n} - 2n - n + \sqrt{n} + 2n + \sqrt{n} = 2n \sqrt{n} - n + 2 \sqrt{n} \leq 2n \sqrt{n}$ dès que $n \geq 4$ .

Pourquoi montrer $u(n) \leq 2 n^{3/2}$ et non pas $u(n) \leq n^{3/2}$ ? Le problème est que dans le deuxième cas de la récurrence on enlève $2n$ arêtes pour $\sqrt{n}$ sommets. Il faudrait enlever seulement $n$ arêtes pour que la récurrence $u(n) \leq n^{3/2}$ fonctionne…

Une autre idée vient du fait que deux cercles distincts s’intersectent en au plus deux points, et donc que deux sommets ont au plus deux voisins en commun. En termes de graphes, cela signifie qu’un graphe distance-unité ne contient pas de $\textbf{K}_{2,3}$ (graphe biparti complet contenant deux sommets d’un côté et trois de l’autre).

Quel est le nombre maximum d’arêtes d’un graphe (pas forcément distance-unité) sans $\textbf{K}_{2,3}$ ?

Être sans $\textbf{K}_{2,3}$ , ça veut dire que deux sommets quelconques ont au plus deux voisins en commun. Donc il y a au plus $\displaystyle{\binom{n}{2} \times 2}$ triplets $(u,v,w)$ tels que:

D’autre part ce nombre de triplets est aussi le nombre de façons de choisir deux voisins d’un même sommet, c’est à dire $\displaystyle \sum_{w \in V}{\binom{d(w)}{2}}$ , d’où $\displaystyle{\sum_{w\in V}{\binom{d(w)}{2}}} \leq \binom{n}{2} \times 2$ .

On peut ensuite développer $\displaystyle{\sum_{w\in V}{\binom{d(w)}{2}}}$ et, en utilisant le lemme des poignées de mains ainsi que l’inégalité de Cauchy-Schwartz, on trouve que:

Un graphe à $n$ sommets sans $\textbf{K}_{2,3}$ a au plus $\displaystyle{\frac{n}{4} (1 + \sqrt{8(n-1)+1})}$ arêtes.

Donc on retrouve que, asymptotiquement, $u(n)$ est $O(n^{3/2})$ !

En fait on on peut remplacer $\textbf{K}_{2,3}$ par un $\textbf{K}_{2,k}$ dans la preuve pour obtenir:

(Kövari-Sós-Turán) Un graphe à $n$ sommets sans $\textbf{K}_{2,k}$ a au plus $\displaystyle{\frac{n}{4} (1 + \sqrt{4(k-1)(n-1)+1})}$ arêtes.

Ce théorème est utile dans de nombreux problèmes de géométrie discrète autre que celui proposé ici.

Dans les preuves précédentes, on a utilisé le fait que deux cercles s’intersectent en au plus deux points, et ensuite on a oublié toute la géométrie du problème. Essayons d’améliorer ceci.

On a vu que le nombre de distance unité est la somme, pour tout point, du nombre de cercle-unité contenant ce point. Pour un graphe distance-unité $G$ avec $n$ sommets et $m$ arêtes, construisons le graphe $G'$ suivant: les sommets sont les $n$ points du plan, et, pour chaque cercle, on met une arête entre chaque couple de points consécutifs sur ce cercle.

Si il y a un cercle avec un seul point dessus, ce point n’augmente le nombre de distance-unité que de 1, on peut donc (quitte à enlever les sommets correspondant) supposer que tout cercle contient au moins deux points.

En rouge: un exemple d'arête — En rouge: un exemple d’arête dans $G'$

Pour chaque arête de $G$ on crée 2 arêtes dans $G'$ donc $G'$ a $n$ sommets et $2m$ arêtes.

En ajoutant une distance-unité, on augmente de 1 le nombre d'arêtes sur le cercle dessiné, et de 1 le nombre d'arêtes sur le cercle autour du point rouge — En ajoutant une distance-unité, on augmente de 1 le nombre d’arêtes sur le cercle dessiné, et de 1 le nombre d’arêtes sur le cercle autour du point rouge

$G'$ n’est pas forcément simple, il a au plus une multiplicité de 4 (la multiplicité d’un graphe est le nombre maximal d’arêtes parallèles que celui-ci possède).

On crée au plus 4 arêtes par distance-unité — Il y a au plus 4 arêtes parallèles entre 2 sommets

On souhaite donc regarder comment les cercles s’intersectent: intéressons nous au Crossing Number $cr(G')$ de $G'$ , c’est à dire le nombre minimal de croisements des arêtes qu’il y a dans une représentation planaire de $G$ . Puisque deux cercles s’intersectent en au plus deux points, $\displaystyle{cr(G') \leq 2 \binom{n}{2}}$ .

Comment trouver une minoration de $cr(G')$ ? On peut enlever $cr(G')$ arêtes de $G' = (V, E)$ de façon à enlever toutes les intersections, on obtient alors un graphe planaire, dont le nombre d’arêtes, c’est à dire $\vert E \vert$ $- cr(G')$ , est majoré par $3 \vert V \vert - 6$ , soit $cr(G') \geq \vert E \vert - 3 \vert V \vert + 6$ . Malheureusement cette inégalité, combiné avec $\displaystyle{cr(G') \leq 2 \binom{n}{2}}$ donne seulement la borne triviale en $n^2$ de $\vert E \vert$ .

L’inégalité suivante donne une meilleure minoration de $cr$ :

(Crossing number inequality) Un graphe $G$ simple (sans arête parallèle, sans boucle) ayant $n$ sommets et $m$ arêtes et tel que $m > 7n$ vérifie:

$\displaystyle{cr(G) \geq \frac{m^3}{29n^2}}$

Pour sa preuve (particulièrement élégante) je renvoie à un excellent article de Terence Tao sur son blog.

Petit soucis: cette inégalité suppose le graphe simple, or on vient de voir que $G'$ peut avoir des arêtes parallèles (jusqu’à 4)… Mais si enlève les arêtes parallèles surnuméraires de $G'$ (au plus $3 \vert E \vert$ ) on obtient un graphe simple sur lequel on peut appliquer l’inégalité ci-dessus et bien évidemment les intersections de ce graphe sont aussi des intersections de $G'$ . On en déduit que, si $\vert E \vert = 2m \geq 7n$ , alors $\displaystyle{cr(G) \geq \frac{(2m)^3}{4^3 \times 29 n^2}}$ .

Bref, si $\displaystyle{2m<7n}$ , il n’y a pas de problème, et, si $\vert E \vert = 2m \geq 7n$ , $\displaystyle{\frac{(2m)^3}{4^3 \times 29 n^2} \leq cr(G') \leq 2\binom{n}{2}}$ d’où $m = O(n^{4/3})$ !

A ce jour, il s’agit de la meilleure borne connue.

Je parlerai des bornes inférieures sur $u(n)$ , ainsi que d’autres problèmes liés à celui décrit ici, dans un prochain billet.

Quentin Fortier

Archives mensuelles : septembre 2014

Problème de distances

Bornes supérieures