pipette
ENEnglish

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

Zhewei Wei

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 18 pages, 3 figures