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

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

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)