Unfriendly partitions when a finite set meets every pair of hubs sharing infinitely many components (Challenge 10)
ProvedTenChallenges.challenge_10_finiteKernelCooccurrenceLet be a countable simple graph, let be its set of infinite-degree vertices (the hubs), and let be the components of the subgraph induced by the finite-degree vertices. Let consist of the hubs with a neighbour in . Suppose each is finite and there is a finite set of vertices such that
Then has an unfriendly partition. In this two-colouring, each vertex has at least as many neighbours of the opposite colour as of its own colour. The Partitioner also wins the Challenge 10 game from the empty partition for every ordinal clock.
For example, can consist of two hubs. Either of them can share infinitely many components with the other and with any number of further hubs. The hypotheses allow unbounded component sizes and unbounded numbers of hubs on their boundaries.
import Definitions.Def_TenChallenges_Challenge_10 import Mathlib.Combinatorics.SimpleGraph.Connectivity.Connected universe u v
namespace TenChallenges
theorem challenge_10_finiteKernelCooccurrence {V : Type u} [Countable V] (G : SimpleGraph V)
(K : Set V) (hK : K.Finite)
(hfinite : ∀ C : (G.induce {v : V | (G.neighborSet v).Finite}).ConnectedComponent, C.supp.Finite)
(hshare : ∀ x y : V, x ∉ K → y ∉ K → (G.neighborSet x).Infinite →
(G.neighborSet y).Infinite → x ≠ y →
{C : (G.induce {v : V | (G.neighborSet v).Finite}).ConnectedComponent |
(∃ a ∈ C.supp, G.Adj x a.val) ∧ (∃ b ∈ C.supp, G.Adj y b.val)}.Finite) :
(∃ f : V → Option Bool, ∀ x : V, UnfriendlyAt G f x) ∧
∀ r : Ordinal.{v}, PartitionerWins G (emptyPartition V) r := by sorry
end TenChallenges