Chung–Diaconis–Graham conjecture on universal cycles

About 18 years old · traced to

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∣(n−1k−1)k\mid\binom{n-1}{k-1}.

Chung–Diaconis–Graham conjecture. For every k∈Nk\in\mathbb{N}, there exists n0∈Nn_0\in\mathbb{N} such that for all n≥n0n\ge n_0, there exists a universal cycle for ([n]k)\binom{[n]}{k} whenever kk divides (n−1k−1)\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.

References

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.