Odd Independent Transversals are Odd

Abstract

We put the final piece into a puzzle first introduced by Bollobás, Erdõs and Szemerédi in 1975. For arbitrary positive integers $n$ and $r$ we determine the largest integer $\Delta=\Delta (r,n)$, for which any $r$-partite graph with partite sets of size $n$ and of maximum degree less than $\Delta$ has an independent transversal. This value was known for all even $r$. Here we determine the value for odd $r$ and find that $\Delta(r,n)=\Delta(r-1,n)$. Informally this means that the addition of an oddth partite set does not make it any harder to guarantee an independent transversal.

In the proof we establish structural theorems which could be of independent interest. They work for all$r\geq 7$, and specify the structure of slightly sub-optimal graphs for even$r\geq 8$.