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\ge 0$, 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