Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, February 9, 2010 - 4:30pm

Liviu Ilinca

Rutgers

Location

University of Pennsylvania

DRL 2N36

We use entropy methods to prove asymptotic upper bounds for the number of matchings of a given size l in a graph G with a given degree sequence. In particular, for a d-regular, N-vertices graph G, our bound is best possible up to an error factor exp(o(N)). This represents the best progress to date on the "Upper Matching Conjecture" of Friedland, Krop, Lundow and Markstrom. Joint with Jeff Kahn.