AFTD Auto-Formalizing Theoretical Domains

cycle_not_proportionally_two_choosable

theoremverifiedformalization

For every integer n ≥ 3, the simple n-cycle C_n is not proportionally 2-choosable: it is not the case that for every finite color palette α and every assignment L of 2 colors to each vertex, there exists a proper coloring f of C_n with f(v) ∈ L(v) for all v such that for every color c : α, the number of vertices colored c is either ⌊η_L(c)/2⌋ or ⌈η_L(c)/2⌉, where η_L(c) is the number of vertices whose list contains c.

Statement

theorem cycle_not_proportionally_two_choosable (n : ℕ) (hn : 3 ≤ n) :
    ¬ ∀ (α : Type) [Fintype α] [DecidableEq α] (L : Fin n → Finset α),
      (∀ v, (L v).card = 2) →
      ∃ f : (SimpleGraph.cycleGraph n).Coloring α,
        (∀ v, f v ∈ L v) ∧
        ∀ c : α,
          let η := (Finset.univ.filter (fun v => c ∈ L v)).card
          let uses := (Finset.univ.filter (fun v => f v = c)).card
          uses = η / 2 ∨ uses = η ⌈/⌉ 2
Formalizes
scout/2610-33914-improved-bounds-on-proportional-choice-numbers.md:115
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

Read back from the Lean

For every natural number $n \ge 3$, the cycle graph on $n$ vertices is not proportionally 2-choosable: that is, it is not the case that for every finite type $\alpha$ with decidable equality and every list assignment $L : \text{Fin } n \to \text{Finset } \alpha$ satisfying $|L(v)| = 2$ for all $v \in \text{Fin } n$, there exists a proper vertex coloring $f$ of the cycle graph $C_n$ with colors in $\alpha$ such that: 1. For every vertex $v \in \text{Fin } n$, $f(v) \in L(v)$, and 2. For every color $c \in \alpha$, the number of vertices colored $c$ (i.e., $|\{v \in \text{Fin } n \mid f(v) = c\}|$) is equal to $\lfloor \eta(c) / 2 \rfloor$ or $\lceil \eta(c) / 2 \rceil$, where $\eta(c) = |\{v \in \text{Fin } n \mid c \in L(v)\}|$ is the number of vertices whose list contains $c$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by case analysis on the parity of the cycle length n. The claim is dispatched in each case by invoking the specialized lemmas for even cycles (cycle_not_proportionally_two_choosable_of_even) and odd cycles (cycle_not_proportionally_two_choosable_of_odd).

  1. It suffices to prove the result separately when n is even and when n is odd.

    We split into cases based on the parity of n using Nat.even_or_odd.

    line 11

    uses Nat.even_or_odd

      rcases Nat.even_or_odd n with hn_even | hn_odd
  2. The cycle C_n is not proportionally 2-choosable when n is even.

    In the case where n is even, the result is directly supplied by cycle_not_proportionally_two_choosable_of_even.

    line 12

    uses cycle_not_proportionally_two_choosable_of_even

      · exact cycle_not_proportionally_two_choosable_of_even n hn hn_even
  3. The cycle C_n is not proportionally 2-choosable when n is odd.

    In the case where n is odd, the result is directly supplied by cycle_not_proportionally_two_choosable_of_odd.

    line 13

    uses cycle_not_proportionally_two_choosable_of_odd

      · exact cycle_not_proportionally_two_choosable_of_odd n hn hn_odd
Nat.even_or_odd
Every natural number is either even or odd: ∀ n, Even n ∨ Odd n.
cycle_not_proportionally_two_choosable_of_even
For every even natural number n ≥ 3, the simple cycle C_n is not proportionally 2-choosable.
cycle_not_proportionally_two_choosable_of_odd
For every odd natural number n ≥ 3, the simple cycle C_n is not proportionally 2-choosable.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- No simple cycle C_n (n >= 3) is proportionally 2-choosable (arXiv:2610.33914 Theorem 4). -/theorem cycle_not_proportionally_two_choosable (n : ℕ) (hn : 3 ≤ n) :    ¬ ∀ (α : Type) [Fintype α] [DecidableEq α] (L : Fin n → Finset α),      (∀ v, (L v).card = 2) →      ∃ f : (SimpleGraph.cycleGraph n).Coloring α,        (∀ v, f v ∈ L v) ∧        ∀ c : α,          let η := (Finset.univ.filter (fun v => c ∈ L v)).card          let uses := (Finset.univ.filter (fun v => f v = c)).card          uses = η / 2 ∨ uses = η ⌈/⌉ 2 := by  rcases Nat.even_or_odd n with hn_even | hn_odd  · exact cycle_not_proportionally_two_choosable_of_even n hn hn_even  · exact cycle_not_proportionally_two_choosable_of_odd n hn hn_odd
See it in the graphDiscuss this resultChallenge it