Graph universal cycles of combinatorial objects

DOI10.1016/J.AAM.2021.102166MaRDI QIDQ2020052zbMATH OpenOpenAlexFDO

Authors Amelia Cantwell, Juliann Geraci, Anant P. Godbole, Cristobal Padilla

Publication date 23 April 2021

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

connected digraph

Mathematics Subject Classification ID

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

Abstract: A connected digraph in which the in-degree of any vertex equals its out-degree is Eulerian; this baseline result is used as the basis of existence proofs for universal cycles (also known as ucycles or generalized deBruijn cycles or U-cycles) of several combinatorial objects. The existence of ucycles is often dependent on the specific representation that we use for the combinatorial objects. For example, should we represent the subset $2,5$ of $1,2,3,4,5$ as "25" in a linear string? Is the representation "52" acceptable? Or it it tactically advantageous (and acceptable) to go with $0,1,0,0,1$? In this paper, we represent combinatorial objects as graphs, as in cite{bks}, and exhibit the flexibility and power of this representation to produce {it graph universal cycles}, or {it Gucycles}, for $k$-subsets of an $n$-set; permutations (and classes of permutations) of $[n]=1,2,ldots,n$, and partitions of an $n$-set, thus revisiting the classes first studied in cite{cdg}. Under this graphical scheme, we will represent $2,5$ as the subgraph $A$ of $C_5$ with edge set consisting of $2,3$ and $5,1$, namely the "second" and "fifth" edges in $C_5$. Permutations are represented via their permutation graphs, and set partitions through disjoint unions of complete graphs.

Recommendations

• Universal cycles for combinatorial structures
• On universal cycles for new classes of combinatorial structures
• Universal cycles of k-subsets and k-permutations
• Universal and near-universal cycles of set partitions
• Universal cycles of restriced words

Cites work

• An inductive approach to constructing universal cycles on the \(k\)-subsets of \([n]\)
• Contributions to the theory of de Bruijn cycle
• Euler tours in hypergraphs
• Near-universal cycles for subsets exist
• On Universal Cycles for k-Subsets of an n-Set
• On universal cycles for new classes of combinatorial structures
• On universal cycles of labeled graphs
• Ordering block designs. Gray codes, universal cycles and configuration orderings
• Special issue: Generalisations of de Bruijn cycles and gray codes. Papers from the Banff International Research Station (BIRS) workshop, Banff, Canada, December 5--9, 2004
• Universal and near-universal cycles of set partitions
• Universal cycles for combinatorial structures
• Universal cycles for permutations
• Universal cycles for weak orders
• Universal cycles of k-subsets and k-permutations

Cited in

(8)

• Shortened universal cycles for permutations
• On universal cycles of labeled graphs
• Universal cycles of restriced words
• Graph universal cycles: compression and connections to universal cycles
• Constructing the first (and coolest) fixed-content universal cycle
• Universal cycles of k-subsets and k-permutations
• Universal cycle constructions for k-subsets and k-multisets
• A universal cycle for strings with fixed-content (which are also known as multiset permutations)

This page was built for publication: Graph universal cycles of combinatorial objects

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