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+ε)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.