Conjecture de Hadwiger (géométrie combinatoire)

Un triangle peut être recouvert par trois copies plus petites de lui-même ; un carré nécessite quatre copies plus petites.

En géométrie combinatoire, la conjecture de Hadwiger affirme que tout volume convexe dans l'espace euclidien de dimension n peut être couvert par au plus 2^n copies homothétiques du volume donné et ,de plus, que le nombre 2^n est nécessaire si et seulement si le volume est un parallélépipède. Il existe aussi une formulation équivalente sur le nombre de sources de lumière nécessaires pour éclairer le volume.

La conjecture porte le nom de Hugo Hadwiger qui l'a inclus dans une liste de problèmes ouverts publiés en 1957, mais elle avait été étudiée auparavant par Levi 1955, puis indépendamment par Gohberg et Markus 1960. Il existe aussi une conjecture de Hadwiger concernant la coloration de graphe, et dans certaines sources la conjecture de Hadwiger en géométrie combinatoire est aussi appelée la conjecture de Levi–Hadwiger ou le problème de recouvrement de Hadwiger–Levi.

La conjecture reste ouvert même en dimension trois ; le cas du plan a été résolu par Levi 1955.

Énoncé formel

Énoncé géométrique

L"énoncé formel de la conjecture de Hadwiger est le suivant :

Conjecture de Hadwiger — Si K est une partie bornée convexe de l'espace euclidien R^n de dimension n, alors il existe un ensemble de 2^n scalaires s_i et un ensemble de 2^n translations v_i tels que tous les s_i sont dans l'intervalle e 0 < s_i < 1, et

${\displaystyle K\subseteq \bigcup _{i=1}^{2^{n}}s_{i}K+v_{i}.}$.

De plus, la borne supérieure est atteint si et seulement si K est un parallélépipède, et dans ce cas les 2^n scalaires peuvent être choisis égaux à 1/2.

Formulation avec éclairage

Il a été montré par Vladimir Boltyanski que le problème est équivalent à un problème d'éclairage : combien de projecteurs doivent être placés à l'extérieur d'un solide convexe opaque pour éclairer complètement son extérieur ? Dans ce contexte, un solide n'est considéré comme éclairé que si, pour chaque point sur le contour du solide, au moins un des projecteurs est séparé du solide par l'ensemble des espaces tangents intersectant le solide en ce point ; ainsi, même si les faces d'un cube peuvent être éclairées par deux projecteurs seulement, les plans tangents à ses sommets et à ses arêtes font qu'il faut de beaucoup plus de sources de lumière pour qu'il soit pleinement éclairé. Pour tout solide convexe, le nombre de projecteurs nécessaires pour l'éclairer complètement s'avère être égal au nombre de copies plus petites du solide nécessaires pour le recouvrir[1].

Exemples

Comme le montre l'illustration, un triangle peut être couvert par trois copies plus petites de lui-même et, plus généralement, en toute dimension,un simplexe peut être couvert par n + 1 copies de lui-même, mises à l'échelle par un facteur de n/(n + 1). Cependant, pour couvrir un carré par des carrés plus petits (avec des côtés parallèles à l'original), il faut quatre carrés plus petits, car chacun ne peut couvrir qu'un seul des quatre coins du grand carré.

En dimensions supérieures, couvrant un hypercube ou plus généralement un parallélépipède par des copies homothétiques plus petites de la même forme nécessite une copie séparée pour chacun des sommets de l'hypercube ou du parallélépipède de départ ; parce que ces objets ont 2^n sommets, il faut 2^n petites copies. Ce nombre est également suffisant : un cube ou un parallélépipède peut être couvert par 2^n copies, mises à l'échelle par un facteur de 1/2. La conjecture de Hadwiger est que les parallélépipèdes sont le pire cas pour ce problème, et que tout autre volume convexe peut être couvert par moins de 2^n copies plus petites de lui-même[1].

Résultats connus

Le cas de la dimension deux a été résolu par Levi 1955: tout ensemble convexe borné bidimensionnel peut être recouvert par quatre exemplaires plus petits de lui-même, le quatrième exemplaire n'étant nécessaire que dans le cas des parallélogrammes.

La conjecture reste ouverte dans les dimensions supérieures, sauf pour certains cas particuliers. La borne supérieure asymptotique la plus connue concernant le nombre de petits exemplaires nécessaires pour couvrir un volume donné est :

${\displaystyle \displaystyle 4^{n}(5n\ln n).}$

Pour des petites valeurs de ${\displaystyle n}$ la borne supérieure ${\displaystyle (n+1)n^{n-1}-(n-1)(n-2)^{n-1}}$ prouvée par Lassak 1988 est meilleure que la borne asymptotique. En dimension trois, on sait qu'il suffit de 16 copies, mais on est encore loin de la valeur conjecturée de 8 copies[1].

La conjecture est prouvée pour certaines classes spéciales de volumes convexes, notamment les polyèdres symétriques et les solides d'épaisseur constante en trois dimensions[1]. Le nombre de copies nécessaires pour couvrir un zonoèdre est au plus ${\displaystyle (3/4)2^{n}}$, tandis que pour les volumes à surface lisse (c'est-à-dire ayant un seul plan tangent par point limite), au plus ${\displaystyle n+1}$ copies plus petites sont nécessaires pour le couvrir, comme l'a déjà prouvé Levi[1].

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hadwiger conjecture (combinatorial geometry) » (voir la liste des auteurs).

1. Brass, Moser et Pach 2005.

Bibliographie

• Vladimir Boltjansky et Israel Gohberg, Results and Problems in Combinatorial Geometry, Cambridge University Press, 1985, « 11. Hadwiger's Conjecture », p. 44–46.
• Peter Brass, William Moser et János Pach, Research Problems in Discrete Geometry, Springer-Verlag, 2005, « 3.3 Levi–Hadwiger Covering Problem and Illumination », p. 136–142.
• (ru) Israel Ts. Gohberg et Alexander S. Markus, « A certain problem about the covering of convex sets with homothetic ones », Izvestiya Moldavskogo Filiala Akademii Nauk SSSR, vol. 10, n^o 76,‎ 1960, p. 87–90.
• Hugo Hadwiger, « Ungelöste Probleme Nr. 20 », Elemente der Mathematik, vol. 12,‎ 1957, p. 121.
• Marek Lassak, « Covering the boundary of a convex set by tiles », Proceedings of the American Mathematical Society, vol. 104, n^o 1,‎ 1988, p. 269–272 (DOI 10.1090/s0002-9939-1988-0958081-7, MR 0958081).
• Friedrich Wilhelm Levi, « Überdeckung eines Eibereiches durch Parallelverschiebungen seines offenen Kerns », Archiv der Mathematik, vol. 6, n^o 5,‎ 1955, p. 369–370 (DOI 10.1007/BF01900507).

Voir aussi

• conjecture de Borsuk (en) sur le recouvrement des volumes convexes par des ensembles de plus petit diamètre.