Challenge 10: every ordinal clock for an infinite-minimum-degree core with finitely many outside hubs
ProvedTenChallenges.challenge_10_infiniteCoreLet be a countable simple graph and let be a subset of vertices such that:
- Every vertex has infinitely many neighbors inside , i.e., .
- Only finitely many vertices outside have infinite degree in :
Then Partitioner has a winning strategy in the unfriendly partitioning game on starting from the empty partial coloring at every ordinal clock:
At each move, Challenger announces a vertex and a strictly smaller ordinal clock , and Partitioner responds with a finite partial coloring extending the current position so that has at least as many opposite-colored neighbors as same-colored neighbors.
This unifies and strictly generalizes two classical regimes of the Unfriendly Partition Problem: taking recovers the Aharoni-Milner-Prikry theorem for countable graphs with finitely many infinite-degree vertices, while taking recovers countable graphs of infinite minimum degree, and intermediate choices allow an infinite-minimum-degree core attached arbitrarily to infinite locally-finite subgraphs and finitely many exceptional hubs.
Formalization Note. The core condition and outside-hub finiteness are expressed via (G.neighborSet x ∩ R).Infinite and {x : V | x ∉ R ∧ (G.neighborSet x).Infinite}.Finite. The vertex universe u and clock universe v are independent, using PartitionerWins and emptyPartition from Definitions.Def_TenChallenges_Challenge_10.
import Definitions.Def_TenChallenges_Challenge_10 universe u v
namespace TenChallenges
theorem challenge_10_infiniteCore {V : Type u} [Countable V] (G : SimpleGraph V)
(R : Set V) (hR : ∀ x ∈ R, (G.neighborSet x ∩ R).Infinite)
(hOutside : {x : V | x ∉ R ∧ (G.neighborSet x).Infinite}.Finite)
(r : Ordinal.{v}) : PartitionerWins G (emptyPartition V) r := by sorry
end TenChallenges