Abstract

Motivated by an application in controllability we consider maximum matchings in random bipartite graphs G = (A, B). First we analyse Karp–Sipser's algorithm to determine the asymptotic size of maximum matchings in random bipartite graphs with a fixed degree distribution. We then allow an adversary to delete one edge adjacent to every vertex in A in the more restricted model where each vertex in A chooses d neighbours uniformly at random from B.

1 Introduction

We are interested in finding large matchings in random bipartite graphs. The motivation comes in part from recent work by Liu, Slotine, and Barabási [16], in which they used a characterisation by Lin [15] of structural controllability to show how large matchings in random bipartite graphs play a crucial role in obtaining bounds on the number of nodes needed to control directed networks. We will give a short description of this connection in Section 2.

Matchings in bipartite graphs are a classical problem in graph theory. The famous theorem of Hall [10] states that a bipartite graph with vertex sets V1 and V2 contains a matching of size |V1| if and only if for every set S ⊆ V1 we have |S| ≤ |Γ(S)| where Γ(S) is the neighbourhood of S. One can use this characterisation to show that in a random bipartite graph G(n, n, p) with vertex sets V1 and V2 of the same size n where each of the possible n2 edges is present with probability p independent of the presences or absence of all other edges, with high probability (whp) there is a matching of size n if there is no isolated vertex. The random bipartite graph G(n, n, p) has no isolated vertex with high probability if np − log n tends to infinity as n tends to infinity, see for example [11].