Bounded-degree factor-ball cardinality bounds
ProvedKSATSingleFlip.Connect.lemma_2_7_ball_boundsLet every clause have at most variables, with , and set
If the radius- factor ball around a variable is a tree and every variable in it has full-formula degree at most , then the number of variable and clause vertices in that ball is at most . For any fixed variable , at most such locally tree-structured balls contain . These are the two cardinality statements in (2.1); the separate clause-insertion/deletion sensitivity statement of Lemma 2.7 is not included.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_FactorGraph open scoped Classical BigOperators
Formal statement
namespace KSATSingleFlip.Connect
/-- The two cardinality bounds in (2.1) of Lemma 2.7. The separate
clause-insertion sensitivity conclusion is not part of this target. -/
theorem lemma_2_7_ball_bounds {n : ℕ} (Φ : GFormula (Fin n)) (k r D : ℕ)
(hk : 1 ≤ k) (hr : 1 ≤ r) (hD : 1 ≤ D)
(hwidth : ∀ c : Fin Φ.length, (vbl (Φ.get c)).card ≤ k) :
(∀ v, LocallyTree Φ v r D →
(ballVars Φ v r).card + (ballIdx Φ v r).card ≤
∑ h ∈ Finset.range (r + 2), (k * D)^h) ∧
(∀ u, (Finset.univ.filter fun v : Fin n =>
LocallyTree Φ v r D ∧ u ∈ ballVars Φ v r).card ≤
∑ h ∈ Finset.range (r + 2), (k * D)^h) := by
sorry
end KSATSingleFlip.Connect
Source
Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, Lemma 2.7, equation (2.1), printed pp. 12–13 (PDF pp. 14–15), STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf