EUVIMEDEUVIMED entdecken
Crossref

Refuting Perfect Matchings in Spectral Expanders Is Hard

Ari Biswas, Rajko Nenadov

SIAM Journal on Discrete Mathematics · 30.06.2026 · 40 (2) · 905-918

DOI: 10.1137/25m1767200 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 12.06.2026. Verfasst von Ari Biswas und 1 weiteren Autor:innen. Die Arbeit nennt 36 Literaturangaben. Gefördert von: Marsden Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Marsden Fund

Zitieren

APA

Biswas, A., & Nenadov, R. (2026). Refuting Perfect Matchings in Spectral Expanders Is Hard. SIAM Journal on Discrete Mathematics, 40(2), 905-918. https://doi.org/10.1137/25m1767200

Vancouver

Biswas A, Nenadov R. Refuting Perfect Matchings in Spectral Expanders Is Hard. SIAM Journal on Discrete Mathematics. 2026;40(2):905-918. doi:10.1137/25m1767200

BibTeX
@article{Biswas2026,
  author = {Biswas, Ari and Nenadov, Rajko},
  title = {Refuting Perfect Matchings in Spectral Expanders Is Hard},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2026},
  volume = {40},
  number = {2},
  pages = {905--918},
  doi = {10.1137/25m1767200}
}
Kostenlos starten →