Pour inaugurer ce magnifique blog, je vais parler du problème suivant (Unit distance problem), posé par Erdős en 1946:
On place points distincts dans le plan. Quel est le nombre maximum de couples de points à distance un?
Appelons 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é.

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 , du nombre de cercles contenant
.
On peut calculer les valeurs exactes des premiers et les graphes distance-unité correspondant:
Bien évidemment, .
De plus, en considérant une grille, on s’aperçoit que . 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
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
.
-
Bornes supérieures
La première borne supérieure pour , proposé par Erdős, est
, i.e qu’un sommet ait en moyenne au plus
voisins. Montrons
par récurrence sur
:
Supposons que notre graphe distance-unité à
sommets ait
arêtes. Si il existe un sommet de degré au plus
alors en enlevant ce sommet on obtient un graphe à
sommets et au moins
arêtes. On en déduit par récurrence que
et donc que
.
Si maintenant tous les sommets ont un degré supérieur à , choisissons-en un
. Considérons un ensemble
de
voisins
. Combien d’arêtes enlève t-on lorsqu’on enlève
du graphe? Déjà les
arêtes entre
et les éléments de
. Mais, un sommet
différent de
est contenu dans au plus deux cercles-unité issus des points de
(pour s’en convaincre, regarder la figure ci-dessous).
Donc en enlevant
on enlève au plus 2
arêtes, i.e le nouveau graphe a
sommets et au moins
arêtes. Ainsi
, en utilisant
.
D’où dès que
.
Pourquoi montrer et non pas
? Le problème est que dans le deuxième cas de la récurrence on enlève
arêtes pour
sommets. Il faudrait enlever seulement
arêtes pour que la récurrence
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 (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 ?
Être sans , ça veut dire que deux sommets quelconques ont au plus deux voisins en commun. Donc il y a au plus
triplets
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 , d’où
.
On peut ensuite développer et, en utilisant le lemme des poignées de mains ainsi que l’inégalité de Cauchy-Schwartz, on trouve que:
Un graphe à sommets sans
a au plus
arêtes.
Donc on retrouve que, asymptotiquement, est
!
En fait on on peut remplacer par un
dans la preuve pour obtenir:
(Kövari-Sós-Turán) Un graphe à sommets sans
a au plus
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é avec
sommets et
arêtes, construisons le graphe
suivant: les sommets sont les
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.

Pour chaque arête de on crée 2 arêtes dans
donc
a
sommets et
arêtes.

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 souhaite donc regarder comment les cercles s’intersectent: intéressons nous au Crossing Number de
, c’est à dire le nombre minimal de croisements des arêtes qu’il y a dans une représentation planaire de
. Puisque deux cercles s’intersectent en au plus deux points,
.
Comment trouver une minoration de ? On peut enlever
arêtes de
de façon à enlever toutes les intersections, on obtient alors un graphe planaire, dont le nombre d’arêtes, c’est à dire
, est majoré par
, soit
. Malheureusement cette inégalité, combiné avec
donne seulement la borne triviale en
de
.
L’inégalité suivante donne une meilleure minoration de :
(Crossing number inequality) Un graphe simple (sans arête parallèle, sans boucle) ayant
sommets et
arêtes et tel que
vérifie:
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 peut avoir des arêtes parallèles (jusqu’à 4)… Mais si enlève les arêtes parallèles surnuméraires de
(au plus
) 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
. On en déduit que, si
, alors
.
Bref, si , il n’y a pas de problème, et, si
,
d’où
!
A ce jour, il s’agit de la meilleure borne connue.
Je parlerai des bornes inférieures sur , ainsi que d’autres problèmes liés à celui décrit ici, dans un prochain billet.