Challenge 10: every ordinal clock under finite hub co-occurrence on finite-degree components
ProvedTenChallenges.challenge_10_finiteCooccurrenceLet be a countable simple graph. Partition into the set of finite-degree vertices and the set of infinite-degree vertices (hubs), and let denote the set of connected components of the induced subgraph . Assume that:
- Every connected component is finite, with no uniform upper bound on or on the number of hubs adjacent to .
- Any two distinct infinite-degree vertices in are simultaneously adjacent to vertices of only finitely many components :
Then Partitioner has a winning strategy in the unfriendly partitioning game from the empty partial coloring at every ordinal clock:
At each turn of the game, Challenger announces a vertex and a strictly smaller ordinal clock , and Partitioner supplies a finite extension of the current partial -coloring on which is colored and has at least as many colored neighbors of the opposite color as of its own color.
This establishes the all-ordinal-clocks game consequence of Challenge 10 for countable graphs whose finite-degree subgraph decomposes into finite components of arbitrary size and boundary cardinality with finite pairwise hub overlap, even when infinitely many hubs are present.
Formalization Note. Connected components of are represented as (G.induce {x : V | (G.neighborSet x).Finite}).ConnectedComponent with vertex support C.supp. The vertex type lives in Type u and the ordinal clock r lives in an independent Ordinal.{v}, using the canonical PartitionerWins and emptyPartition definitions from Definitions.Def_TenChallenges_Challenge_10. The unrestricted countable Unfriendly Partition Conjecture 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_finiteCooccurrence {V : Type u} [Countable V] (G : SimpleGraph V)
(hfinite : ∀ C : (G.induce {x : V | (G.neighborSet x).Finite}).ConnectedComponent, C.supp.Finite)
(hshare : ∀ x y : V, (G.neighborSet x).Infinite → (G.neighborSet y).Infinite → x ≠ y →
{C : (G.induce {x : V | (G.neighborSet x).Finite}).ConnectedComponent |
(∃ a ∈ C.supp, G.Adj x a.val) ∧ (∃ b ∈ C.supp, G.Adj y b.val)}.Finite)
(r : Ordinal.{v}) : PartitionerWins G (emptyPartition V) r := by sorry
end TenChallenges