cycle_not_proportionally_two_choosable
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
- cycle_not_proportionally_two_choosable_of_oddFor every odd integer n ≥ 3, the simple n-cycle C_n is not proportionally 2-choosable.
- cycle_not_proportionally_two_choosable_of_evenFor every even integer n ≥ 3, the simple n-cycle C_n is not proportionally 2-choosable.
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).
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.
uses
Nat.even_or_oddrcases Nat.even_or_odd n with hn_even | hn_odd
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.
uses
cycle_not_proportionally_two_choosable_of_even· exact cycle_not_proportionally_two_choosable_of_even n hn hn_evenThe 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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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