报告题目：Sharp lower bounds for the number of maximum matchings in bipartite multigraphs

报告人：Douglas B. West, Zhejiang Normal University and University of Illinois

报告时间：2024年3月8日（周五）15:00-16:00

报告地点：20-202

报告摘要：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.