Challenge 10: every ordinal clock when finite-degree components touch at most three hubs
ProvedTenChallenges.challenge_10_threeBoundaryLet be a countable simple graph, let be the set of finite-degree vertices, let be the set of infinite-degree vertices (hubs), and let denote the set of connected components of the induced subgraph . For each component , write for the set of hubs adjacent to at least one vertex of . Assume that:
- Every connected component is finite, with no uniform upper bound on .
- Every connected component is adjacent to at most three infinite-degree vertices:
Then Partitioner wins the unfriendly partitioning game on starting from the empty partial coloring for every ordinal clock:
In each round, Challenger selects a vertex and a strictly smaller ordinal , and Partitioner supplies a finite extension of the current partial -coloring under which is colored and has at least as many opposite-colored neighbors as same-colored neighbors.
This settles all ordinal game clocks of Challenge 10 when every component of is finite and meets at most three hubs, complementing the finite-co-occurrence regime by allowing pairs and triples of hubs to share infinitely many components.
Formalization Note. For each connected component C of G.induce {x : V | (G.neighborSet x).Finite}, the hub-boundary bound is formalized via Set.ncard ≤ 3. The vertex universe u and ordinal clock universe v are independent, targeting PartitionerWins G (emptyPartition V) r from Definitions.Def_TenChallenges_Challenge_10; the unrestricted countable case remains open.
import Definitions.Def_TenChallenges_Challenge_10 import Mathlib.Combinatorics.SimpleGraph.Connectivity.Connected import Mathlib.Data.Set.Card universe u v
namespace TenChallenges
theorem challenge_10_threeBoundary {V : Type u} [Countable V] (G : SimpleGraph V)
(hfinite : ∀ C : (G.induce {x : V | (G.neighborSet x).Finite}).ConnectedComponent, C.supp.Finite)
(hboundary : ∀ C : (G.induce {x : V | (G.neighborSet x).Finite}).ConnectedComponent,
{x : V | (G.neighborSet x).Infinite ∧ ∃ a ∈ C.supp, G.Adj x a.val}.ncard ≤ 3)
(r : Ordinal.{v}) : PartitionerWins G (emptyPartition V) r := by sorry
end TenChallenges