Repository logo

Browsing by Author "Zhao, Zhiduo"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Solution of an outstanding conjecture: the non-existence of universal cycles with k= n−2
    (2002) Stevens, Brett; Buskell, Paul; Ecimovic, Paule; Ivanescu, Cristian; Malik, Abid Muslim; Savu, Anamaria; Vassilev, Tzvetalin S.; Verrall, Helen; Yang, Boting; Zhao, Zhiduo
    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.