Spectral Statistics of the Conflict Laplacian of Random k-SAT Instances

To every instance of the random k-satisfiability problem one may associate its conflict graph, whose vertices are the Boolean variables and whose edges join pairs of variables that co-occur in a common clause. We undertake a systematic and rigorous study of the spectral statistics of the associated combinatorial conflict Laplacian L_Φn when the instance is drawn from the uniform ensemble μ(k)_{n,α} with m = ⌊αn⌋ clauses over n variables. We first show that the conflict graph is, to leading order, an Erdős–Rényi graph G(n, p_n) with edge density p_n = c/n, where c := αk(k−1) is the conflict density; we compute all lower-order edge correlations explicitly and show they are of order O(n^{−3}). Exploiting this comparison, we establish three main results. (I) Limiting spectral law: the empirical spectral distribution of A_Φ converges weakly, in probability, to the Poisson–Galton–Watson law μ_c, whose moments are given by a tree-walk expansion. (II) Phase transition: the algebraic connectivity λ_2(L_Φn) undergoes a phase transition at the conflict density c = 1, in exact lockstep with the emergence of the giant component in G(n, c/n); the internal spectral gap of the giant component is Θ((log n)^{−2}) for c > 1. (III) Concentration: every spectral functional of L_Φn that is 2(k−1)-Lipschitz under single-clause resampling (including λ_2, λ_n, and the giant gap) obeys a sub-Gaussian McDiarmid concentration inequality, with deviation scale O(√(n log n)). The results are purely combinatorial and probabilistic, and require no hypothesis on the satisfiability of the underlying instance.