Math 2.0

Convex and discrete geometry Convex sets: basic notions Theorem

Tverberg's theorem

Builds on Euclidean spaceConvex hullPartition of a setRadon's theoremColorful Carathéodory theorem

Statement

Let d≥1d \ge 1 and r≥2r \ge 2 be integers, and let X⊆ℝdX \subseteq \R^d be a finite set with at least (r−1)(d+1)+1(r - 1)(d + 1) + 1 points. Then XX can be partitioned into rr disjoint sets X1,…,XrX_1, \dots, X_r whose convex hulls have a common point: conv⁡(X1)∩⋯∩conv⁡(Xr)≠∅.\operatorname{conv}(X_1) \cap \cdots \cap \operatorname{conv}(X_r) \ne \emptyset.

Remarks

For r=2r = 2 the bound is d+2d + 2, and the theorem is Radon's theorem.

Example: with d=2d = 2 and r=3r = 3, any 77 points in the plane can be split into three groups whose convex hulls share a point. For instance, take the vertices of a large triangle, the vertices of a smaller triangle with the same centroid cc, and the point cc itself. The three groups formed by the large triangle, the small triangle and {c}\set{c} all have cc in their convex hulls.

The bound (r−1)(d+1)+1(r - 1)(d + 1) + 1 is sharp: there are sets of (r−1)(d+1)(r - 1)(d + 1) points in ℝd\R^d with no such partition.

Proof idea: Tverberg's original proof was a direct geometric argument. A shorter proof by Sarkaria lifts the points to a space of dimension (r−1)(d+1)(r - 1)(d + 1) using tensor products with vectors that sum to 00, and applies the colorful Carathéodory theorem there.

Going deeper

For a student

A common point of a Tverberg partition is a kind of multidimensional median of the set, which links the theorem to the centerpoint theorem. The topological Tverberg conjecture asked whether continuous maps of a simplex can replace convex hulls. It holds when rr is a prime power and fails for some other values of rr.

Reading path

To understand this page from the ground up, read these 8 pages in order. The foundations come first.

Show the path as a graph
Affine combination, concept, no evidence levelAffine combinationconceptConvex hull, concept, no evidence levelConvex hullconceptEuclidean space, object, no evidence levelEuclidean spaceobjectPartition of a set, concept, no evidence levelPartition of a setconceptCarathéodory's theorem, statement, no evidence levelCarathéodory's theoremstatementRadon's theorem, statement, no evidence levelRadon's theoremstatementColorful Carathéodory theorem, statement, no evidence levelColorful Carathéodory…statementTverberg's theorem, statement, no evidence levelTverberg's theoremstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Affine combination concept
  2. Convex hull concept
  3. Euclidean space object
  4. Partition of a set concept
  5. Carathéodory's theorem statement
  6. Radon's theorem statement
  7. Colorful Carathéodory theorem statement
  8. Tverberg's theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Tverberg%27s_theorem
About this page
TagV21XNZ1H0B
URIm2://V21XNZ1H0B
Kindstatement, theorem
WritingW0 stub
MSC52A35, 52A37
StatusThis copy of the site has no build data. Run m2 status V21XNZ1H0B.
AboutConvex hull
UsesEuclidean space, Convex hull, Partition of a set, Radon's theorem, Colorful Carathéodory theorem
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.