Repository logo
 

Solution of an outstanding conjecture: the non-existence of universal cycles with k= n−2

Simple item page
dc.contributor.authorStevens, Brett
dc.contributor.authorBuskell, Paul
dc.contributor.authorEcimovic, Paule
dc.contributor.authorIvanescu, Cristian
dc.contributor.authorMalik, Abid Muslim
dc.contributor.authorSavu, Anamaria
dc.contributor.authorVassilev, Tzvetalin S.
dc.contributor.authorVerrall, Helen
dc.contributor.authorYang, Boting
dc.contributor.authorZhao, Zhiduo
dc.date.accessioned2025-02-06T21:35:29Z
dc.date.available2025-02-06T21:35:29Z
dc.date.issued2002
dc.description.abstractA universal cycle for k-subsets of an n-set, {1,2,…,n}, is a cyclic sequence of integers with the property that each subset of {1,2,…,n} of size k appears exactly once consecutively in the sequence. This problem was first posed by Chung et al. (Discrete Math. 110 (1992) 43) and solved for k=2,3,4,6 by Jackson and Hurlbert (Ph.D. Thesis, Rutgers University, New Brunswick, NJ, 1990; SIAM J. Discrete Math. 7(4) (1994) 598; Discrete Math. 137 (1995) 241; Personal communication, 1999). Both Jackson and Hurlbert noted the difficulty of finding universal cycles with k⩾⌈n/2⌉. Jackson has found some of these but conjectured that universal cycles never exist when k=n−2. We prove this result and give some bounds on the longest word not repeating any (n−2)-subset and also the shortest word that contains all at least once.
dc.description.urihttps://macewan.primo.exlibrisgroup.com/permalink/01MACEWAN_INST/d1nmsu/cdi_scopus_primary_2_s2_0_0037032975
dc.identifier.citationStevens, B., Buskell, P., Ecimovic, P., Ivanescu, C., Malik, A. M., Savu, A., Vassilev, T. S., Verrall, H., Yang, B., & Zhao, Z. (2002). Solution of an outstanding conjecture: the non-existence of universal cycles with k= n−2. Discrete Mathematics, 258(1), 193–204. https://doi.org/10.1016/S0012-365X(02)00298-4
dc.identifier.doihttps://doi.org/10.1016/S0012-365X(02)00298-4
dc.identifier.urihttps://hdl.handle.net/20.500.14078/3798
dc.language.isoen
dc.rightsAll Rights Reserved
dc.subjectuniversal cycle
dc.subjectgray code
dc.subjectqueue
dc.subjectcombination
dc.titleSolution of an outstanding conjecture: the non-existence of universal cycles with k= n−2en
dc.typeArticle

Files

Collections

Department of Mathematics and Statistics