An asymptotically sharp bound on the maximum number of independent transversals (Q6131742)

Summary: Let \(G\) be a multipartite graph with partition \(V_1, V_2, \ldots, 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 independent set of \(G\) with exactly one vertex in each \(V_i\). In this paper, we prove an asymptotically sharp upper bound on the maximum number of independent transversals given the \(d_{i,j}\)'s.