On weak \(\epsilon\)-nets and the Radon number (Q2223615): Difference between revisions

The main results of this paper involve a finite set \(X\), a family \(C\) of subsets of \(X\) and probability measures \(\mu\) on \(X\). The family \(C\) is said to have a weak \(\epsilon\)-net of size \(\beta\) over \(\mu\) if there exists a subset \(S\) of \(X\) of size \(\beta\) whose intersection with every member of \(C\) that has the \(\mu\)-measure at least \(\epsilon\) is non-empty. The pair \((X,C)\) is called a convexity space if \(C\) is closed under intersections and both the empty sets and the whole \(X\) are elements of \(C\). In this case, sets from \(C\) are said to be convex sets of the convexity space \((X,C)\). The convex hull \(\mathrm{conv }Y\) of a subset \(Y\) of \(X\) in the convexity space \((X,C)\) is defined as the intersection of all elements of \(C\) that contain \(A\) as a subset. A convexity space \((X,C)\) is called separable if for every convex set \(Y\in C\) and a point \(p\in X\setminus Y\) there exists a partition of \(X\) into convex sets \(X_1\in C\) and \(X_2\in C\) that satisfies \(Y\subseteq X_1\) and \(p\in X_2\). The Radon number of a convexity space \((X,C)\) is the minimal number \(r\) with the property that every subset \(Y\) of \(X\) with \(r\) elements can be partitioned into sets \(Y_1\) and \(Y_2\) whose convex hulls have a non-empty intersection. The main theorem of this paper is about the interplay of the Radon number and the size of weak \(\epsilon\)-nets for \(X\). The theorem states that for a finite convexity space \((X,C)\) the following assertions hold: \begin{itemize} \item[(a)] if \((X,C)\) is separable and has Radon number at most \(r\), then, for every \(\epsilon>0\) and every probability measure \(\mu\) on \(X\), the family \(C\) has a weak \(\epsilon\)-net over \(\mu\) of size at most \((120 r^2/\epsilon) ^{4 r^2\ln(1/\epsilon)}\) \item[(b)] If \((X,C)\) has Radon number at least \(r\), then for some choice of a probability measure \(\mu\) on \(X\), every 1/4-net for \(C\) over \(\mu\) has size at least \(r/2\). \end{itemize} The authors mention that meanwhile Holmsen and Lee (2019) have derived an upper bound on the size of the weak \(\epsilon\)-net of finite convexity spaces \((X,C)\) without any use of the separability assumption on \((X,C)\).