×

Graph universal cycles of combinatorial objects. (English) Zbl 1462.05205

Summary: 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 is it tactically advantageous (and acceptable) to go with \(\{0, 1, 0, 0, 1 \}\)? In this paper, we represent combinatorial objects as graphs, as in [G. Brockman et al., Electron. J. Comb. 17, No. 1, Research Paper R4, 9 p. (2010; Zbl 1184.05110)], and exhibit the flexibility and power of this representation to produce graph universal cycles, or 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 [F. Chung et al., Discrete Math. 110, No. 1–3, 43–59 (1992; Zbl 0776.05001)]. 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.

MSC:

05C45 Eulerian and Hamiltonian graphs
05A05 Permutations, words, matrices
05A18 Partitions of sets
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Hurlbert, G.; Jackson, B.; Stevens, B., (Proceedings of the Workshop on Generalizations of de Bruijn Cycles and Gray Codes. Proceedings of the Workshop on Generalizations of de Bruijn Cycles and Gray Codes, held at the Banff International Research Station, Banff, December 4-9 (2004)). (Proceedings of the Workshop on Generalizations of de Bruijn Cycles and Gray Codes. Proceedings of the Workshop on Generalizations of de Bruijn Cycles and Gray Codes, held at the Banff International Research Station, Banff, December 4-9 (2004)), Discrete Math., 309, 5255-5508 (2009), special volume · Zbl 1211.05004
[2] Blanca, A.; Godbole, A., On universal cycles for new classes of combinatorial structures, SIAM J. Discrete Math., 25, 1832-1842 (2011) · Zbl 1237.05111
[3] Brockman, G.; Kay, B.; Snively, E., On universal cycles of labeled graphs, Electron. J. Comb., 17, Article R4 pp. (2010) · Zbl 1184.05110
[4] Campbell, A.; Godbole, A.; Kay, B., Contributions to the theory of de Bruijn cycles, Integers, 14A, Article A2 pp. (2014)
[5] Chung, F.; Diaconis, P.; Graham, R., Universal cycles for combinatorial structures, Discrete Math., 110, 43-59 (1992) · Zbl 0776.05001
[6] Curtis, D.; Hines, T.; Hurlbert, G.; Moyer, T., Near-universal cycles for subsets exist, SIAM J. Discrete Math., 23, 1441-1449 (2009) · Zbl 1231.05049
[7] Diaconis, P.; Graham, R.; Gardner, M., Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks (2011), Princeton University Press: Princeton University Press New Jersey
[8] Dewar, M.; Stevens, B., Gray Codes, Universal Cycles, and Configuration Orderings (2012), Springer Verlag: Springer Verlag New York · Zbl 1260.05001
[9] Glock, S.; Joos, F.; Kühn, D., Euler tours in hypergraphs, Combinatorica, 40, 679-690 (2020) · Zbl 1474.05287
[10] Horan, V.; Hurlbert, G., Universal cycles for weak orders, SIAM J. Discrete Math., 27, 1360-1371 (2013) · Zbl 1292.05011
[11] Higgins, Z.; Kelley, E.; Sieben, B.; Godbole, A., Universal and near-universal cycles of set partitions, Electron. J. Comb., 22, Article P4.48 pp. (2015) · Zbl 1329.05160
[12] Hurlbert, G., On universal cycles for k-subsets of an n-set, SIAM J. Discrete Math., 7, 598-604 (1994) · Zbl 0810.05012
[13] Jackson, B., Universal cycles of k-subsets and k-permutations, Discrete Math., 17, 141-150 (1993) · Zbl 0783.05001
[14] Johnson, J. R., Universal cycles for permutations, Discrete Math., 309, 5264-5270 (2009) · Zbl 1181.05005
[15] Rudoy, Y., An inductive approach to constructing universal cycles on the k-subsets of \([n]\), Electron. J. Comb., 20, Article P18 pp. (2013) · Zbl 1267.05014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.