MATH Seminar

Title: Independent transversals in multipartite graphs
Seminar: Discrete Math
Speaker: Yi Zhao, PhD of Georgia State University
Contact: Dr. Cosmin Pohoata, cosmin.pohoata@emory.edu
Date: 2025-02-19 at 4:00PM
Venue: MSC E408
Download Flyer
Abstract: An independent transversal in a multipartite graph is an independent set that intersects each part in exactly one vertex. We show that given any positive even integer r, every r-partite graph with parts of size n and maximum degree r n / (2r-2) - t (t>0) contains c t n^{r-1}) independent transversals. This is best possible up to the constant c=c_r, confirming a conjecture of Haxell and Szabo from 2006 and partially answering a question Erdos from 1972 and a question of Bollobas, Erdos and Szemeredi from 1975. We also show that for every s\ge 2, even r\ge 2 and sufficiently large n, every r-partite graph with parts of size n and maximum degree \Delta