Diskrepansteori

Inom matematik beskriver diskrepansteori en situations avvikelse från det tillstånd man skulle vilja att den skulle vara i. Den kallas också teorin om fördelningsoegentligheter . Detta syftar på temat för klassisk diskrepansteori, nämligen att fördela punkter i något utrymme så att de är jämnt fördelade med avseende på vissa (mestadels geometriskt definierade) delmängder. Diskrepansen (oregelbundenheten) mäter hur långt en given fördelning avviker från en idealisk.

Diskrepansteori kan beskrivas som studiet av oundvikliga oegentligheter i distributioner, i måttteoretiska och kombinatoriska miljöer. Precis som Ramsey-teorin belyser omöjligheten av total oordning, studerar diskrepansteorin avvikelserna från total enhetlighet.

En viktig händelse i diskrepansteorins historia var Weyls artikel från 1916 om den enhetliga fördelningen av sekvenser i enhetsintervallet.

Satser

Diskrepansteori är baserad på följande klassiska satser:

• Van Aardenne–Ehrenfests sats
• Axelparallella rektanglar i planet ( Roth , Schmidt)
• Diskrepans mellan halvplan (Alexander, Matoušek )
• Aritmetiska progressioner (Roth, Sarkozy, Beck , Matousek & Spencer )
• Beck–Fiala-satsen
• Sex standardavvikelser räcker (Spencer)

Stora öppna problem

De olösta problemen relaterade till diskrepansteori inkluderar:

• Axelparallella rektanglar i dimensionerna tre och högre (folklore)
• Komlós gissning
• Heilbronn triangelproblem på minsta arean av en triangel bestäms av tre punkter från en n -punktsuppsättning

Ansökningar

Ansökningar om diskrepansteori inkluderar:

• Numerisk integration: Monte Carlo-metoder i höga dimensioner.
• Beräkningsgeometri: Dela-och-härska-algoritm .
• Bildbehandling: Halvtoning
• Slumpmässig prövningsformulering: Randomiserad kontrollerad prövning

Se även

• Avvikelse i hypergrafer

Vidare läsning

•   Beck, József; Chen, William WL (1987). Oegentligheter i distributionen . New York: Cambridge University Press. ISBN 0-521-30792-9 .
•   Chazelle, Bernard (2000). Diskrepansmetoden: slumpmässighet och komplexitet . New York: Cambridge University Press. ISBN 0-521-77093-9 .
•   Matousek, Jiri (1999). Geometrisk diskrepans: en illustrerad guide . Algoritmer och kombinatorik. Vol. 18. Berlin: Springer. ISBN 3-540-65528-X .