An Asymptotically Sharp Bound on the Maximum Number of Independent Transversals

Abstract

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 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.

arXiv comment15 pages, 1 figure