Bounded two-step reachability in a bipartite incidence system
ProvedKSATSingleFlip.Connect.bounded_bipartite_reach_cardIn a finite-neighbor bipartite incidence system, suppose every variable has at most incident clauses and every clause has at most variables. Starting from one variable, at most variables are reachable by at most variable–clause–variable steps. This provides a path-counting ingredient for the factor-ball bounds in Lemma 2.7.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_BoundedReach open scoped Classical BigOperators
Formal statement
namespace KSATSingleFlip.Connect
/-- Two-step reachability in a bounded bipartite incidence system. -/
theorem bounded_bipartite_reach_card {V C : Type} [DecidableEq V] [DecidableEq C]
(clauses : V → Finset C) (scope : C → Finset V)
(root : V) (D k r : ℕ)
(hD : ∀ v, (clauses v).card ≤ D) (hk : ∀ c, (scope c).card ≤ k) :
(boundedReachBall (fun v => (clauses v).biUnion scope) root r).card ≤
∑ i ∈ Finset.range (r + 1), (D*k)^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