Universal cycles for combinatorial structures

DOI10.1016/0012-365X(92)90699-GzbMath0776.05001OpenAlexW2085157194WikidataQ29041464 ScholiaQ29041464MaRDI QIDQ1208348

Persi Diaconis, Fan R. K. Chung, Ronald L. Graham

Publication date: 16 May 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(92)90699-g

zbMATH Keywords

partitions permutations universal cycle De Bruijn cycles

Mathematics Subject Classification ID

Partitions of sets (05A18) Permutations, words, matrices (05A05) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items

A universal cycle for strings with fixed-content (which are also known as multiset permutations) ⋮ Universal and overlap cycles for posets, words, and juggling patterns ⋮ Packing analogue of \(k\)-radius sequences ⋮ Multicover Ucycles ⋮ Enumerations of universal cycles for \(k\)-permutations ⋮ Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles ⋮ Path-sequential labellings of cycles ⋮ New classes of perfect maps. I ⋮ The combinatorics of binary arrays ⋮ Equivalence class universal cycles for permutations ⋮ Quasi-Eulerian hypergraphs ⋮ Euler tours in hypergraphs ⋮ Computing generalized de Bruijn sequences ⋮ Designing preference functions for de Bruijn sequences with forbidden words ⋮ Enumerating cycles in the graph of overlapping permutations ⋮ Graph universal cycles: compression and connections to universal cycles ⋮ Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions ⋮ Properties of the cycles that contain all vectors of weight \(\le k\) ⋮ The lexicographically smallest universal cycle for binary strings with minimum specified weight ⋮ On universal partial words ⋮ Constructing the first (and coolest) fixed-content universal cycle ⋮ Universal partial words over non-binary alphabets ⋮ Graphs with the unique path property: Structure, cycles, factors, and constructions ⋮ An embedding technique in the study of word-representability of graphs ⋮ A new universal cycle for permutations ⋮ The k-centre problem for classes of cyclic words ⋮ A tight upper bound on the length of maximal bordered box repetition-free words ⋮ Short k‐radius sequences, k‐difference sequences and universal cycles ⋮ Locating patterns in the de Bruijn torus ⋮ Universal and near-universal cycles of set partitions ⋮ An inductive approach to constructing universal cycles on the \(k\)-subsets of \([n\)] ⋮ Binary bubble languages and cool-lex order ⋮ The existence of \(k\)-radius sequences ⋮ On a Greedy Algorithm to Construct Universal Cycles for Permutations ⋮ Number of cycles in the graph of 312-avoiding permutations ⋮ Containing All Permutations ⋮ Growing perfect cubes ⋮ On shortening \(u\)-cycles and \(u\)-words for permutations ⋮ Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set ⋮ Overlap Cycles for Steiner Quadruple Systems ⋮ Harmonious and achromatic colorings of fragmentable hypergraphs ⋮ Universal cycles of \(k\)-subsets and \(k\)-permutations ⋮ 1-overlap cycles for Steiner triple systems ⋮ On uniquely \(k\)-determined permutations ⋮ On the de Bruijn torus problem ⋮ Shorthand universal cycles for permutations ⋮ Hamiltonian decompositions of complete \(k\)-uniform hypergraphs ⋮ Universal cycles of classes of restricted words ⋮ Graph universal cycles of combinatorial objects ⋮ Cycles in the graph of overlapping permutations avoiding barred patterns ⋮ Generalized de Bruijn words for primitive words and powers ⋮ De Bruijn Sequences for the Binary Strings with Maximum Density ⋮ The feasible region for consecutive patterns of permutations is a cycle polytope ⋮ The feasible region for consecutive patterns of permutations is a cycle polytope ⋮ Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence ⋮ de Bruijn sequences and de Bruijn graphs for a general language ⋮ Universal cycles for permutations ⋮ Minimum Eulerian circuits and minimum de Bruijn sequences ⋮ On universal cycles for multisets ⋮ A recursive construction for universal cycles of 2-subspaces ⋮ Universal cycles of \((n - 1)\)-partitions of an \(n\)-set ⋮ Hamiltonian paths in Cayley graphs ⋮ Universal cycles for minimum coverings of pairs by triples, with application to 2-radius sequences ⋮ Gray cycles of maximum length related to \(k\)-character substitutions ⋮ Shortened universal cycles for permutations

Cites Work