Debsoumya Chakraborti

Approximate packing of independent transversals in locally sparse graphs

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\'edi theorem. We use probabilistic methods, including a `two-layer nibble' argument. This talk is based on joint work with Tuan Tran.