School Seminars and Colloquia

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