Discrepancy theory
From Wikipedia, the free encyclopedia
Discrepancy theory can be described as the study of inevitable irregularities of distributions, in measure-theoretic and combinatorial settings. Just as Ramsey theory elucidates the impossibility of total disorder, discrepancy theory studies the deviations from total uniformity.
Contents |
[edit] History
- The 1916 paper of Weyl on the uniform distribution of sequences in the unit interval
- The theorem of Van Aardenne Ehrenfest
[edit] Classic theorems
- Axis-parallel rectangles in the plane (Roth, Schmidt)
- Discrepancy of half-planes (Alexander, Matousek)
- Arithmetic progressions (Roth, Sarkozy, Beck, Matousek & Spencer)
- Beck-Fiala theorem
- Six Standard Deviations Suffice (Spencer)
[edit] Major open problems
- Axis-parallel rectangles in dimensions three and higher (Folklore)
- Komlos conjecture
- The three permutations problem (Beck)
- Homogeneous arithmetic progressions (Erdos, $500)
[edit] Applications
- Numerical Integration: Monte Carlo methods in high dimensions.
- Computational Geometry: Divide and conquer algorithms.
- Image Processing: Halftoning
[edit] References
- Irregularities of Distribution (Beck & Chen)
- Geometric Discrepancy (Matousek)
- The Discrepancy Method (Chazelle)
