An approximate version of a conjecture of Aharoni and Berger

作者：Pokrovskiy Alexey^*

来源：Advances in Mathematics, 2018, 333: 1197-1241.

DOI：10.1016/j.aim.2018.05.036

• Latin squares
• Rainbow matchings
• Connectedness

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 Aharoni Berger 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.

• 出版日期2018-7-31