Hypergraphs of Low Degree Without Independent Transversals

Source abstract

For every fixed $k\ge 3$ and every integer $b\ge 2$, we construct a finite vertex-partitioned $k$-uniform hypergraph with blocks of size $b$ and no independent transversal. We show that the maximum number of edges meeting a block is $\left(\frac{(k-1)^{k-1}}{k^k}+O_k(b^{-1})\right)b^k,$ while the maximum vertex degree is $\left(\frac{(k-2)^{k-2}}{(k-1)^{k-1}}+O_k(b^{-1})\right)b^{k-1}$. This shows that the known bound on the number of edges meeting a block is asymptotically sharp even when the leading constant in the maximum vertex degree tends to zero, which answers a problem of Groenland, Kaiser, Treffers, and Wales. By blowing up the same construction, we further obtain for arbitrarily large $n$, there exists a $k$-uniform hypergraph with $n$ blocks, each of size at least $n$, and $Δ(G)<\left(1-\frac1k\right)^{k-1}n^{k-1}$, but with no independent transversal. This gives a negative answer to a problem of Haxell and Wdowinski.