Extremal number of edges in bipartite graphs as a function of the topological connectivity of the matching complex

Extremal number of edges in bipartite graphs as a function of the topological connectivity of the matching complex

-
Eli Berger, University of Haifa
Fine Hall 224

The topological connectivity of the matching complex of a graph has been found to be a useful tool in solving many kinds of combinatorial problems such as finding rainbow matchings in edge-colored graphs. In this talk I find the extremal cases for this parameter in bipartite graphs in terms of the number of edges and the number of vertices in each side. More accurately, I answer the following question: given the topological connectivity of the matching complex and the number of vertices in each side of a bipartite graph, what is the maximum possible number of edges? I answer this question and find what the extremal graphs for this problem look like.