General Events - Department of Mathematics

View Full Calendar

Graph Theory & Combinatorics Seminar

Event Type
Ceremony/Service
Sponsor
Department of Mathematics
Location
Altgeld 241
Date
Dec 6, 2022   1:00 pm  
Speaker
Zimu Xiang (UIUC)
Views
27
Zimu Xiang (UIUC)
Sharp lower bound for the number of maximum matchings in bipartite multigraphs
*************************************************************************
 
Abstract: The well-known Marshall Hall's Theorem gives a sharp lower bound on the number of maximum matchings in bipartite graph. We generalize this bound to bipartite multigraph and characterize all the extremal examples. We also look into multigraphs with different conditions, determine a sharp lower bound and provide extremal constructions for each case.
link for robots only