Universal cycles for k-subsets

DefinitionUniversal cycle for \(k\)-subsets#✓fully proved

For natural numbers \(n\) and \(k\), let \(N = \binom{n}{k}\). A sequence \(c_0, \dots, c_{N-1}\) of elements of \(\{0, \dots, n-1\}\), read cyclically, is a universal cycle for the \(k\)-subsets of \(\{0, \dots, n-1\}\) when, for every starting position \(i < N\), the \(k\) consecutive entries \(c_i, c_{i+1}, \dots, c_{i+k-1}\) (indices taken modulo \(N\)) are pairwise distinct, and every \(k\)-element subset of \(\{0, \dots, n-1\}\) is the set of these entries for exactly one starting position \(i\).

def IsUniversalCycle (n k : ℕ) (c : Fin (Nat.choose n k) → Fin n) : Prop :=
  ∀ hpos : 0 < Nat.choose n k,
    (∀ i : Fin (Nat.choose n k),
      ((Finset.univ : Finset (Fin k)).image (fun j : Fin k =>
        c ⟨(i.val + j.val) % Nat.choose n k,
          Nat.mod_lt (i.val + j.val) hpos⟩)).card = k)
    ∧ ∀ S : Finset (Fin n), S.card = k →
        ∃! i : Fin (Nat.choose n k),
          (Finset.univ : Finset (Fin k)).image (fun j : Fin k =>
            c ⟨(i.val + j.val) % Nat.choose n k,
              Nat.mod_lt (i.val + j.val) hpos⟩) = S

Sources

• Chung/Diaconis/Graham as cited in Cooper, Combinatorial Problems I Like, Words and Codes bullet 78 [AMR-030-0078].

Used by 1

Used byChung–Diaconis–Graham universal cycle conjecture

DefinitionChung–Diaconis–Graham universal cycle conjecture#✓fully proved

The statement that for every natural number \(k\) there is a natural number \(N\) such that every \(n \ge N\) for which \(k\) divides \(\binom{n-1}{k-1}\) admits a universal cycle for the \(k\)-subsets of \(\{0, \dots, n-1\}\). Here \(n - 1\) and \(k - 1\) are truncated at \(0\), so for \(k = 0\) the divisibility condition reads \(0 \mid 1\) and never holds.

def conjecture : Prop :=
  ∀ k : ℕ, ∃ N : ℕ, ∀ n : ℕ, N ≤ n →
    k ∣ Nat.choose (n - 1) (k - 1) →
    ∃ c : Fin (Nat.choose n k) → Fin n, IsUniversalCycle n k c

Sources

• Chung/Diaconis/Graham as cited in Cooper, Combinatorial Problems I Like, Words and Codes bullet 78 [AMR-030-0078].

Uses 1 · Used by 1

Statement usesUniversal cycle for \(k\)-subsets

Used byExistence of universal cycles for \(k\)-subsets

TheoremExistence of universal cycles for \(k\)-subsets#●ready to prove

For every natural number \(k\) there is a natural number \(N\) such that for every \(n \ge N\) for which \(k\) divides \(\binom{n-1}{k-1}\), there is a universal cycle for the \(k\)-subsets of \(\{0, \dots, n-1\}\). Here \(n - 1\) and \(k - 1\) are truncated at \(0\), so for \(k = 0\) the divisibility condition reads \(0 \mid 1\) and never holds.

This is the Chung–Diaconis–Graham conjecture. Glock, Joos, Kühn and Osthus (Theorem 1.1) proved it for every \(k \ge 2\) in the language of tight Euler tours of the complete \(k\)-uniform hypergraph; the case \(k = 1\) is elementary.

public theorem_wanted conjecture_holds : conjecture

Sources

• Stefan Glock, Felix Joos, Daniela Kühn, Deryk Osthus, Euler tours in hypergraphs, Combinatorica 40 (2020), 679-690; arXiv:1808.07720, https://arxiv.org/abs/1808.07720.

Uses 1

Statement usesChung–Diaconis–Graham universal cycle conjecture

2 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.