Independent transversals in \(r\)-partite graphs (Q1377695)

\({\mathcal G}(r,n)\) denotes the set of all \(r\)-partite graphs having precisely \(n\) vertices in each of the \(r\) classes. An independent transversal is an independent set consisting of exactly one vertex from each of the \(r\) classes. If \(\Delta(r,n)\) denotes the maximum integer \(m\) such that every \(G\in{\mathcal G}(r,n)\) with maximum degree less than \(m\) contains an independent transversal, then \(C_r\) is defined to be \(\lim\limits_{n\to\infty}\frac{\Delta(r,n)}n\). Theorem 1.1. (1) \(\Delta(4,n)\geq\frac{2n}3\). (2) For all \(r\geq3\), \(\Delta(2r,n)\geq\frac{\Delta(r,n)}2\). (3) For all \(r\geq3\), \(C_r\geq\max\{\frac{1}{2^{\log\left\lceil r/3 \right\rceil}},\frac 1{3\cdot 2^{\left\lceil\log r\right\rceil}-3}\}\). Theorem 1.2. For every \(r\geq2\), \(\Delta(r,n)\leq n\cdot\frac{2^{\lfloor\log r\rfloor-1}}{2^{\lfloor \log r \rfloor}-1}\) holds for infinitely many values of \(n\). Consequently \(C_r\leq\frac{2^{\lfloor\log r\rfloor-1}}{2^{\lfloor \log r \rfloor}-1}\).