标题： VC-维和点配置在$\mathbb{R}^d$ 显示英文标题

标题： The VC-dimension and point configurations in $\mathbb{R}^d$

摘要： 给定一个集合$X$和从$X$到$\{0,1\}$的函数族${\mathcal H}$，VC-维数衡量了在PAC学习背景下假设类$\mathcal{H}$的复杂性。 近年来，这已被连接到有限域上的向量空间中的几何配置问题。 特别是，可以很容易地证明，在$\mathbb{F}_q^d$中给定半径的球集的VC-维数等于$d+1$，因为这是通常确定一个球所需的点数。 已知对于$E\subseteq \mathbb{F}_q^d$,$|E|\geq q^{d-\frac{1}{d-1}}$，以$E$中的点为球心，并与集合$E$相交的球的集合，其VC维为$d$或$d+1$。 在本文中，我们研究欧几里得空间中的类似问题。 我们找到一个显式的维度阈值$s_d<d$，使得当$E\subseteq \mathbb{R}^d$，$d\geq 3$，并且$E$的豪斯多夫维数至少为$s_d$时，可以得出存在一个区间$I$，使得对于任何$t\in I$，以$E$中的点为中心且半径为$t$的球体集合与$E$的交集的 VC 维数至少为$3$。 在证明这个定理的过程中，我们还首次提供了集合$E\subseteq \mathbb{R}^3$包含$4$-循环的第一个显式维度阈值，即 $x_1,x_2,x_3,x_4\in E$满足$$ |x_1-x_2|=|x_2-x_3|=|x_3-x_4|=|x_4-x_1| $$ 显示英文摘要

摘要： Given a set $X$ and a collection ${\mathcal H}$ of functions from $X$ to $\{0,1\}$, the VC-dimension measures the complexity of the hypothesis class $\mathcal{H}$ in the context of PAC learning. In recent years, this has been connected to geometric configuration problems in vector spaces over finite fields. In particular, it is easy to show that the VC-dimension of the set of spheres of a given radius in $\mathbb{F}_q^d$ is equal to $d+1$, since this is how many points generically determine a sphere. It is known that for $E\subseteq \mathbb{F}_q^d$, $|E|\geq q^{d-\frac{1}{d-1}}$, the set of spheres centered at points in $E$, and intersected with the set $E$, has VC-dimension either $d$ or $d+1$. In this paper, we study a similar question over Euclidean space. We find an explicit dimensional threshold $s_d<d$ so that whenever $E\subseteq \mathbb{R}^d$, $d\geq 3$, and the Hausdorff dimension of $E$ is at least $s_d$, it follows that there exists an interval $I$ such that for any $t\in I$, the VC-dimension of the set of spheres of radius $t$ centered at points in $E$, and intersected with $E$, is at least $3$. In the process of proving this theorem, we also provide the first explicit dimensional threshold for a set $E\subseteq \mathbb{R}^3$ to contain a $4$-cycle, i.e. $x_1,x_2,x_3,x_4\in E$ satisfying $$ |x_1-x_2|=|x_2-x_3|=|x_3-x_4|=|x_4-x_1| $$