Journal of Combinatorics

Volume 8 (2017)

Number 1

Adversarial resilience of matchings in bipartite random graphs

Pages: 79 – 92

DOI: http://dx.doi.org/10.4310/JOC.2017.v8.n1.a4

Authors

Paul Balister (Department of Mathematical Sciences, University of Memphis, Tennessee, U.S.A.)

Stefanie Gerke (Department of Mathematics, Royal Holloway University of London, Egham, United Kingdom)

Andrew McDowell (Department of Mathematics, Royal Holloway University of London, Egham, United Kingdom)

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 + \epsilon) 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 \geq 1$. Let $\epsilon_{r,d} := \big( \frac{r+1}{r}(\log d) / (\frac{d}{r+1}) \big)^{1/r}$. We show that for each $\eta \gt 0$ and for sufficiently large (but fixed) $d$, if $\epsilon \geq (1 + \eta) \epsilon_{r,d}$ then asymptotically almost surely an adversary who deletes $r$ edges incident to each vertex in $A$ cannot destroy all matchings of size $n$. On the other hand if $\epsilon \lt (1 - \eta) \epsilon_{r,d}$, then asymptotically almost surely such an adversary can destroy all matchings of size $n$.

Keywords

resilience, bipartite graph, matching, random graph

Full Text (PDF format)

Published 2 December 2016