@article{d3a943437d184a5291aa47e86cf7abed,
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 (Formula presented.) with parts (Formula presented.) and (Formula presented.) under various conditions, refining the well-known lower bound due to M. Hall. When (Formula presented.), every vertex in (Formula presented.) has degree at least (Formula presented.), and every vertex in (Formula presented.) has at least (Formula presented.) distinct neighbors, the minimum is (Formula presented.) when (Formula presented.) and is (Formula presented.) when (Formula presented.). When every vertex has at least two neighbors and (Formula presented.), the minimum is (Formula presented.), where (Formula presented.). We also determine the minimum number of maximum matchings in several other situations. We provide a variety of sharpness constructions.",
keywords = "Hall's theorem, bipartite, maximum matching, multigraph",
author = "Kostochka, {Alexandr V.} and West, {Douglas B.} and Zimu Xiang",
note = "The authors thank Jozsef Balogh for a discussion that eventually led to Construction 4.4. We also thank the referees for a very careful reading that caught a number of typographical errors and insufficiently clear explanations. This study was supported by NSF grants DMS-1937241 (RTG) and DMS-2153507 (to A. V. K.), University of Illinois Campus Research Board Award RB24000 (to Z. X.), and National Natural Science Foundation of China grants NSFC 11871439, 11971439, and U20A2068 (to D. B. W.). The authors thank Jozsef Balogh for a discussion that eventually led to Construction 4.4. We also thank the referees for a very careful reading that caught a number of typographical errors and insufficiently clear explanations. This study was supported by NSF grants DMS\u20101937241 (RTG) and DMS\u20102153507 (to A. V. K.), University of Illinois Campus Research Board Award RB24000 (to Z. X.), and National Natural Science Foundation of China grants NSFC 11871439, 11971439, and U20A2068 (to D. B. W.).",
year = "2024",
month = jul,
doi = "10.1002/jgt.23080",
language = "English (US)",
volume = "106",
pages = "525--555",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "3",
}