A lower bound for families of Natarajan dimension \(d\) (Q5940311)

Let \(h_d(n,k)\) be the maximum size of a family \({\mathcal F}\) of functions from an \(n\)-element set \(S\) into a \(k\)-element set \(K\) such that there are no \((d+1)\)-element subset \(A\) of \(S\), and 2-element sets \(K_x\subseteq K\) for \(x\in A\) such that all \(2^{d+1}\) transversals of \(\{K_x:x\in A\}\) are realized by some function in \({\mathcal F}\). It is shown that \(h_1(n,3)=3n\) and \(h_d(n,k)\gg n^dg_d(k-1)\) where \(g_d(k)\) is the maximum possible number of edges of a \((d+1)\)-regular \((d+1)\)-partite hypergraph with classes of size \(k\) containing no \(K_{d+1}(2,2,\dots,2)\) as subhypergraph.