Refuting Perfect Matchings in Spectral Expanders Is Hard
Abstract
Abstract. 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 [ Perfect matching in random graphs is as hard as tseitin, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia] showed that refuting perfect matchings in sparse [Formula: see text]-regular random graphs, in the above proof systems, with high probability requires proofs with degree [Formula: see text]. We extend their result by showing the same lower bound holds for all [Formula: see text]-regular graphs with a mild spectral gap.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Markov Chains and Monte Carlo Methods
Advanced Graph Theory Research
Publication details
- Journal / source
- SIAM Journal on Discrete Mathematics
- Volume
- 40
- Issue
- 2
- Pages
- 905–918
- Publication date
- 12 June 2026
- Language
- EN