Controllability and matchings in random bipartite graphs

Paul Balister, Stefanie Gerke

Research output: Chapter in Book/Report/Conference proceedingChapter


Motivated by an application in controllability we consider maximum matchings in random bipartite graphs G = (A, B). First we analyse Karp–Sipser's algorithm to determine the asymptotic size of maximum matchings in random bipartite graphs with a fixed degree distribution. We then allow an adversary to delete one edge adjacent to every vertex in A in the more restricted model where each vertex in A chooses d neighbours uniformly at random from B.
Original languageEnglish
Title of host publicationSurveys in Combinatorics 2015
EditorsArtur Czumaj, Agelos Georgakopoulos, Daniel Král, Vadim Lozin, Oleg Pikhurko
PublisherCambridge University Press
Number of pages28
ISBN (Electronic)9781316106853
Publication statusPublished - Jul 2015

Publication series

NameLondon Mathematical Society Lecture Note Series

Cite this