Universal cycles for $k$-sets of an $n$-set

Question

Let $[n] = \{1, \ldots, n \}$, and let $S(n,k)$ be the family of $k$-element subsets of $[n]$.

A cyclic word $w$ over alphabet $[n]$ is called a universal cycle for $S(n,k)$ if each element of $S(n,k)$ appears in $w$ as a factor (continuous subword) exatly once.

---

Examlpe

$n=8$, $k=3$

$w = 02456145712361246703671345034601250135672560234723570147$.

Here, for example, since the first 3-letter subword $024$ represents the 3-set $\{ 0,2,4 \}$ then none of the five other 3-letter subwords $042$, $204$, $240$, $402$ and $420$ can occur in $w$.

---

It is not hard to see that if $S(n,k)$ has a universal cycle, then $k$ divides $\binom{n-1}{k-1}$.

The following conjecture was proposed in [Chung F., Diaconis P., Graham R. Universal cycles for combinatorial structures // Discrete Mathematics (1992)]

Conjecture. For every natural $k$ there is $n_0(k)$ such that a universal cycle for $S(n,k)$ always exists provided that $k$ divides $\binom{n-1}{k-1}$ and $n \geq n_0(k)$.

I'm wondering if this conjecture is still open, and if yes, then what would be a good reference to check recent progress?

Answer 1

I believe the conjecture is still open. See the comment on Problem 476 and references therein for partial results in the paper below.

Jackson, Brad; Stevens, Brett; Hurlbert, Glenn. Research problems on Gray codes and universal cycles. Discrete Math. 309 (2009), no. 17, 5341--5348.

This is fairly recent (2009). A look at the papers which cite the above shows the following paper with some further results.

Blanca, Antonio; Godbole, Anant P. On universal cycles for new classes of combinatorial structures. SIAM J. Discrete Math. 25 (2011), no. 4, 1832--1842.