An induced walk ball witnesses a first finite loss (Challenge 10)
ProvedTenChallenges.challenge_10_losingInducedBallcombinatoricsgraph-theoryinfinite-graphsten-challengesunfriendly-partition
Let be a simple graph and let be a natural number. Assume Partitioner wins from the empty partial partition at every natural clock and loses from the empty partial partition at clock . Then there is a vertex such that Partitioner also loses from the empty partial partition at clock on the graph induced by the vertices reachable from by a walk of length at most .
Preamble
import Definitions.Def_TenChallenges_Challenge_10 import Mathlib.Combinatorics.SimpleGraph.Maps import Mathlib.Combinatorics.SimpleGraph.Walk.Operations universe u v
Formal statement
namespace TenChallenges
theorem challenge_10_losingInducedBall {V : Type u} (G : SimpleGraph V) (n : ℕ)
(hprev : ∀ m : ℕ, m < n → PartitionerWins G (emptyPartition V) (m : Ordinal.{v}))
(hloss : ¬ PartitionerWins G (emptyPartition V) (n : Ordinal.{v})) :
∃ a : V,
let B : Set V := {x | ∃ w : G.Walk a x, w.length ≤ 2 ^ n - 2}
¬ PartitionerWins (G.induce B) (emptyPartition B) (n : Ordinal.{v}) := by sorry
end TenChallengesSource
Ten Challenges in Combinatorics, Challenge 10 (https://tenchallenges.github.io/ten-challenges/). This is a finite-clock reduction for its partitioning game.