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 requires proofs with degree $\Omega(n/\log n)$ on average. We extend their result by showing the same lower bound holds for all $d$-regular graphs with a mild spectral gap.Additionally, as Austrin and Risse do for random graphs, we show that the hardness of refuting a more general class of formulae, which includes both perfect matchings and even-colouring formulas, also reduces to the hardness of refuting perfect matchings in spectral expanders, thereby settling an open problem of Buss and Nordstrom.
Comment: In March 2024, when I was first introduced to this problem, I was largely unaware of the field of proof complexity, or even the combinatorial techniques used to prove the hardness result in this paper. I owe a huge debt of gratitude to Rajko for being patient with me, and re-drafting numerous poorly written proofs in the early stages of this project. He did not need to do this. I was not his student, nor were we related in any funding capacity. Prior to working on this paper, we were strangers, and we'd been put in touch owing to the fact that we were married to kiwis. Still, he took the time to meet and guide me through his ideas; and this ended up being the result I was most proud of during the course of my doctoral degree. This project would be impossible without his help.