Tverberg-Type Theorems with Altered Intersection Patterns (Nerves)
- PDF / 1,934,934 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 61 Downloads / 145 Views
Tverberg-Type Theorems with Altered Intersection Patterns (Nerves) Jesús A. De Loera1 · Thomas A. Hogan1 Dominic Yang1
· Deborah Oliveros2 ·
Received: 2 November 2018 / Revised: 10 June 2020 / Accepted: 1 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Tverberg’s theorem says that a set with sufficiently many points in Rd can always be partitioned into m parts so that the (m − 1)-simplex is the (nerve) intersection pattern of the convex hulls of the parts. The main results of our paper demonstrate that Tverberg’s theorem is just a special case of a more general situation, where other simplicial complexes must always arise as nerve complexes, as soon as the number of points is large enough. We prove that, given a set with sufficiently many points, all trees and all cycles can also be induced by at least one partition of the point set. We also discuss how some simplicial complexes can never be achieved this way, even for arbitrarily large sets of points. Keywords Tverberg’s theorem · Nerve complexes · Geometric Ramsey theory · Combinatorial convexity · Intersection graphs · Clustering Mathematics Subject Classification 52A35 · 52A01 · 52C40 · 05C55
Editor in Charge: János Pach Jesús A. De Loera [email protected] Thomas A. Hogan [email protected] Deborah Oliveros [email protected] Dominic Yang [email protected] 1
Department of Mathematics, University of California, Davis, USA
2
Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico City, Mexico
123
Discrete & Computational Geometry
1 Introduction The celebrated theorem of Helge Tverberg states (see [2] and references therein): Tverberg’s Theorem ([27]) Every set S with at least (d + 1)(m − 1) + 1 points in Euclidean d-space Rd can be partitioned into m parts P = S1 , . . . , Sm such that all the convex hulls of these parts have nonempty intersection. The special case of a bi-partition, m = 2, is called Radon’s lemma. The nerve (intersection pattern) of the convex hulls in Tverberg’s theorem is very specific, a simplex; our paper investigates other possible nerves. Informally, the main results of our paper demonstrate that, given sufficiently many points, other kinds of nerves can always be induced by a suitable partition of the point set. In particular, we show that any tree or cycle can be induced as the nerve. Our geometric results are naturally motivated from two independent research directions. First of all, there is Ramsey theory (see [11]) where one studies how every sufficiently large system must contain a large well-organized subsystem. Here “sufficiently large” is governed by Ramsey numbers. In geometry a classical example of a Ramsey-type theorem is Erd˝os–Szekeres’ theorem saying that every sufficiently large point set in the plane must contain a sub-configuration forming a convex k-gon (in this case the constant is hard to compute; see [24] and references there). We stress that Tverberg’s theorem is also Ramsey-type, although in this case the constant is explicit and
Data Loading...
