A numeral system for the middle-levels graphs

Italo J. Dejter

Abstract


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.


Keywords


numeral system, middle-levels graph, Boolean lattice, Hasse diagram, complemented reversal

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2021.9.1.13

References

J. Arndt, Matters Computational: Ideas, Algorithms, Source Code, Springer, 2011.

C. Dalfo, M.A. Fiol, and M. Mitjana, Cube middle graphs, Electron. J. Graph Theory Appl. 3 (2) (2015), 133–145.

C. Dalfo and M.A. Fiol, Graphs, friends and acquaintance, Electron. J. Graph Theory Appl. 6 (2) (2018), 28–305.

I.J. Dejter, J. Cordova, and J.A. Quintana, Two Hamilton cycles in bipartite reflective Kneser graphs, Discrete Math. 72 (1988), 6–70.

I.J. Dejter, Reinterpreting the middle-levels theorem via natural enumeration of ordered trees, Open Journal of Discrete Applied Mathematics 3–2 (2020), 8–22.

P. Gregor, T.Mutze, and J. Nummenpalo, A short proof of the middle levels theorem, Discrete Analysis, 2018:8, 12pp.

H.A. Kierstead and W.T. Trotter, Explicit matchings in the middle levels of the Boolean lattice, Order 5 (1988), 163–171.

T. Mutze, Proof of the middle levels conjecture, Proc. Lond. Math. Soc. 112 (2016) 677–713.

[

T.Mutze and J. Nummenpalo, Efficient computation of middle levels gray codes, ACM Trans. Algorithms 14 (2018), (2)-15, 1–29.

T. Mutze, J. Nummenpalo, and B.Walczak, Sparse Kneser graphs are Hamiltonian, STOC’18, Proc. 50th Annual ACM SIGACT Symp. on Theory of Computing, 912–919, ACM, New York, 2018.

T. Mutze and J. Nummenpalo, A constant-time Algorithm for middle levels gray codes, Algorithmica 82 (5) (2020), 1239–1258.

I. Shields and C. Savage, A Hamilton path heuristic with applications to the middle two levels problem, Congr. Num. 140 (1999), 161-178.

N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/.

R. Stanley, Enumerative Combinatorics, Volume 2, (Cambridge Studies in Advanced Mathematics Book 62), Cambridge University Press, 1999.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats