Labbé, Sébastien et Reutenauer, Christophe
(2015).
« A d-dimensional Extension of Christoffel Words ».
Discrete & Computational Geometry, 54(1), pp. 152-181.
Fichier(s) associé(s) à ce document :
Résumé
In this article, we extend the definition of Christoffel words to directed subgraphs of the hypercubic lattice in an arbitrary dimension that we call Christoffel graphs. Christoffel graphs, when d=2, correspond to the well-known Christoffel words. Due to periodicity, the d-dimensional Christoffel graph can be embedded in a (d−1)-torus (a parallelogram when d=3). We show that Christoffel graphs have similar properties to those of Christoffel words: symmetry of their central part and conjugation with their reversal. Our main result extends Pirillo’s theorem (characterization of Christoffel words which asserts that a word amb is a Christoffel word if and only if it is conjugate to bma) to an arbitrary dimension. In the generalization, the map amb↦bma is seen as a flip operation on graphs embedded in Zd and the conjugation is a translation. We show that a fully periodic subgraph of the hypercubic lattice is a translation of its flip if and only if it is a Christoffel graph.
Altmetric
Altmetric
RECHERCHER
PARCOURIR
LIBRE ACCÈS
