An Asymptotically Sharp Bound on the Maximum Number of Independent Transversals

Let G be a multipartite graph with partition V₁, V₂,…, Vₖ of $V(G)$. Let di,j denote the edge density of the pair (Vᵢ, Vⱼ). An independent transversal is an independent set of G with exactly one vertex in each Vᵢ. In this paper, we prove an asymptotically sharp upper bound on the maximum number of independent transversals given the di,j's.