DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.52

Colorful Intersections and Tverberg Partitions

Authors: Michael Gene Dobbins, Andreas F. Holmsen, and Dohyeon Lee

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

The colorful Helly theorem and Tverberg’s theorem are fundamental results in discrete geometry. We prove a theorem which interpolates between the two. In particular, we show the following for any integers d ≥ m ≥ 1 and k a prime power. Suppose F₁, F₂, … , F_m are families of convex sets in ℝ^d, each of size n > (d/m+1)(k-1), such that for any choice C_i ∈ F_i we have ⋂_{i = 1}^m C_i ≠ ∅. Then, one of the families F_i admits a Tverberg k-partition. That is, one of the F_i can be partitioned into k nonempty parts such that the convex hulls of the parts have nonempty intersection. As a corollary, we also obtain a result concerning r-dimensional transversals to families of convex sets in ℝ^d that satisfy the colorful Helly hypothesis, which extends the work of Karasev and Montejano.

Cite as

Michael Gene Dobbins, Andreas F. Holmsen, and Dohyeon Lee. Colorful Intersections and Tverberg Partitions. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 52:1-52:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dobbins_et_al:LIPIcs.SoCG.2024.52,
  author =	{Dobbins, Michael Gene and Holmsen, Andreas F. and Lee, Dohyeon},
  title =	{{Colorful Intersections and Tverberg Partitions}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{52:1--52:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.52},
  URN =		{urn:nbn:de:0030-drops-199973},
  doi =		{10.4230/LIPIcs.SoCG.2024.52},
  annote =	{Keywords: Tverberg’s theorem, geometric transversals, topological combinatorics, configuration space/test map, discrete Morse theory}
}

Search Results

Documents authored by Lee, Dohyeon

Colorful Intersections and Tverberg Partitions

Abstract

Cite as

Thanks for your feedback!

Could not send message