On the number of tangencies among 1-intersecting curves

Cet article démontre la conjecture de János Pach affirmant que le nombre de tangences parmi un ensemble de courbes x-monotones qui se coupent exactement une fois est linéaire par rapport au nombre de courbes.

L'essentiel

Imaginez que vous êtes un urbaniste chargé de dessiner des routes dans une ville très particulière. Dans cette ville, il y a une règle d'or : chaque route doit croiser chaque autre route exactement une fois.

Parfois, les routes se croisent en formant un "X" (un croisement classique). Mais parfois, elles se touchent simplement, comme deux voitures qui frôlent leur pare-choc sans se percuter : c'est ce qu'on appelle une tangence.

Le problème que les auteurs de cet article, Eyal Ackerman et Balázs Keszegh, tentent de résoudre est le suivant : Si vous avez un grand nombre de routes (disons $n$), combien de fois au maximum peuvent-elles se frôler (se toucher) sans se croiser ?

Le mystère du "frôlement"

Il y a quelques années, un mathématicien célèbre, János Pach, a émis une hypothèse (une conjecture) : il pensait que le nombre de ces frôlements ne pouvait pas exploser. Il croyait que même si vous aviez des milliers de routes, le nombre de frôlements resterait proportionnel au nombre de routes (par exemple, si vous avez 100 routes, vous ne pouvez pas avoir 10 000 frôlements, mais plutôt quelque chose comme 200 ou 300).

Cependant, si les routes peuvent se croiser n'importe comment, il est possible de créer des situations où les frôlements sont beaucoup plus nombreux (comme $n^{4/3}$). Mais les auteurs se sont concentrés sur un cas plus simple et plus ordonné : les courbes "x-monotones".

L'analogie des courbes "x-monotones"

Pour comprendre ce terme compliqué, imaginez que toutes vos routes vont de gauche à droite sans jamais faire demi-tour.

• Si vous tracez une ligne verticale n'importe où sur votre carte, elle ne traversera chaque route qu'une seule fois.
• C'est comme si toutes les routes étaient des rivières qui coulent toujours vers l'est, sans jamais faire de boucle vers l'ouest.

C'est dans ce cadre très ordonné que les auteurs ont prouvé la conjecture de Pach.

Comment ont-ils prouvé cela ? (La méthode des "Bleus" et des "Rouges")

Pour démontrer que le nombre de frôlements est limité, les auteurs ont utilisé une stratégie de tri très intelligente, un peu comme si vous deviez organiser une grande fête où certains invités ne peuvent pas se parler.

1. Le tri par couleur : Ils ont divisé les routes en deux équipes : les Bleues et les Rouges.

   • La règle est simple : une route Bleue ne peut "frôler" qu'une route Rouge. Deux routes Bleues ne se frôlent jamais (elles se croisent toujours).
   • Cela crée un système très structuré, comme un tournoi de tennis où les joueurs de l'équipe A ne jouent jamais contre les joueurs de l'équipe A, mais seulement contre l'équipe B.

2. L'arbre de la forêt : En regardant comment ces routes se touchent, ils ont découvert que si l'on dessine un lien entre chaque paire de routes qui se frôle, on obtient une structure qui ressemble à une forêt (un ensemble d'arbres sans boucles).

   • Imaginez des arbres dans une forêt. Si vous avez 100 arbres, vous ne pouvez pas avoir 10 000 branches qui se connectent les unes aux autres sans créer de cercles magiques. Il y a une limite naturelle.
   • Grâce à cette propriété, ils ont pu montrer mathématiquement que le nombre de frôlements ne peut pas dépasser un certain multiple du nombre de routes.

3. L'escalade interdite : Pour les autres types de frôlements, ils ont utilisé une autre astuce. Ils ont imaginé les frôlements comme des marches d'escalier. Ils ont prouvé qu'il est impossible de construire une "montée" trop longue (une suite de frôlements qui s'enchaînent dans un ordre précis). Si vous essayez de monter trop haut, la géométrie des routes vous force à faire une boucle, ce qui est interdit par les règles du jeu.

Le résultat final

En résumé, ces mathématiciens ont dit : "Non, vous ne pouvez pas créer une ville où les routes se frôlent de manière chaotique."

Même si vous avez des milliers de routes qui vont toutes de gauche à droite et qui se croisent toutes exactement une fois, le nombre de fois où elles se touchent doucement (sans se percuter) restera toujours proportionnel au nombre de routes. C'est une bonne nouvelle pour les mathématiciens : cela signifie que le chaos est limité dans ce monde géométrique.

En une phrase : Sur une carte où toutes les routes vont de gauche à droite et se croisent une seule fois, le nombre de "frôlements" entre elles ne peut jamais exploser ; il reste toujours raisonnable et contrôlé.

Résumé technique

1. Problématique et Contexte

L'article s'intéresse à la géométrie combinatoire, plus précisément au nombre de points de tangence (ou de contact) dans une famille de courbes planes.

• Définitions :

  • Une courbe est un arc de Jordan (image d'une fonction continue injective d'un intervalle fermé dans $\mathbb{R}^2$).
  • Une courbe est x-monotone si aucune ligne verticale ne la coupe en plus d'un point.
  • Une famille de courbes est dite 1-intersectante si chaque paire de courbes distinctes se coupe en exactement un point. Ce point d'intersection est soit un point de croisement (transversal), soit un point de tangence (touchant).
  • Une contrainte cruciale est imposée : aucune trois courbes ne doivent se couper en un même point. Sans cette restriction, on pourrait construire des familles avec $\Omega(n^2)$ tangences (ex: graphes de $x^{2i}$).

• La Conjecture de Pach :
  János Pach a conjecturé que pour une telle famille $\mathcal{C}$ de $n$ courbes (sans triple intersection, 1-intersectante), le nombre de paires de courbes tangentes est linéaire, c'est-à-dire $O(n)$.

  • Contexte antérieur : Des constructions basées sur les incidences point-ligne d'Erdős montrent qu'il existe des familles 1-intersectantes avec $\Omega(n^{4/3})$ tangences si l'on ne suppose pas que les courbes sont x-monotones. Pour les courbes x-monotones, la borne supérieure connue était $O(n^{4/3} (\log n)^{2/3})$.

• Objectif de l'article : Prouver la conjecture de Pach pour le cas spécifique des courbes x-monotones.

2. Méthodologie

Les auteurs divisent la preuve en deux parties principales basées sur la géométrie relative des projections des courbes sur l'axe des $x$. Ils utilisent une approche par graphes de tangence et des propriétés d'ordre partiel.

A. Classification des tangences

Soient deux courbes $c_1$ et $c_2$ qui se touchent. Selon la position relative de leurs extrémités gauche ($L$) et droite ($R$) sur l'axe des $x$, les auteurs définissent quatre types de relations d'ordre partiel ($\prec_i$ pour $i=1,2,3,4$) :

1. $L(c_1) < L(c_2) < R(c_2) < R(c_1)$ (Inclusion stricte).
2. $L(c_2) < L(c_1) < R(c_1) < R(c_2)$ (Inclusion stricte inversée).
3. $L(c_1) < L(c_2) < R(c_1) < R(c_2)$ (Chevauchement partiel).
4. $L(c_2) < L(c_1) < R(c_2) < R(c_1)$ (Chevauchement partiel inversé).

La preuve traite séparément les tangences de Types 1 et 2 (inclusions) et les Types 3 et 4 (chevauchements).

B. Preuve pour les Types 1 et 2 (Inclusions)

1. Partitionnement : En utilisant une ligne verticale $\ell$ coupant toutes les courbes, les auteurs partitionnent les courbes en deux ensembles : bleues et rouges. Une courbe bleue touche une courbe rouge par-dessous.
2. Propriété de croisement : Ils démontrent que deux courbes bleues doivent nécessairement se croiser (elles ne peuvent pas être tangentes entre elles dans ce contexte).
3. Graphe de tangence bipartite : Ils construisent un graphe $G$ où les sommets sont les courbes bleues et rouges, et les arêtes représentent les tangences.
4. Absence de cycles : La partie centrale de la preuve consiste à montrer que ce graphe $G$ est une forêt (un graphe sans cycles).
   • Ils utilisent une induction et des propriétés topologiques (ordre des intersections sur $\ell$ et sur les courbes) pour prouver qu'un cycle dans $G$ conduirait à une contradiction géométrique (par exemple, une courbe devrait traverser une autre courbe deux fois ou ne pas pouvoir atteindre l'axe $y$).
   • Puisque $G$ est une forêt sur $n$ sommets, il a au plus $n-1$ arêtes. Cela implique un nombre linéaire de tangences de ce type.

C. Preuve pour les Types 3 et 4 (Chevauchements)

1. Réduction par théorèmes de Dilworth/Mirsky : Pour les types 3 et 4, les auteurs utilisent le théorème dual de Dilworth (Théorème de Mirsky). Ils montrent que l'ensemble des courbes bleues peut être partitionné en un nombre constant de chaînes et d'anti-chaînes par rapport aux relations d'ordre $\prec_i$. En itérant ce processus, ils isolent un sous-ensemble de courbes bleues qui sont toutes mutuellement croisées et qui contiennent une fraction constante des tangences.
2. Graphes et chemins monotones : Ils définissent un ordre total sur les arêtes du graphe de tangence basé sur la position $x$ des points de tangence.
3. Propriété de non-existence de chemins longs : Ils prouvent que le graphe de tangence ne contient pas de chemin croissant monotone de longueur 7 (une suite d'arêtes $e_1, \dots, e_7$ telles que $e_1 < e_2 < \dots < e_7$).
4. Application du lemme de Rödl : En utilisant un résultat de Rödl (cité via [6]), qui stipule qu'un graphe sans chemin croissant de longueur $k$ a au plus $O(k^2 |V|)$ arêtes, ils concluent que le nombre d'arêtes (tangences) est linéaire en fonction du nombre de sommets.

3. Résultats Principaux

• Théorème 2 (Résultat Principal) : Soit $\mathcal{C}$ un ensemble de $n$ courbes x-monotones telles qu'aucune trois ne se coupent en un point et que chaque paire se coupe exactement une fois (croisement ou tangence). Alors, le nombre de tangences dans $\mathcal{C}$ est $O(n)$.
• Preuve de la Conjecture de Pach : Ce résultat confirme la conjecture de János Pach pour la classe des courbes x-monotones.
• Bornes inférieures : Les auteurs mentionnent une construction simple montrant qu'il est possible d'avoir $3n - 4$ tangences, ce qui suggère que la borne est effectivement linéaire (bien que la constante cachée dans leur preuve soit très grande, de l'ordre de 900).

4. Contributions Clés et Signification

• Résolution d'un problème ouvert : L'article résout une conjecture majeure en géométrie combinatoire pour une classe importante de courbes (x-monotones), fermant l'écart entre les bornes inférieures ($\Omega(n)$) et supérieures connues ($O(n^{4/3})$).
• Nouvelles techniques combinatoires : L'article combine habilement la topologie des courbes planes, la théorie des ordres partiels (Dilworth/Mirsky) et la théorie des graphes (propriétés de chemins monotones) pour contraindre la structure des intersections.
• Distinction cruciale : Il met en évidence que la propriété d'être x-monotone est suffisante pour réduire drastiquement le nombre de tangences par rapport au cas général où la borne est $\Theta(n^{4/3})$.
• Limites et perspectives :
  • La constante dans la borne $O(n)$ est très élevée (environ 904), ce qui suggère que la preuve n'est pas optimale en termes de constantes.
  • Les auteurs soulignent que si l'on autorise plus de deux courbes à se couper en un même point (mais en comptant les points de tangence et non les paires), la borne linéaire ne tient plus ($\Omega(n^{4/3})$ est possible).
  • La question de la borne exacte (le coefficient optimal) pour les courbes x-monotones reste ouverte.

En résumé, ce papier établit que pour des courbes x-monotones qui se coupent toutes deux à deux, la complexité des contacts (tangences) est fondamentalement linéaire, contrairement aux cas plus généraux où elle peut être super-linéaire.