Challenge 10: every ordinal clock with finitely many infinite-degree vertices
ProvedTenChallenges.challenge_10_finiteInfiniteDegreeLet be a countable simple graph such that only finitely many vertices have infinite degree. Then Partitioner wins the unfriendly partitioning game from the empty partial coloring for every ordinal clock:
At each turn, Challenger chooses a vertex and a strictly smaller ordinal clock. Partitioner supplies a finite extension of the current partial coloring that makes the queried vertex have at least as many colored neighbors of the opposite color as of its own color.
This is the ordinal-game consequence of the Aharoni–Milner–Prikry theorem that graphs with finitely many infinite-degree vertices admit an unfriendly partition. It includes the locally finite case and allows arbitrary interaction between finite-degree vertices and the finitely many infinite-degree vertices.
Formalization note: the vertex and clock universes are independent. The statement concerns the canonical PartitionerWins and emptyPartition definitions. It does not cover graphs with infinitely many infinite-degree vertices.
import Definitions.Def_TenChallenges_Challenge_10 universe u v
namespace TenChallenges
theorem challenge_10_finiteInfiniteDegree {V : Type u} [Countable V]
(G : SimpleGraph V)
(hI : {x : V | (G.neighborSet x).Infinite}.Finite)
(r : Ordinal.{v}) : PartitionerWins G (emptyPartition V) r := by sorry
end TenChallenges