Irregularities of Distributions and Extremal Sets in Combinatorial Complexity Theory
Autor: | Christoph Aistleitner, Aicke Hinrichs |
---|---|
Rok vydání: | 2018 |
Předmět: |
Discrete mathematics
Sauer–Shelah lemma 010102 general mathematics Point set Boundary (topology) Combinatorial proof 010103 numerical & computational mathematics 01 natural sciences Combinatorics Set (abstract data type) Combinatorial complexity Vapnik–Chervonenkis theory Metric (mathematics) 0101 mathematics Mathematics |
Zdroj: | Contemporary Computational Mathematics-A Celebration of the 80th Birthday of Ian Sloan ISBN: 9783319724553 |
DOI: | 10.1007/978-3-319-72456-0_3 |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |
Pro tento záznam nejsou dostupné žádné jednotky.