The author studies the complexity of the family of convex subsets of the \(d\)-dimensional cube \([1,n]^d\) as \(n\to\infty\). The results answer partially the following question: “Will the family of sets \(\Omega\) resulting from the intersection of all possible convex subsets of the cube \([1,n]^d\) with the integer lattice \(\mathbb{Z}^d\) satisfy the following constraints on the complexity?”
The constraints on the complexity are as follows: Let \(\Omega\) be a family of subsets of indices \(I\). For some \(\alpha\geq 1\) and \(\beta\geq 0\) there exist families \(\Delta_s\), \(\emptyset\in\Delta_s\), \(s=1,\dots,s_0\), with number of elements \(\#\Delta_s\leq C_0N^{\beta}\exp s^{\alpha}\) and such that each set \(\omega\in\Omega\) can be expressed as the union of elements \(E_s\in\Delta_s\) with \(\#E_s\leq 2^{-s}\#I\) and \(E_s\cap E_{s'}\) for \(s\neq s'\).
The result of the paper reads as follows.
“For any \(0<\gamma<1\), there exists a family \(\Omega\) of subsets of the set \(\{1,\dots,n\}^d\) satisfying the above constraints with constants \(\alpha\geq 1\) and \(\beta\geq 0\) depending only on \(\gamma\) and \(d\) such that, for any convex set \(B\subset[1,n]^d\), there exists an \(A\in\Omega\) such that \(A\subset B_{\mathbb{Z}}\) and \(\#(B_{\mathbb{Z}}\setminus A)\leq \gamma\cdot \#B_{\mathbb{Z}}\).” Here \(B_{\mathbb{Z}}\) denotes the intersection of the set \(B\) with the lattice \(\mathbb{Z}^d\).