# On Aharoni-Berger's conjecture of rainbow matchings

*Discrete Structures and Algorithms (Seminar)*

*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.

*For More Information:* Contact: Sanming Zhou. email: sanming@unimelb.edu.au