Refuting Perfect Matchings in Spectral Expanders is Hard

2025/06/09 by Biswas, Ari, Nenadov, Rajko
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2506.07700

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 [SODA, 2021] showed that refuting perfect matchings in sparse d-regular random graphs, in the above proof systems, with high probability requires proofs with degree Ω(n/log n). We extend their result by showing the same lower bound holds for all d-regular graphs with a mild spectral gap.

Citations

• Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
• Routing permutations on spectral expanders via matchings
• Strongly refuting all semi-random Boolean CSPs
• Rolling backwards can move you forward: on embedding problems in sparse expanders
• Complete minors in graphs without sparse cuts
• Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs
• Sum of squares lower bounds for refuting any CSP
• The Factorization of Linear Graphs

Related

• Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
• Counting Perfect Matchings in Dense Graphs Is Hard
• Counting matchings in irregular bipartite graphs and random lifts
• Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap
• Spectrum preserving short cycle removal on regular graphs