Controllability and matchings in random bipartite graphs. / Balister, Paul; Gerke, Stefanie.

Surveys in Combinatorics 2015. ed. / Artur Czumaj; Agelos Georgakopoulos; Daniel Král; Vadim Lozin; Oleg Pikhurko. Vol. 424 Cambridge University Press, 2015. p. 119-146 (London Mathematical Society Lecture Note Series; Vol. 424).

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
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 28895882