Extending prescribed hub colours to an unfriendly partition (Challenge 10)
ProvedTenChallenges.challenge_10_stableComponentExtensioncombinatoricsgraph-theoryinfinite-graphsten-challengesunfriendly-partition
Let be a countable simple graph, let be its infinite-degree vertices (the hubs), and fix a two-colouring of the hubs. Suppose every component of the subgraph obtained by deleting is finite. A colouring is unfriendly at a vertex if it has at least as many neighbours of the opposite colour as of its own colour.
Then extends to an unfriendly colouring of all of if and only if each hub satisfies at least one of the following conditions.
- Infinitely many hub neighbours of have colour different from .
- There are infinitely many distinct components for which one can colour so that every vertex of is unfriendly, using the fixed boundary colours, and some neighbour of in has colour different from .
The colouring in the second condition may depend on both and . Component sizes and the numbers of hubs on their boundaries may be unbounded.
Preamble
import Definitions.Def_TenChallenges_Challenge_10 import Mathlib.Combinatorics.SimpleGraph.Connectivity.Connected universe u
Formal statement
namespace TenChallenges
theorem challenge_10_stableComponentExtension {V : Type u} [Countable V] (G : SimpleGraph V)
(q : V → Bool) (hfinite : ∀ C : (G.induce {v : V | (G.neighborSet v).Finite}).ConnectedComponent, C.supp.Finite) :
let I : Set V := {v | (G.neighborSet v).Infinite}
(∃ c : V → Bool, Set.EqOn c q I ∧ ∀ v, UnfriendlyAt G (fun w => some (c w)) v) ↔
∀ x ∈ I, ({y : V | G.Adj x y ∧ q y ≠ q x} ∩ I).Infinite ∨
{C : (G.induce {v : V | (G.neighborSet v).Finite}).ConnectedComponent |
∃ d : V → Bool,
(Set.EqOn d q I ∧ ∀ y ∈ C.supp, UnfriendlyAt G (fun w => some (d w)) y.val) ∧
∃ y ∈ C.supp, G.Adj x y.val ∧ d y.val ≠ q x}.Infinite := by sorry
end TenChallengesSource
Original component-extension lemma for the unfriendly partition mission in Ten Challenges in Combinatorics, Challenge 10. The local Lean theorem is TenChallenges.Continuation.StableComponents.extension_iff. The canonical challenge is at https://tenchallenges.github.io/ten-challenges/.