Finite directed reachability balls
DefinitionKSATSingleFlip_Connect_BoundedReachFor a directed graph specified by finite outgoing-neighbor sets, is the finite set of vertices reachable from in at most steps, including . It is defined recursively by adjoining and all outgoing neighbors of the preceding ball.
Definition code
import Mathlib
namespace KSATSingleFlip.Connect
/-- Vertices reachable in at most r directed steps from root, with finite
neighbor lists. The root is included even for r=0. -/
def boundedReachBall {V : Type} [DecidableEq V] (neighbors : V → Finset V) (root : V) : ℕ → Finset V
| 0 => {root}
| r+1 => {root} ∪ (boundedReachBall neighbors root r).biUnion neighbors
end KSATSingleFlip.Connect
Source
Auxiliary definition for the path-counting proof of Lemma 2.7 in Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, printed pp. 12–13 (PDF pp. 14–15), STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf