Irregularities of Distributions and Extremal Sets in Combinatorial Complexity Theory
Irregularities of Distributions and Extremal Sets in Combinatorial Complexity Theory
复制标题
组合复杂性理论中的分布不规则性和极值集
DOI：
10.1007/978-3-319-72456-0_3
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Hinrichs
中科院分区：
文献类型：
--
作者：
C. Aistleitner;A. Hinrichs
在2004年，本文的第二作者证明了在[0，1]d中的一个点集，其星差最多为e，必然至少由cabsde−1个点组成。等价地，[0，1]d中的每一组n个点必须至少有cabsdn-1的星差。这个结果的原始证明使用了Vapnik-Chervonenkis理论和度量熵理论的方法。本文给出了同一结果的初等组合证明，证明的基础是确定[0，1]d的一个子盒，它的边界上有点集的约d个元素。此外，我们表明，一个点集，没有这样的盒子存在是相当不规则的，必须有一个大的明星差异。
In 2004 the second author of the present paper proved that a point set in [0, 1]d which has star-discrepancy at most e must necessarily consist of at least cabsde−1 points. Equivalently, every set of n points in [0, 1]d must have star-discrepancy at least cabsdn−1. The original proof of this result uses methods from Vapnik–Chervonenkis theory and from metric entropy theory. In the present paper we give an elementary combinatorial proof for the same result, which is based on identifying a sub-box of [0, 1]d which has approximately d elements of the point set on its boundary. Furthermore, we show that a point set for which no such box exists is rather irregular, and must necessarily have a large star-discrepancy.