A numeral system for the middle-levels graphs - Italo J. Dejter (GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, 2021)
A sequence S of restricted-growth strings unifies the presentation of middle-levels graphs Mk as follows, for 0 < k ∈ Z. Recall Mk is the subgraph in the Hasse diagram of the Boolean lattice 2[2k+1] induced by the k- and (k+1)-levels. The dihedral group D4k+2 acts on Mk via translations mod (2k + 1) and complemented reversals.The first (2k)!/(k!(k+1)!) terms of S stand for the orbits of V(Mk) under such D4k+2-action, via the lexical matching colors 0, 1, ... , k on the k+1 edges at each vertex. So, S is proposed here as a convenient numeral system for the graphs Mk. Color 0 allows to reorder S via an integer sequence that behaves as an idempotent permutation on its first (2k)!/(k!(k+1)!) terms, for each 0 < k ∈ Z. Related properties hold for the remaining colors 1, ... , k.