Challenge 10: all ordinal clocks on graphs with every degree infinite
ProvedTenChallenges.challenge_10_infiniteDegreecombinatoricsgraph-theoryinfinite-graphsten-challenges
Let be a simple graph such that every vertex has infinitely many neighbors, and let be a partial coloring with finite colored domain. For every ordinal , Partitioner has a winning strategy in the unfriendly partition game starting from :
At each move, Challenger chooses a vertex and a strictly smaller ordinal clock. Partitioner must extend the current finite coloring so that the queried vertex has at least as many opposite-colored neighbors as same-colored neighbors. In particular, the conclusion holds from the empty coloring at every ordinal clock. This proves the infinite-degree-at-every-vertex case of Challenge 10; no countability assumption on is required.
Preamble
import Definitions.Def_TenChallenges_Challenge_10 universe u v
Formal statement
namespace TenChallenges
theorem challenge_10_infiniteDegree {V : Type u} (G : SimpleGraph V)
(hG : ∀ x, (G.neighborSet x).Infinite) (r : Ordinal.{v})
{f : V → Option Bool} (hf : HasFiniteDomain f) : PartitionerWins G f r := by sorry
end TenChallengesSource
Ten Challenges in Combinatorics, Challenge 10; infinite-degree special case using the canonical unfriendly-partition game definitions. https://tenchallenges.github.io/ten-challenges/