Degree-truncated variable reachability in factor graphs
DefinitionKSATSingleFlip_Connect_GoodReachIn a factor graph, retain the outgoing clause incidences of variables whose full-formula degree is at most , and give variables above the cutoff no outgoing incidences. The degree-truncated variable reachability set consists of variables reachable from a root in at most variable–clause–variable steps through these directed incidences.
Definition code
import Definitions.Def_KSATSingleFlip_Connect_FactorGraph
import Definitions.Def_KSATSingleFlip_Connect_BoundedReach
noncomputable section
open scoped Classical BigOperators
namespace KSATSingleFlip.Connect
/-- The incident clauses of a variable whose full-formula degree is at most D;
variables above the cutoff have no outgoing edges. -/
def goodIncidentClauses {n : ℕ} (Φ : GFormula (Fin n)) (D : ℕ) (u : Fin n) : Finset (Fin Φ.length) :=
if degree Φ u ≤ D then Finset.univ.filter (fun c => u ∈ vbl (Φ.get c)) else ∅
/-- Variables reachable through at most r variable–clause–variable steps
whose departure variables satisfy the degree cutoff. -/
def goodVariableReach {n : ℕ} (Φ : GFormula (Fin n)) (D : ℕ) (u : Fin n) (r : ℕ) : Finset (Fin n) :=
boundedReachBall (fun v => (goodIncidentClauses Φ D v).biUnion (fun c => vbl (Φ.get c))) u r
end KSATSingleFlip.Connect
Source
Auxiliary definition 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