Échelle de Möbius

Une vue de ${\displaystyle ML_{8}}$ mettant en évidence sa ressemblance avec un ruban de Möbius

L'échelle de Möbius sur un ruban de Möbius.

Coloration avec 3 couleurs de ${\displaystyle ML_{4}}$.

Les échelles de Möbius sont des graphes circulants.

Elles ne sont pas des graphes planaires, mais peuvent être rendues planaires en supprimant un seul sommet, ce qui en fait des graphes apex (en). Il est possible de le dessiner sur un plan avec un seul croisement et ce nombre est minimal. Il peut être plongé (en) dans un tore ou un plan projectif sans croisements, il s'agit donc d'exemple de graphe toroïdal. De-Ming Li a exploré des plongements de ces graphes sur des surfaces d'ordre supérieur[5].

Les échelles de Möbius sont sommet-transitives mais ne sont pas arête-transitives (sauf ${\displaystyle ML_{3}}$) : chaque montant de l'échelle appartient à un seul cycle de 4 sommets, tandis que les barreaux de l'échelle appartiennent chacun à deux de ces cycles.

Le théorème de Brooks et le fait que le graphe soit cubique garantissent que 3 couleurs suffisent à le colorer. De fait, quand ${\displaystyle n}$ est pair, on a besoin des trois couleurs, et dans le cas contraire deux couleurs suffisent. De plus, les échelles de Möbius sont déterminées de façon unique par leurs polynômes chromatiques[6].

L'échelle de Möbius ${\displaystyle ML_{4}}$ possède 392 arbres couvrants. Elle et ${\displaystyle ML_{3}}$ ont le plus d'arbres couvrants parmi tous les graphes cubiques ayant le même nombre de sommets[7]^,[8]. Ce n'est toutefois pas général. En effet, le graphe cubique à 10 sommet ayant le plus d'arbres couvrants est le graphe de Petersen, qui n'est pas une échelle de Möbius.

Les polynômes de Tuttes des échelles de Möbius peuvent être calculés à l'aide d'une simple relation de récurrence[9].

Vue en trois dimensions de ${\displaystyle ML_{4}}$. Un des cycles hamiltoniens est numéroté.

Vue en trois dimensions de ${\displaystyle ML_{6}}$.

Les échelles de Möbius jouent un rôle important dans l'histoire de mineurs de graphes. Le résultat le plus ancien dans ce domaine est le théorème de 1937 de Klaus Wagner affirmant que les graphes sans mineur peut être formé en utilisant des opérations de somme de clique (en) pour combiner des graphes planaires et l'échelle de Möbius ${\displaystyle ML_{4}}$. Pour cette raison, ${\displaystyle ML_{4}}$ est appelé le graphe de Wagner[10].

Gubser (1996) définit un graphe presque planaire comme un graphe non planaire dans lequel tout mineur non trivial est planaire. Il montre que les graphes presque planaires 3-connexes sont des échelles de Möbius ou des membres d'un petit nombre d'autres familles et que d'autres graphes presque-planaires peuvent être formés à partir d'une suite d'opérations simples[11].

John Maharry a montré que presque tous les graphes qui n'ont pas un mineur cubique peuvent être déduits d'une suite d'opérations simples à partir d'échelles de Möbius[12].

D. Walba et ses collègues ont synthétisé les premiers des structures moléculaires en forme d'échelle de Möbius[13], et depuis cette structure a été objet d'intérêt en chimie et en stéréochimie[14], et en particulier en relation avec la forme en échelle des molécules d'ADN. En gardant cette application à l'esprit, Erica Flapan étudie[15] les symétries mathématiques des plongements (en) des échelles de Möbius dans ${\displaystyle \mathbb {R} ^{3}}$.

Les échelles de Möbius ont également été utilisées pour la forme d'anneaux supraconducteurs dans des expériences consistant à étudier la structure spatiale des conducteurs dans les interactions entre électrons[16]^,[17].

Enfin, elles ont également été utilisées en informatique, dans le cadre d'approches par optimisation linéaire en nombres entiers de problèmes de set packing et d'ordonnancement. Les échelles de möbius peuvent servir à définir les facettes du polytope qui décrit une relaxation continue du problème ; ces facettes sont appelées contraintes en échelle de Möbius[18]^,[19]^,[20]^,[21]^,[22].