Add to Outlook calendar Add to Google calendar

Algebra & Combinatorics Seminar

Title: Approximate packing of independent transversals in locally sparse graphs
Speaker: Debsoumya Chakraborti (Mathematics Institute, University of Warwick, UK)
Date: 03 April 2024
Time: 4 pm
Venue: LH-1, Mathematics Department (Joint with the APRG Seminar)

Consider a multipartite graph $G$ with maximum degree at most $n-o(n)$, parts $V_1,\ldots,V_k$ have size $|V_i|=n$, and every vertex has at most $o(n)$ neighbors in any part $V_i$. Loh and Sudakov proved that any such $G$ has an independent set, referred to as an ‘independent transversal’, which contains exactly one vertex from each part $V_i$. They further conjectured that the vertex set of $G$ can be decomposed into pairwise disjoint independent transversals. We resolve this conjecture approximately by showing that $G$ contains $n-o(n)$ pairwise disjoint independent transversals. As applications, we give approximate answers to questions on packing list colorings and multipartite Hajnal-Szemerédi theorem. We use probabilistic methods, including a ‘two-layer nibble’ argument. This talk is based on joint work with Tuan Tran.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 19 Apr 2024