Abstract. We prove extensions of Halman’s discrete Helly theorem for axis-parallel boxes in [Formula: see text]. Halman’s theorem says that, given a set [Formula: see text] in [Formula: see text], if [Formula: see text] is a finite family of axis-parallel boxes such that the intersection of any [Formula: see text] contains a point of [Formula: see text], then the intersection of [Formula: see text] contains a point of [Formula: see text]. We prove colorful, fractional, and quantitative versions of Halman’s theorem. For the fractional versions, it is enough to check that many [Formula: see text]-tuples of the family contain points of [Formula: see text]. Among the colorful versions, we include variants where the coloring condition is replaced by an arbitrary matroid. Our results generalize beyond axis-parallel boxes to H-convex sets.

Abstract. Given a finite set of points in [Formula: see text], Tverberg’s theorem guarantees the existence of partitions of this set into parts whose convex hulls intersect. We introduce a graph structured on the family of Tverberg partitions of a given set of points, whose edges describe closeness between different Tverberg partitions. We prove bounds on the minimum and maximum degrees of this graph, the number of vertices of maximal degree, its clique number, and its connectedness.

Regression depth, introduced by Rousseeuw and Hubert in 1999, is a notion that measures how good of a regression hyperplane a given query hyperplane is with respect to a set of data points. Under projective duality, this can be interpreted as a depth measure for query points with respect to an arrangement of data hyperplanes. The study of depth measures for query points with respect to a set of data points has a long history, and many such depth measures have natural counterparts in the setting of hyperplane arrangements. For example, regression depth is the counterpart of Tukey depth. Motivated by this, we study general families of depth measures for hyperplane arrangements and show that all of them must have a deep point. Along the way we prove a Tverberg-type theorem for hyperplane arrangements, giving a positive answer to a conjecture by Rousseeuw and Hubert from 1999. We also get three new proofs of the centerpoint theorem for regression depth, all of which are either stronger or more general than the original proof by Amenta, Bern, Eppstein, and Teng. Finally, we prove a version of the center transversal theorem for regression depth.

A Helly-type theorem for diameter provides a bound on the diameter of the intersection of a finite family of convex sets in $\mathbb{R}^d$ given some information on the diameter of the intersection of all sufficiently small subfamilies. We prove fractional and colorful versions of a long-standing conjecture by Bárány, Katchalski, and Pach. We also show that a Minkowski norm admits an exact Helly-type theorem for diameter if and only if its unit ball is a polytope and prove a colorful version for those that do. Finally, we prove Helly-type theorems for the property of “containing $k$ colinear integer points.”

The coloured Tverberg theorem was conjectured by Barany, Lovasz and Furedi [2] and asks whether for any d+1 sets (considered as colour classes) of k points each in Rd there is a partition of them into k colourful sets whose convex hulls intersect. This is known when d=1,2 [3] or k+1 is prime [5]. In this paper we show that (k-1)d+1 colour classes are necessary and sufficient if the coefficients in the convex combination in the colourful sets are required to be the same in each class. We also examine what happens if we want the convex hulls of the colourful sets to intersect even if we remove any r of the colour classes. Namely, if we have (r+1)(k-1)d+1 colour classes of $k$ point each, there is a partition of them into k colourful sets such that they intersect using the same coefficients regardless of which r colour classes are removed. We also investigate the relation of the case k=2 and the Gale transform. We then show applications of these results to purely combinatorial problems.