2020/04/14 by Davies, Ewan, Jenssen, Matthew, Perkins, Will · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2004.06695
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 n/(2d) 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.