2026/07/19 by Vaibhav Suvagiya · 1 citation
#math.CO #cs.DM #math.SP
For a signing σ of a d-regular graph, the spectrum of Aσ depends only on the signs of cycles. We study the affine \mathbb F2 family of signings making every short even cycle unbalanced, and show that averaging over it converts the sign problem of the Bilu-Linial conjecture into a counting problem: a master identity expresses the family-averaged trace as a parity-weighted sum over wrap classes confined to the span W of the constraint cycles, and the family-averaged Ihara L-function diagonalizes so that every prime whose parity escapes W contributes the Ramanujan rate √(d-1) automatically. Uniform averaging over all signings, by contrast, provably cannot certify a spectral radius below the Kesten profile. We prove matched upper and lower bounds for the confined walk counts, a doubling injection from below, and from above an ear-decomposition encoding in which the number of fresh runs of a non-backtracking walk equals the cycle rank of its support, combined with a window lemma for bicycle-free graphs and a rank bound via the Moore bound for irregular graphs. Consequences include ε-versions of the Bilu-Linial conjecture: every d-regular graph that is subcritical at scale log n, and every d-regular graph bicycle-free at radius Cloglog n/δ, admits a signing in the parity family with ρ(Aσ)≤2√(d-1)(1+Cδlog(1/δ))(1+o(1)). We further identify the necessary hypotheses exactly (Kd-trapping; tree-burst gadgets), give an exact certificate on the hypercube, and record a decisive obstruction to two-sided interlacing: \mathbb Eσdet(xI-Aσ2) is not real-rooted, already for the quadrilateral, where it equals (x2-4x+2)2+4.