Tverberg's theorem

Last updated March 27, 2023

In discrete geometry, Tverberg's theorem, first stated by Helge Tverberg in 1966,^[1], is the result that sufficiently many points in d-dimensional Euclidean space can be partitioned into subsets with intersecting convex hulls. Specifically, for any positive integers d, r and any set of

Examples

The case d = 1 states that any 2r-1 points on the real line can be partitioned into r subsets with intersecting convex hulls. Indeed, if the points are x₁ < x₂ < ... < x_2r < x_2r-1, then the partition into A_i = {x_i, x_2r-i} for i in 1,...,r satisfies this condition (and it is unique).

For r = 2, Tverberg's theorem states that any d + 2 points may be partitioned into two subsets with intersecting convex hulls. This is known as Radon's theorem. In this case, for points in general position, the partition is unique.

The case r = 3 and d = 2 states that any seven points in the plane may be partitioned into three subsets with intersecting convex hulls. The illustration shows an example in which the seven points are the vertices of a regular heptagon. As the example shows, there may be many different Tverberg partitions of the same set of points; these seven points may be partitioned in seven different ways that differ by rotations of each other.

Topological Tverberg Theorem

An equivalent formulation of Tverberg's theorem is:

Let d, r be positive integers, and let N := (d+1)(r-1). If ƒ is any affine function from an N-dimensional simplex Δ^N to R ^d, then there are r pairwise-disjoint faces of Δ^N whose images under ƒ intersect. That is: there exist faces F₁,...,F_r of Δ^N such that $\forall i,j\in [r]:F_{i}\cap F_{j}=\emptyset$ and $f(F_{1})\cap \cdots \cap f(F_{r})\neq \emptyset$ .

They are equivalent because any affine function on a simplex is uniquely determined by the images of its vertices. Formally, let ƒ be an affine function from Δ^N to R ^d. Let $v_{1},v_{2},\dots ,v_{N+1}$ be the vertices of Δ^N, and let $x_{1},x_{2},\dots ,x_{N+1}$ be their images under ƒ. By the original formulation, the $x_{1},x_{2},\dots ,x_{N+1}$ can be partitioned into r disjoint subsets, e.g. ((x_i)_{i in Aj})_{j in [r]} with overlapping convex hull. Because f is affine, the convex hull of (x_i)_{i in Aj} is the image of the face spanned by the vertices (v_i)_{i in Aj} for all j in [r]. These faces are pairwise-disjoint, and their images under f intersect - as claimed by the new formulation. The topological Tverberg theorem generalizes this formluation. It allows f to be any continuous function - not necessarily affine. But, currently it is proved only for the case where r is a prime power:

Let d be a positive integer, and let r be a power of a prime number. Let N := (d+1)(r-1). If ƒ is any continuous function from an N-dimensional simplex Δ^N to R ^d, then there are r pairwise-disjoint faces of Δ^N whose images under ƒ intersect. That is: there exist faces F₁,...,F_r of Δ^N such that $\forall i,j\in [r]:F_{i}\cap F_{j}=\emptyset$ and $f(F_{1})\cap \cdots \cap f(F_{r})\neq \emptyset$ .

Proofs

The topological Tverberg theorem was proved for prime r by Barany, Shlosman and Szucs.^[2] Matousek^[3]^: 162--163 presents a proof using deleted joins.

The theorem was proved for r a prime-power by Ozaydin,^[4] and later by Volovikov^[5] and Sarkaria.^[6]

Related Research Articles

In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint non-empty open subsets. Connectedness is one of the principal topological properties that are used to distinguish topological spaces.

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersects every line into a single line segment . For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex.

In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism group of the structure. It is said that the group acts on the space or structure. If a group acts on a structure, it will usually also act on objects built from that structure. For example, the group of Euclidean isometries acts on Euclidean space and also on the figures drawn in it. For example, it acts on the set of all triangles. Similarly, the group of symmetries of a polyhedron acts on the vertices, the edges, and the faces of the polyhedron.

In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of n-dimensional Euclidean space. For n = 1, 2, or 3, it coincides with the standard measure of length, area, or volume. In general, it is also called n-dimensional volume, n-volume, or simply volume. It is used throughout real analysis, in particular to define Lebesgue integration. Sets that can be assigned a Lebesgue measure are called Lebesgue-measurable; the measure of the Lebesgue-measurable set A is here denoted by λ(A).

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

In mathematics, an extreme point of a convex set $in a real or complex vector space is a point in which does not lie in any open line segment joining two points of In linear programming problems, an extreme point is also called vertex or corner point of$

In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles, their edges, and their vertices.

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth (1950).

Carathéodory's theorem is a theorem in convex geometry. It states that if a point $lies in the convex hull of a set, then can be written as the convex combination of at most points in . More sharply, can be written as the convex combination of at most extremal points in, as non-extremal points can be removed from without changing the membership of in the convex hull.$

In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that:

Any set of d + 2 points in R^d can be partitioned into two sets whose convex hulls intersect.

Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913, but not published by him until 1923, by which time alternative proofs by Radon (1921) and König (1922) had already appeared. Helly's theorem gave rise to the notion of a Helly family.

<span class="mw-page-title-main">Triangulation (topology)</span>

In mathematics, triangulation describes the replacement of topological spaces by piecewise linear spaces, i.e. the choice of a homeomorphism in a suitable simplicial complex. Spaces being homeomorphic to a simplicial complex are called triangulable. Triangulation has various uses in different branches of mathematics, for instance in algebraic topology, in complex analysis or in modeling.

<span class="mw-page-title-main">Join (topology)</span>

In topology, a field of mathematics, the join of two topological spaces $and, often denoted by or, is a topological space formed by taking the disjoint union of the two spaces, and attaching line segments joining every point in to every point in . The join of a space with itself is denoted by . The join is defined in slightly different ways in different contexts$

In the mathematical theory of functional analysis, the Krein–Milman theorem is a proposition about compact convex sets in locally convex topological vector spaces (TVSs).

In mathematics, Choquet theory, named after Gustave Choquet, is an area of functional analysis and convex analysis concerned with measures which have support on the extreme points of a convex set C. Roughly speaking, every vector of C should appear as a weighted average of extreme points, a concept made more precise by generalizing the notion of weighted average from a convex combination to an integral taken over the set E of extreme points. Here C is a subset of a real vector space V, and the main thrust of the theory is to treat the cases where V is an infinite-dimensional topological vector space along lines similar to the finite-dimensional case. The main concerns of Gustave Choquet were in potential theory. Choquet theory has become a general paradigm, particularly for treating convex cones as determined by their extreme rays, and so for many different notions of positivity in mathematics.

In geometry, the hyperplane separation theorem is a theorem about disjoint convex sets in n-dimensional Euclidean space. There are several rather similar versions. In one version of the theorem, if both these sets are closed and at least one of them is compact, then there is a hyperplane in between them and even two parallel hyperplanes in between them separated by a gap. In another version, if both disjoint convex sets are open, then there is a hyperplane in between them, but not necessarily any gap. An axis which is orthogonal to a separating hyperplane is a separating axis, because the orthogonal projections of the convex bodies onto the axis are disjoint.

In the mathematical field of topology, a hyperconnected space or irreducible space is a topological space X that cannot be written as the union of two proper closed sets. The name irreducible space is preferred in algebraic geometry.

In mathematics, a separoid is a binary relation between disjoint sets which is stable as an ideal in the canonical order induced by inclusion. Many mathematical objects which appear to be quite different, find a common generalisation in the framework of separoids; e.g., graphs, configurations of convex sets, oriented matroids, and polytopes. Any countable category is an induced subcategory of separoids when they are endowed with homomorphisms.

In geometry, the moment curve is an algebraic curve in d-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form

A geometric separator is a line that partitions a collection of geometric shapes into two subsets, such that proportion of shapes in each subset is bounded, and the number of shapes that do not belong to any subset is small.

References

↑ Tverberg, H. (1966), "A generalization of Radon's theorem" (PDF), Journal of the London Mathematical Society , 41: 123–128, doi:10.1112/jlms/s1-41.1.123
↑ Bárány, I.; Shlosman, S. B.; Szücs, A. (1981-02-01). "On a Topological Generalization of a Theorem of Tverberg". Journal of the London Mathematical Society. s2-23 (1): 158–164. doi:10.1112/jlms/s2-23.1.158.
↑ Matoušek, Jiří (2007). Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry (2nd ed.). Berlin-Heidelberg: Springer-Verlag. ISBN 978-3-540-00362-5. Written in cooperation with Anders Björner and Günter M. Ziegler , Section 4.3
↑ Ozaydin, Murad (1987). "Equivariant Maps for the Symmetric Group".{{cite journal}}: Cite journal requires |journal= (help)
↑ Volovikov, A. Yu. (1996-03-01). "On a topological generalization of the Tverberg theorem". Mathematical Notes. 59 (3): 324–326. doi:10.1007/BF02308547. ISSN 1573-8876.
↑ Sarkaria, K. S. (2000-11-01). "Tverberg partitions and Borsuk–Ulam theorems". Pacific Journal of Mathematics. 196 (1): 231–241. ISSN 0030-8730.
↑ Hell, S. (2006), Tverberg-type theorems and the Fractional Helly property, Dissertation, TU Berlin, doi:10.14279/depositonce-1464

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Tverberg, H. (1966), "A generalization of Radon's theorem" (PDF), Journal of the London Mathematical Society , 41: 123–128, doi:10.1112/jlms/s1-41.1.123

[2] Bárány, I.; Shlosman, S. B.; Szücs, A. (1981-02-01). "On a Topological Generalization of a Theorem of Tverberg". Journal of the London Mathematical Society. s2-23 (1): 158–164. doi:10.1112/jlms/s2-23.1.158.

[:03-3] Matoušek, Jiří (2007). Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry (2nd ed.). Berlin-Heidelberg: Springer-Verlag. ISBN 978-3-540-00362-5. Written in cooperation with Anders Björner and Günter M. Ziegler , Section 4.3

[4] Ozaydin, Murad (1987). "Equivariant Maps for the Symmetric Group".{{cite journal}}: Cite journal requires |journal= (help)

[5] Volovikov, A. Yu. (1996-03-01). "On a topological generalization of the Tverberg theorem". Mathematical Notes. 59 (3): 324–326. doi:10.1007/BF02308547. ISSN 1573-8876.

[6] Sarkaria, K. S. (2000-11-01). "Tverberg partitions and Borsuk–Ulam theorems". Pacific Journal of Mathematics. 196 (1): 231–241. ISSN 0030-8730.

[7] Hell, S. (2006), Tverberg-type theorems and the Fractional Helly property, Dissertation, TU Berlin, doi:10.14279/depositonce-1464

[1]

[2]

[3]

[4]

[5]

[6]

[7]