Hypergraphs of Low Degree Without Independent Transversals

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 $(\frac{(k-1{)}^{k-1}}{k^k}+O_k(b^{-1}))b^k,$ while the maximum vertex degree is $(\frac{(k-2{)}^{k-2}}{(k-1{)}^{k-1}}+O_k(b^{-1}))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 $\mathrm{\Delta }(G)<{(1-\frac{1}{k})}^{k-1}{n}^{k-1}$, but with no independent transversal. This gives a negative answer to a problem of Haxell and Wdowinski.