A proof of the Upper Matching Conjecture for large graphs

Abstract: We show 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 \over 2d$ copies of the complete $d$-regular bipartite graph maximises the number of independent sets and matchings of any given size over all $d$-regular graphs on $n$ vertices. For the proof, we'll discuss two different approaches to these problems, both inspired by statistical physics. This is joint work with Ewan Davies and Will Perkins.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).