Adversarial resilience of matchings in bipartite random graphs. / Balister, Paul; Gerke, Stefanie; McDowell, Andrew.

In: Journal of Combinatorics, Vol. 8, No. 1, 02.12.2016, p. 79-92.

Research output: Contribution to journalArticle

Published

Documents

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

ID: 26304004