MOSS Seminar #5 - Richard Montgomery: Latin squares via graph theory скачать в хорошем качестве

MOSS Seminar #5 - Richard Montgomery: Latin squares via graph theory

MOSS Mathematical Online Seminar Series presents: "Latin squares via graph theory" by Richard Montgomery (University of Warwick, UK) June 5th, 2025 Latin squares have been studied in Combinatorics since the initiating work of Euler in the 1780's. More recently, much progress has been made from the perspective of graph theory, allowing modern graph theory tools to be applied to an equivalent formulation using edge-coloured graphs. I will discuss the study of transversals in Latin squares via this route, and in particular: 1️⃣ How large a partial transversal can we find in any Latin square? 2️⃣ How many disjoint transversals are we likely to find in a random Latin square? More specifically: a Latin square of order n is an n by n grid filled with n symbols so that every symbol appears exactly once in each row and each column. A partial transversal of a Latin square of order n is a collection of cells in the grid which share no row, column or symbol, and a transversal is a partial transversal with n cells. Not every Latin square has a transversal, but I will discuss how, when n is large, every large Latin square has a partial transversal extremely close to a transversal. We should expect to be able to find much more in a `typical' Latin square, and I will also discuss recent work showing that in a random Latin square we should expect to be able to decompose it into disjoint transversals.