Unfriendly partitions for finite blocks of hubs with finite co-occurrence between blocks (Challenge 10)
ProvedTenChallenges.challenge_10_finiteBlockCooccurrenceLet be a countable simple graph. Call its infinite-degree vertices hubs and let be the set of connected components of the subgraph induced by its finite-degree vertices. Suppose every is finite. Partition the hubs into finite blocks and suppose that any two hubs in different blocks each have a neighbour in the same component for only finitely many .
Then has an unfriendly partition, a two-colouring in which each vertex has at least as many opposite-coloured neighbours as same-coloured neighbours. The Partitioner also wins the Challenge 10 game from the empty partition for every ordinal clock.
The blocks may have unbounded finite sizes. Hubs in the same block may share infinitely many components, and the hypothesis allows infinitely many such blocks.
import Definitions.Def_TenChallenges_Challenge_10 import Mathlib.Combinatorics.SimpleGraph.Connectivity.Connected universe u v w
namespace TenChallenges
theorem challenge_10_finiteBlockCooccurrence {V : Type u} {I : Type v}
[Countable V] [Countable I] (G : SimpleGraph V)
(hfinite : ∀ C : (G.induce {x : V | (G.neighborSet x).Finite}).ConnectedComponent, C.supp.Finite)
(block : {h : V | (G.neighborSet h).Infinite} → I)
(hblocks : ∀ i : I, {h : {h : V | (G.neighborSet h).Infinite} | block h = i}.Finite)
(hshare : ∀ x y : {h : V | (G.neighborSet h).Infinite}, block x ≠ block y →
{C : (G.induce {x : V | (G.neighborSet x).Finite}).ConnectedComponent |
(∃ a ∈ C.supp, G.Adj x.val a.val) ∧ (∃ b ∈ C.supp, G.Adj y.val b.val)}.Finite) :
(∃ f : V → Option Bool, ∀ x : V, UnfriendlyAt G f x) ∧
∀ r : Ordinal.{w}, PartitionerWins G (emptyPartition V) r := by sorry
end TenChallenges