University of Cambridge > Talks.cam > Combinatorics Seminar > A random Hall-Paige Conjecture

A random Hall-Paige Conjecture

Add to your list(s) Download to your calendar using vCal

  • UserAlexey Pokrovskiy (UCL)
  • ClockThursday 25 May 2023, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact ibl10.

A rainbow subgraph in an edge-coloured graph is one in which all edges have different colours. This talk will be about finding rainbow subgraphs in colourings of graphs that come from groups. An old question of this type was asked by Hall and Paige. Their question was equivalent to the following “Let G be a group of order n and consider an edge-coloured Knn, whose parts are each a copy of G and with the edge {x,y} coloured by the group element xy. For which groups G, does this coloured Knn contain a perfect rainbow matching?” This question is equivalent to asking “which groups G contain a complete mapping’’ and also “which multiplication tables of groups contain transversals’’. Hall and Paige conjectured that the answer is “all groups in which the product of all the elements is in the commutator subgroup of G’’. They proved that this is a necessary condition, so the main part of the conjecture is to prove that that rainbow matchings exist under their condition. The Hall-Paige Conjecture was confirmed in 2009 by Wilcox, Evans, and Bray with a proof using the classification of finite simple groups. Recently, Eberhard, Manners, and Mrazovic found an alternative proof of the conjecture for sufficiently large groups using ideas from analytic number theory. Their proof gives a very precise estimate on the number of complete mappings that each group has. In this talk, a third proof of the conjecture will be presented using a different set of techniques, this time coming from probabilistic combinatorics. This proof only works for sufficiently large groups, but generalizes the conjecture in a new direction. Specifically we not only characterize when the edge coloured Knn contains a perfect rainbow matching, but also when random subgraphs of it contain a perfect rainbow matching. This extension has a number of applications, such as to problems of Snevily, Cichacz, Tannenbaum, Evans. This is joint work with Alp Muyesser.

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2024 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity