Discrepancy theory

Last updated

In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be in. It is also called the theory of irregularities of distribution. This refers to the theme of classical discrepancy theory, namely distributing points in some space such that they are evenly distributed with respect to some (mostly geometrically defined) subsets. The discrepancy (irregularity) measures how far a given distribution deviates from an ideal one.

Contents

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.

A significant event in the history of discrepancy theory was the 1916 paper of Weyl on the uniform distribution of sequences in the unit interval. [1]

Theorems

Discrepancy theory is based on the following classic theorems:

Major open problems

The unsolved problems relating to discrepancy theory include:

Applications

Applications for discrepancy theory include:

See also

Related Research Articles

<span class="mw-page-title-main">Euclidean geometry</span> Mathematical model of the physical space

Euclidean geometry is a mathematical system attributed to ancient Greek mathematician Euclid, which he described in his textbook on geometry, Elements. Euclid's approach consists in assuming a small set of intuitively appealing axioms (postulates) and deducing many other propositions (theorems) from these. Although many of Euclid's results had been stated earlier, Euclid was the first to organize these propositions into a logical system in which each result is proved from axioms and previously proved theorems.

The following outline is provided as an overview of and topical guide to statistics:

<span class="mw-page-title-main">Geometry of numbers</span>

Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice in and the study of these lattices provides fundamental information on algebraic numbers. The geometry of numbers was initiated by Hermann Minkowski.

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

<span class="mw-page-title-main">Discrete geometry</span> Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x1, ..., xN has a low discrepancy.

<span class="mw-page-title-main">Klaus Roth</span> British mathematician

Klaus Friedrich Roth was a German-born British mathematician who won the Fields Medal for proving Roth's theorem on the Diophantine approximation of algebraic numbers. He was also a winner of the De Morgan Medal and the Sylvester Medal, and a Fellow of the Royal Society.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

<span class="mw-page-title-main">József Beck</span> Hungarian mathematician

József Beck is a Harold H. Martin Professor of Mathematics at Rutgers University.

Discrepancy of hypergraphs is an area of discrepancy theory.

Joseph O'Rourke is the Spencer T. and Ann W. Olin Professor of Computer Science at Smith College and the founding chair of the Smith computer science department. His main research interest is computational geometry.

<span class="mw-page-title-main">Jiří Matoušek (mathematician)</span> Czech mathematician (1963–2015)

Jiří (Jirka) Matoušek was a Czech mathematician working in computational geometry and algebraic topology. He was a professor at Charles University in Prague and the author of several textbooks and research monographs.

Combinatorica is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honorary editor-in-chief. The current editors-in-chief are Imre Bárány and József Solymosi. The advisory board consists of Ronald Graham, Gyula O. H. Katona, Miklós Simonovits, Vera Sós, and Endre Szemerédi. It is published by the János Bolyai Mathematical Society and Springer Verlag.

In geometry, the moment curve is an algebraic curve in d-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form

In mathematics, the Beck–Fiala theorem is a major theorem in discrepancy theory due to József Beck and Tibor Fiala. Discrepancy is concerned with coloring elements of a ground set such that each set in a certain set system is as balanced as possible, i.e., has approximately the same number of elements of each color. The Beck–Fiala theorem is concerned with the case where each element doesn't appear many times across all sets. The theorem guarantees that if each element appears at most t times, then the elements can be colored so that the imbalance is at most 2t − 1.

A geometric separator is a line that partitions a collection of geometric shapes into two subsets, such that proportion of shapes in each subset is bounded, and the number of shapes that do not belong to any subset is small.

Algorithms and Combinatorics is a book series in mathematics, and particularly in combinatorics and the design and analysis of algorithms. It is published by Springer Science+Business Media, and was founded in 1987.

References

  1. Weyl, Hermann (1 September 1916). "Über die Gleichverteilung von Zahlen mod. Eins" [About the equal distribution of numbers]. Mathematische Annalen (in German). 77 (3): 313–352. doi:10.1007/BF01475864. ISSN   1432-1807. S2CID   123470919.
  2. József Beck and Tibor Fiala (1981). ""Integer-making" theorems". Discrete Applied Mathematics. 3 (1): 1–8. doi: 10.1016/0166-218x(81)90022-6 .
  3. Joel Spencer (June 1985). "Six Standard Deviations Suffice". Transactions of the American Mathematical Society. Transactions of the American Mathematical Society, Vol. 289, No. 2. 289 (2): 679–706. doi: 10.2307/2000258 . JSTOR   2000258.
  4. Spielman, Daniel (11 May 2020). "Using discrepancy theory to improve the design of randomized controlled trials".{{cite journal}}: Cite journal requires |journal= (help)

Further reading