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

A universal cycle for k-subsets of an n-set, {1,2,…,n}, is a cyclic sequence of (nk) 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.