pipette
ESEspañol

Tight Bounds for Tusn\'ady's Problem in the Plane

Zhewei Wei

Preprint

In the authors' words

We show that the worst-case combinatorial discrepancy of points in the plane with respect to axis-parallel rectangles is . The known bounds were and ; we prove the matching lower bound. It holds for random point sets: for every , there is a constant such that, with probability at least , every coloring of independent uniform points in the unit square has an anchored rectangle with imbalance at least . The proof is surprisingly simple and elementary. It reveals one coordinate digit by digit. With overwhelming probability over the points, the conditional gains of an oscillation potential add up to over digits. Bounded differences control the fluctuations well enough for a union bound over all colorings.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 18 pages, 3 figures