A proof of the upper matching conjecture for large graphs

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

Abstract

We prove that the ‘Upper Matching Conjecture’ of Friedland, Krop, and Markström and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enough graphs as a function of the degree. That is, for every d and every large enough n divisible by 2d, a union of copies of the complete d-regular bipartite graph maximizes the number of independent sets and matchings of size k for each k over all d-regular graphs on n vertices. To prove this we utilize the cluster expansion for the canonical ensemble of a statistical physics spin model, and we give some further applications of this method to maximizing and minimizing the number of independent sets and matchings of a given size in regular graphs of a given minimum girth.

Details

Original languageEnglish
Pages (from-to)393-414
Number of pages22
JournalJournal of Combinatorial Theory. Series B
Volume151
Early online date5 Aug 2021
Publication statusE-pub ahead of print - 5 Aug 2021

Keywords

  • Matchings, Independent sets, Matching polynomial, Independence polynomial, Upper matching conjecture, Cluster expansion