This work studies the complexity of refuting the existence of a perfect matching in spectral expanders with an odd number of vertices, in the Polynomial Calculus (PC) and Sum of Squares (SoS) proof system.
Austrin and Risse [SODA, 2021] showed that refuting perfect matchings in sparse $d$-regular \emph{random} graphs, in the above proof systems, with high probability requires proofs with degree $\Omega(n/\log n)$.
We extend their result by showing the same lower bound holds for \emph{all} $d$-regular graphs with a mild spectral gap.
As a direct consequence, we also positively resolve the open problem posed by Buss and Nordström, which asks, "Are even colouring formulas over expander graphs hard for polynomial calculus over fields of characteristic distinct from 2 ?"