/Exposé en anglais/Talk in english/

A rainbow matching in an edge-coloured graph is a matching whose edges all have different colours. Let G be a group of order n and consider an edge-coloured complete bipartite graph, whose parts are each a copy of the group G, and the edge (x, y) gets coloured by the group element xy. We call this graph the multiplication table of G. For which groups G does the multiplication table of G have a rainbow matching? This is an old question in combinatorial group theory due to Hall and Paige, with close connections to the study of Latin squares. The problem has been resolved in 2009 with a proof relying on the classification of finite simple groups. In 2021, a "simpler" proof for large groups appeared, this time using tools from analytic number theory. We present a third resolution of this problem, again only for large groups, and using techniques from probabilistic combinatorics. The main advantage of our approach is that we are able to find rainbow matchings in random subgraphs of the multiplication table of G. This flexibility allows us to settle numerous longstanding conjectures in this area. For example, Evans asked for a characterisation of groups whose elements can be ordered so that the product of each consecutive pair of elements is distinct. Using our results, we are able to answer this question for large groups. In this talk, we will give a gentle survey of this area.

This is joint work with Alexey Pokrovskiy.

[Alp Muyesser] ( University College London )

[ https://alpmuye.github.io/ | https://alpmuye.github.io/ ]

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .