An Asymptotically Sharp Bound on the Maximum Number of Independent Transversals

Jake Ruotolo, Kevin Wang, Fan Wei

Let $G$ be a multipartite graph with partition $V_1,V_2,\dots ,V_k$ of $V(G)$. Let $d_{i,j}$ denote the edge density of the pair $(V_i,V_j)$. An independent transversal is an in…