2011/11/21 by Sarah Birdsong, Gábor Hetyei
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Algorithm #Cellular Automata and Applications #Combinatorics #Discrete mathematics #Equivalence class (music) #Gray code #Hypercube #Indecomposable module #Mathematics #graph theory and CDMA systems #math.CO #msc:05A05 #msc:52B05 #msc:52B22
paper · pdf · doi:10.1016/j.disc.2012.10.011
published as Discrete Math. 313 (2013), no. 3, 258-268
arxiv created 2011/11/21 · openalex publication_date 2012/11/07 · arxiv updated 2014/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We consider two shellings of the boundary of the hypercube equivalent if one can be transformed into the other by an isometry of the cube. We observe that a class of indecomposable permutations, bijectively equivalent to standard double occurrence words, may be used to encode one representative from each equivalence class of the shellings of the boundary of the hypercube. These permutations thus encode the shelling types of the boundary of the hypercube. We construct an adjacent transposition Gray code for this class of permutations. Our result is a signed variant of King's result showing that there is a transposition Gray code for indecomposable permutations.