A d-dimensional Extension of Christoffel Words

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 :
[img]
Prévisualisation
PDF
Télécharger (833kB)

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.

Type: Article de revue scientifique
Mots-clés ou Sujets: Christoffel words, Christoffel graphs, Digital hyperplane, Flip, Hypercubic lattice, Pirillo’s theorem
Unité d'appartenance: Faculté des sciences > Département de mathématiques
Déposé par: Christophe Reutenauer
Date de dépôt: 28 avr. 2016 18:32
Dernière modification: 19 mai 2016 18:19
Adresse URL : http://archipel.uqam.ca/id/eprint/8361

Statistiques

Voir les statistiques sur cinq ans...