Pokrovskiy, A;
(2018)
An approximate version of a conjecture of Aharoni and Berger.
Advances in Mathematics
, 333
pp. 1197-1241.
10.1016/j.aim.2018.05.036.
Preview |
Text
1609.06346v2.pdf - Accepted Version Download (868kB) | Preview |
Abstract
Aharoni and Berger conjectured that in every proper edge-colouring of a bipartite multigraph by n colours with at least n+1 edges of each colour there is a rainbow matching using every colour. This conjecture generalizes a longstanding problem of Brualdi and Stein about transversals in Latin squares. Here an approximate version of the AharoniBerger Conjecture is proved—it is shown that if there are at least n + o(n) edges of each colour in a proper n-edge-colouring of a bipartite multigraph then there is a rainbow matching using every colour.
| Type: | Article |
|---|---|
| Title: | An approximate version of a conjecture of Aharoni and Berger |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.aim.2018.05.036 |
| Publisher version: | https://doi.org/10.1016/j.aim.2018.05.036 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Latin squares, Rainbow matchings, Connectedness |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10112652 |
Archive Staff Only
 |
View Item |
