Abstract. For a set [Formula: see text] of [Formula: see text] points in [Formula: see text], for any [Formula: see text], a hyperplane [Formula: see text] is called [Formula: see text]- rich with respect to [Formula: see text] if it contains at least [Formula: see text] points of [Formula: see text]. Answering and generalizing a question asked by Peyman Afshani, we show that if the number of [Formula: see text]-rich hyperplanes in [Formula: see text], [Formula: see text], is at least [Formula: see text], with a sufficiently large constant of proportionality and with [Formula: see text], then there exists a [Formula: see text]-flat that contains [Formula: see text] points of [Formula: see text]. We also present upper bound constructions that give instances in which the above lower bound is tight. An extension of our analysis yields similar lower bounds for [Formula: see text]-rich spheres or [Formula: see text]-rich flats.

Let K be a convex body in $$\mathbb {R}^n$$ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of $$K \cap h$$ . In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least $$n+1$$ distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if $$p=p_0$$ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for $$n \ge 2$$ , there are always at least three distinct barycentric cuts through the point $$p_0 \in K$$ of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through $$p_0$$ are guaranteed if $$n \ge 3$$ .

Intersection patterns of convex sets in ℝ^d have the remarkable property that for d+1 ≤ k ≤ 𝓁, in any sufficiently large family of convex sets in ℝ^d, if a constant fraction of the k-element subfamilies have nonempty intersection, then a constant fraction of the 𝓁-element subfamilies must also have nonempty intersection. Here, we prove that a similar phenomenon holds for any topological set system ℱ in ℝ^d. Quantitatively, our bounds depend on how complicated the intersection of 𝓁 elements of ℱ can be, as measured by the maximum of the ⌈d/2⌉ first Betti numbers. As an application, we improve the fractional Helly number of set systems with bounded topological complexity due to the third author, from a Ramsey number down to d+1. We also shed some light on a conjecture of Kalai and Meshulam on intersection patterns of sets with bounded homological VC dimension. A key ingredient in our proof is the use of the stair convexity of Bukh, Matoušek and Nivasch to recast a simplicial complex as a homological minor of a cubical complex.

We prove general topological Radon-type theorems for sets in ℝ^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface.

We prove that for every d ≥ 2, deciding if a pure, d -dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d -dimensional, simplicial complex is k -decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d -dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.

The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in Rd. A k-ary semialgebraic predicate Φ(x1, …, xk) on Rd is a Boolean combination of polynomial equations and inequalities in the kd coordinates of k points x1, …, xk ∈ Rd. A sequence P = (p1, …, pn) of points in Rd is called Φ-homogeneous if either Φ(pi1, …,pik) holds for all choices 1 ≤ i1 < … < ik ≤ n, or it holds for no such choice. The Ramsey function RΦ (n) is the smallest N such that every point sequence of length N contains a Φ-homogeneous subsequence of length n.

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in $\mathbb{R}^d$. A $k$-ary semialgebraic predicate $\Phi(x_1,\ldots,x_k)$ on $\mathbb{R}^d$ is a Boolean combination of polynomial equations and inequalities in the $kd$ coordinates of $k$ points $x_1,\ldots,x_k\in\mathbb{R}^d$. A sequence $P=(p_1,\ldots,p_n)$ of points in $\mathbb{R}^d$ is called $\Phi$-homogeneous if either $\Phi(p_{i_1}, \ldots,p_{i_k})$ holds for all choices $1\le i_1<\cdots