Geometric bound for a bounded-branching reachability ball
ProvedKSATSingleFlip.Connect.bounded_reach_ball_cardIn any directed graph represented by finite outgoing-neighbor sets of size at most , the set of vertices reachable from a root in at most steps has cardinality at most . No finiteness assumption on the ambient vertex type is required.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_BoundedReach open scoped Classical BigOperators
Formal statement
namespace KSATSingleFlip.Connect
/-- A degree-d finite reachability ball has at most a geometric number of vertices. -/
theorem bounded_reach_ball_card {V : Type} [DecidableEq V] (neighbors : V → Finset V)
(root : V) (d r : ℕ) (hd : ∀ u, (neighbors u).card ≤ d) :
(boundedReachBall neighbors root r).card ≤ ∑ i ∈ Finset.range (r + 1), d^i := by
sorry
end KSATSingleFlip.Connect
Source
Auxiliary path-counting bound for Lemma 2.7 in Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, printed pp. 12–13, STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf