# On Aharoni-Berger's conjecture of rainbow matchings

#### by Jane Gao

Institution: Monash University
Date: Thu 24th August 2017
Time: 11:00 AM
Location: Room 107, Peter Hall Building

Abstract: Let $$G$$ be a properly edge coloured multigraph with $$m$$ colours and let $${\mathcal M}=\{M_1,\ldots, M_m\}$$ be the set of $$m$$ matchings induced by each colour in $$G$$. Assume that every matching in $${\mathcal M}$$ has size $$n$$. Aharoni and Berger conjectured that if $$G$$ is bipartite and $$m=n-1$$ then $$G$$ contains a full rainbow matching, i.e. a matching that contains exactly one edge from each $$M_i$$ for each $$1\le i\le m$$. We prove an approximate version of this conjecture. We show that if $$m\le n-n^{c}$$, where $$c>9/10$$, and $$G$$ is simple whereas not necessarily bipartite, then $$G$$ contains a rainbow matching if $$n$$ is sufficiently large. Our proof proceeds by analysing a randomised algorithm.

This is collaborated work with Reshma Ramadurai, Ian Wanless and Nick Wormald.