Accueil🇫🇷Chercher

Conjecture de Hadwiger (géométrie combinatoire)

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 2n copies homothétiques du volume donné et ,de plus, que le nombre 2n 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.

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

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 Rn de dimension n, alors il existe un ensemble de 2n scalaires si et un ensemble de 2n translations vi tels que tous les si sont dans l'intervalle e 0 < si < 1, et

.

De plus, la borne supérieure est atteint si et seulement si K est un parallélépipède, et dans ce cas les 2n 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 2n sommets, il faut 2n petites copies. Ce nombre est également suffisant : un cube ou un parallélépipède peut être couvert par 2n 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 2n 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 :

Pour des petites valeurs de la borne supérieure 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 , tandis que pour les volumes à surface lisse (c'est-à-dire ayant un seul plan tangent par point limite), au plus copies plus petites sont nécessaires pour le couvrir, comme l'a déjà prouvé Levi[1].

Notes et références

Bibliographie

Voir aussi

  • conjecture de Borsuk (en) sur le recouvrement des volumes convexes par des ensembles de plus petit diamètre.
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.