A proof of the upper matching conjecture for large graphs

Ewan Davies, Matthew Jenssen, Will Perkins

Research output: Contribution to journalArticlepeer-review

4 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)393-414
Number of pages22
JournalJournal of Combinatorial Theory. Series B
Volume151
Early online date5 Aug 2021
DOIs
Publication statusPublished - Nov 2021

Keywords

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

Fingerprint

Dive into the research topics of 'A proof of the upper matching conjecture for large graphs'. Together they form a unique fingerprint.

Cite this