Geometric bound for degree-truncated factor-graph reachability
ProvedKSATSingleFlip.Connect.good_variable_reach_cardFor a finite formula whose clause scopes have cardinality at most , retain an outgoing variable–clause incidence only when the departure variable has full-formula degree at most . The number of variables reachable from any root in at most variable–clause–variable steps is at most . This is a supporting finite-graph bound for Lemma 2.7; it does not itself prove the lemma’s trimmed-ball or sensitivity claims.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_GoodReach open scoped Classical BigOperators
Formal statement
namespace KSATSingleFlip.Connect
theorem good_variable_reach_card {n : ℕ} (Φ : GFormula (Fin n)) (D k : ℕ)
(hwidth : ∀ c : Fin Φ.length, (vbl (Φ.get c)).card ≤ k) (u : Fin n) (r : ℕ) :
(goodVariableReach Φ D u r).card ≤ ∑ i ∈ Finset.range (r+1), (D*k)^i := by
sorry
end KSATSingleFlip.Connect
Source
Auxiliary result for Lemma 2.7 of 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