Discrepancy theory, Tverberg's theorem, and regression depth

Aleksey Lopez; Pablo Sober\'on

In the authors' words

We prove new bounds for Tverberg's theorem with tolerance. We show that $N = r t + Θ_{d, r} (t^{1/2 - 1/ (2 d)})$ , where $N$ is the smallest number such that any set of $N$ points in $R^{d}$ has a partition into $r$ parts such that the convex hulls of the parts intersect even if we remove any $t$ of the points. We extend Tverberg's theorem with tolerance to families of hyperplanes in $R^{d}$ , and show that for any set of $r t + O_{d, r} (t^{1/2 - 1/ (2 d)} lo g (t + 1))$ hyperplanes in $R^{d}$ there exists a partition of them into $r$ parts such that the regression hulls of the parts intersect even if any $t$ hyperplanes are removed. Our bounds follow from establishing a connection between Tverberg-type results and discrepancy theory.

Main resultThe abstract does not state a limitation.

Discrepancy theory, Tverberg's theorem, and regression depth

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

On infinite families of $[P_{n}]$ -irregular graphs