Chung–Diaconis–Graham conjecture on universal cycles

Let [n]={1,,n}[n]=\{1,\dots,n\}, and let ([n]k)\binom{[n]}{k} be the family of all kk-subsets of [n][n]. A universal cycle for ([n]k)\binom{[n]}{k} is a cyclic sequence of length (nk)\binom{n}{k} whose every kk consecutive elements are distinct and whose consecutive kk-element sets are precisely the members of ([n]k)\binom{[n]}{k}, each exactly once. The necessary divisibility condition is k(n1k1)k\mid\binom{n-1}{k-1}.

Chung–Diaconis–Graham conjecture. For every kNk\in\mathbb{N}, there exists n0Nn_0\in\mathbb{N} such that for all nn0n\ge n_0, there exists a universal cycle for ([n]k)\binom{[n]}{k} whenever kk divides (n1k1)\binom{n-1}{k-1}.

This conjecture asserts that the evident divisibility condition is asymptotically sufficient for universal cycles. The paper proves the claim in the complete-hypergraph case, thereby confirming the conjecture.

Sources & referencesView supporting material

Primary source

Stefan Glock, Felix Joos, Daniela Kühn and Deryk Osthus, “Euler tours in hypergraphs”, arXiv:1808.07720 (2020).

Additional references

3 papers in this index state this conjecture (2008–2018). The statement above is taken from the most recent of them; the others are arXiv:1209.4662, arXiv:0809.3725.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.