Controllability and matchings in random bipartite graphs

Paul Balister, Stefanie Gerke

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

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
Chapter3
Pages119-146
Number of pages28
Volume424
ISBN (Electronic)9781316106853
DOIs
Publication statusPublished - Jul 2015

Publication series

NameLondon Mathematical Society Lecture Note Series
Volume424

Cite this