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

A 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.

Publication Information

Stevens, 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