Discrete Applied Mathematics Seminar by Douglas B. West: "Sharp Lower Bounds for the Number of Maximum Matchings in Bipartite Multigraphs"

Speaker:

Douglas B. West, Zhejiang Normal University and University of Illinois

Title: Sharp lower bounds for the number of maximum matchings in bipartite multigraphs

Abstract: We study the minimum number of maximum matchings in a bipartite multigraph \(G\) with parts \(X\) and \(Y\) under various conditions, refining the well-known lower bound due to M.~Hall. When \(|X|=n\), every vertex in \(X\) has degree at least \(k\), and every vertex in \(X\) has at least \(r\) distinct neighbors, the minimum is \(r!(k-r+1)\) when \(n\ge r\) and is \([r+n(k-r)](r-1)!/(r-n)!\) when \(n<r\).

When every vertex has at least two neighbors and \(|Y|-|X|=t\ge0\), the minimum is \([(n-1)t+2+b](t+1)\), where \(b=|E(G)|-2(n+t)\). We have also determined the minimum number of maximum matchings in several other situations. We provide a variety of sharpness constructions.

These results are joint work with Alexandr V. Kostochka and Zimu Xiang.

 

Discrete Applied Math Seminar

Request Zoom Link