Abstract An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in $$\mathbb {R}^3$$ R 3 consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in $$\mathbb {R}^3$$ R 3 admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: any mass distribution (or point set) in $$\mathbb {R}^3$$ R 3 admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in $$\mathbb {R}^3$$ R 3 (with prescribed normal direction of one of the planes) in time $$O (n^{7/3})$$ O ( n 7 / 3 ) . A preliminary version of this work appeared in SoCG’24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024).

An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}).

Abstract. A celebrated conjecture of Tuza states that in any finite graph the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. For an [Formula: see text]-uniform hypergraph ([Formula: see text]-graph) [Formula: see text], let [Formula: see text] be the minimum size of a cover of edges by [Formula: see text]-sets of vertices, and let [Formula: see text] be the maximum size of a set of edges pairwise intersecting in fewer than [Formula: see text] vertices. Aharoni and Zerbib proposed the following generalization of Tuza’s conjecture: For any [Formula: see text]-graph [Formula: see text], [Formula: see text]. Let [Formula: see text] be the uniformly random [Formula: see text]-graph on [Formula: see text] vertices. We show that for [Formula: see text] and any [Formula: see text], [Formula: see text] satisfies the Aharoni–Zerbib conjecture with high probability (w.h.p.), i.e., with probability approaching 1 as [Formula: see text]. We also show that there is a [Formula: see text] such that for any [Formula: see text] and any [Formula: see text], [Formula: see text] w.h.p. Furthermore, we may take [Formula: see text], for any [Formula: see text], by restricting to sufficiently large [Formula: see text] (depending on [Formula: see text]).

We show that there exists an absolute constant $c > 0$, such that, for any finite set $A$ of quaternions, $\max\{|A+A|, |AA| \} \gtrsim |A|^{4/3 + c}.$ This generalizes a sum-product bound for real numbers proved by Konyagin and Shkredov.

Kelly's theorem states that a set of n points affinely spanning C^3 must determine at least one ordinary complex line (a line passing through exactly two of the points). Our main theorem shows that such sets determine at least 3n/2 ordinary lines, unless the configuration has n-1 points in a plane and one point outside the plane (in which case there are at least n-1 ordinary lines). In addition, when at most n/2 points are contained in any plane, we prove a theorem giving stronger bounds that take advantage of the existence of lines with four and more points (in the spirit of Melchior's and Hirzebruch's inequalities). Furthermore, when the points span four or more dimensions, with at most n/2 points contained in any three dimensional affine subspace, we show that there must be a quadratic number of ordinary lines.

We present new bounds on the first selection lemma in ℜ3. This makes progress on the open problems of Bukh, Matouaek and Nivash [6] and Boros-Füredi [4] for the three-dimensional case, improving the previously best result of Wagner [8]. While our results narrow the gap between the current best lower and upper bounds, they do not settle this question. However, they indicate that it is the current lower-bounds that are not tight, and we conjecture that the lower-bounds can be further improved to match the current upper bound.