Adversarial resilience of matchings in bipartite random graphs

Paul Balister, Stefanie Gerke, Andrew McDowell

Research output: Contribution to journalArticlepeer-review

74 Downloads (Pure)

Abstract

We study the problem of finding the largest matching in a random bipartite graph after an adversary deleted some edges. The bipartite graph consists of a partition class A of size n and a partition class B of size (1+ε)n. Each vertex in A chooses d neighbours in B uniformly and independently at random, and an adversary then deletes, for each vertex v in A, at most r edges incident to v, for some fixed r≥ 1. We show that forsufficiently large (but fixed) d and sufficiently large n, if ε>εrd:=((r+1)/r (\log d)/binom{d}{r+1})1/r,then asymptotically almost surely an adversary who deletes r edges incident to each vertex in A cannot destroy all matchings ofsize n. On the other hand if ε<εrd,then asymptotically almost surely such an adversary can destroy all matchings of size n.
Original languageEnglish
Pages (from-to)79-92
Number of pages14
JournalJournal of Combinatorics
Volume8
Issue number1
DOIs
Publication statusPublished - 2 Dec 2016

Cite this