Matchings in Random Biregular Bipartite Graphs

Guillem Perarnau, Giorgis Petridis

Abstract


We study the existence of perfect matchings in suitably chosen induced subgraphs of random biregular bipartite graphs. We prove a result similar to a classical theorem of Erdös and Rényi about perfect matchings in random bipartite graphs. We also present an application to commutative graphs, a class of graphs that are featured in additive number theory.


Keywords


Random biregular bipartite graphs; Perfect matchings; Commutative graphs

Full Text: PDF