Adversarial resilience of matchings in bipartite random graphs

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