On a combinatorial generation problem of Knuth

DOI10.1137/20M1377394zbMATH Open1490.05148OpenAlexW3115943440MaRDI QIDQ5080484FDOQ5080484

Authors: Arturo I. Merino, Ondřej Mička, Torsten Mütze 

Publication date: 31 May 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: The well-known middle levels conjecture asserts that for every integer $ngeq1$, all binary strings of length $2(n+1)$ with exactly $n+1$ many 0s and 1s can be ordered cyclically so that any two consecutive strings differ in swapping the first bit with a complementary bit at some later position. In his book `The Art of Computer Programming Vol. 4A' Knuth raised a stronger form of this conjecture (Problem 56 in Chapter 7, Section 2.1.3), which requires that the sequence of positions with which the first bit is swapped in each step of such an ordering has $2n+1$ blocks of the same length, and each block is obtained by adding $s=1$ (modulo $2n+1$) to the previous block. In this work, we prove Knuth's conjecture in a more general form, allowing for arbitrary shifts $sgeq1$ that are coprime to $2n+1$. We also present an algorithm to compute this ordering, generating each new bitstring in $mathcalO(n)$ time, using $mathcalO(n)$ memory in total.

Full work available at URL: https://arxiv.org/abs/2007.07164

Recommendations

• Proof of the middle levels conjecture
• Efficient computation of middle levels Gray codes
• Efficient Computation of Middle Levels Gray Codes
• Trimming and gluing Gray codes
• Trimming and gluing Gray codes

zbMATH Keywords

Hamilton cyclegray codemiddle levels conjecture

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Survey of Combinatorial Gray Codes
• A constant-time algorithm for middle levels Gray codes
• A short proof of the middle levels theorem
• Adjacent interchange generation of combinations
• An algorithm for generating subsets of fixed size with a strong minimal change property
• An explicit 1-factorization in the middle of the Boolean lattice
• An update on the middle levels problem
• Colorings of diagrams of interval orders and \(\alpha\)-sequences of sets
• Distance-2 Cyclic Chaining of Constant-Weight Codes
• Doubly adjacent gray codes for the symmetric group
• Efficient generation of the binary reflected gray code and its applications
• Explicit matchings in the middle levels of the Boolean lattice
• Gray codes with restricted density
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• Hamilton cycles and paths in vertex-transitive graphs-current directions
• Hamiltonian paths in Cayley graphs
• Lexicographic matchings cannot form Hamiltonian cycles
• Lexicographically least circular substrings
• Long cycles in the middle two layers of the discrete cube
• Magical mathematics. The mathematical ideas that animate great magic tricks. With a foreword by Martin Gardner
• Monotone Gray codes and the middle levels problem
• On generalized middle-level problem
• Perfect Snake-in-the-Box Codes for Rank Modulation
• Probabilistic combinatorics and the recent work of Peter Keevash
• Proof of the middle levels conjecture
• Shorthand universal cycles for permutations
• Some Hamilton Paths and a Minimal Change Algorithm
• Some properties of a centroid of a free tree
• Sparse Kneser graphs are Hamiltonian
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• The coolest way to generate combinations
• The prism over the middle-levels graph is Hamiltonian

Cited In (3)

• On the hardness of Gray code problems for combinatorial objects
• An alternate form of Merino-Mička-Mütze's solution to a Knuth's combinatorial generation problem.
• On \(O(1)\) time algorithms for combinatorial generation

Uses Software

• OEIS

This page was built for publication: On a combinatorial generation problem of Knuth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080484)