Unfriendly partitions for finite component interfaces and locally finite hub sharing (Challenge 10)
ProvedTenChallenges.challenge_10_finiteComponentInterfacescombinatoricsgraph-theoryinfinite-graphsten-challengesunfriendly-partition
Let be a countable simple graph and call its infinite-degree vertices hubs. Assume that for each component of the subgraph induced by the finite-degree vertices there are only finitely many edges between and the hubs. On the hubs, form a graph by joining two distinct hubs when infinitely many finite-degree components contain a neighbour of both. Assume is locally finite.
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 finite-degree components may be infinite. The sharing graph may also have infinite connected components and triangles.
Preamble
import Definitions.Def_TenChallenges_Challenge_10 import Mathlib.Combinatorics.SimpleGraph.Connectivity.Connected universe u v
Formal statement
namespace TenChallenges
theorem challenge_10_finiteComponentInterfaces {V : Type u} [Countable V] (G : SimpleGraph V)
(hinterface : ∀ C : (G.induce {x : V | (G.neighborSet x).Finite}).ConnectedComponent,
{e : V × V | (G.neighborSet e.1).Infinite ∧ e.2 ∈ Subtype.val '' C.supp ∧ G.Adj e.1 e.2}.Finite)
(R : SimpleGraph {x : V | (G.neighborSet x).Infinite})
(hAdj : ∀ x y, R.Adj x y ↔ x ≠ 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)}.Infinite)
(hloc : ∀ x, (R.neighborSet x).Finite) :
(∃ f : V → Option Bool, ∀ x : V, UnfriendlyAt G f x) ∧
∀ r : Ordinal.{v}, PartitionerWins G (emptyPartition V) r := by sorry
end TenChallengesSource
Ten Challenges in Combinatorics, Challenge 10 (https://tenchallenges.github.io/ten-challenges/). Finite-interface extension of the locally finite sharing theorem at https://prove2.me/theorems/a1003729-ae62-4f12-af15-dbbb49a96beb.