On the complexity of the family of convex sets in \(\mathbb{R}^d\)
type: Item
instance of: scholarly article
title: On the complexity of the family of convex sets in \(\mathbb{R}^d\)
zbMATH Open document ID: 1358.52023
DOI: 10.1134/S0001434616030263
author: Vladimir V. Pernay
published in: Mathematical Notes
publication date: 2016-10-18T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 52C45
Mathematics Subject Classification ID: 52A20
zbMATH DE Number: 6640390
zbMATH Keywords: complexity of a family of subsets of a \(d\)-cube
zbMATH Keywords: generalized majorant of partial sums
zbMATH Keywords: convex set
zbMATH Keywords: simplex
zbMATH Keywords: Khinchine's inequality
reviewed by: Judit Abardia
MaRDI profile type: Publication
cites work: Analogue of Men'shov's theorem ''on correction'' for discrete orthonormal systems
cites work: On the possibility of generalizing ``correction'' theorems
cites work: Spaces generated by the generalized majorant of partial sums
cites work: A Lower Bound for the Volume of Strictly Convex Bodies with many Boundary Lattice Points
cites work: Q3569377
full work available at URL: s0001434616030263
OpenAlex ID: W2402082153
description: scientific article; zbMATH DE number 6640390