Point sets with many \(k\)-sets (Q5946377)

For a set \(P\) of \(n\) points in the \(d\)-dimensional space \(\mathbb{R}^d\), a \(k\)-set is a subset \(P'\) of \(P\) such that \(P'=P\cap H\) for some open half-space \(H\), and \(|P'|=k\). The problem is to determine the maximum number of \(k\)-sets. The author constructs for any \(n\) and \(k\) \((n\geq 2k>0)\) a set of \(n\) points in \(\mathbb{R}^2\) with \(ne^{\Omega (\sqrt{\log k})}\) \(k\)-sets. He also constructs for any \(n\) and \(d\geq 2\) a set of \(n\) points in \(\mathbb{R}^d\) with \(n^{d-1} e^{\Omega(\sqrt{\log n})}\) halving hyperplanes (i.e. \(k\)-sets with \(k=n/2)\).