Tverberg's theorem
![](/wiki/images/thumb/5/5b/Tverberg_heptagon.svg/250px-Tverberg_heptagon.svg.png)
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
- [math]\displaystyle{ (d + 1)(r - 1) + 1\ }[/math]
points there exists a point x (not necessarily one of the given points) and a partition of the given points into r subsets, such that x belongs to the convex hull of all of the subsets. The partition resulting from this theorem is known as a Tverberg partition.
The special case r = 2 was proved earlier by Radon, and it is known as Radon's theorem.
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 x1 < x2 < ... < x2r < x2r-1, then the partition into Ai = {xi, x2r-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 Rd, then there are r pairwise-disjoint faces of ΔN whose images under ƒ intersect. That is: there exist faces F1,...,Fr of ΔN such that [math]\displaystyle{ \forall i,j\in[r]: F_i\cap F_j = \emptyset }[/math] and [math]\displaystyle{ f(F_1)\cap\cdots\cap f(F_r)\neq \emptyset }[/math].
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 Rd. Let [math]\displaystyle{ v_1,v_2,\dots,v_{N+1} }[/math] be the vertices of ΔN, and let [math]\displaystyle{ x_1,x_2,\dots,x_{N+1} }[/math] be their images under ƒ. By the original formulation, the [math]\displaystyle{ x_1,x_2,\dots,x_{N+1} }[/math] can be partitioned into r disjoint subsets, e.g. ((xi)i in Aj)j in [r] with overlapping convex hull. Because f is affine, the convex hull of (xi)i in Aj is the image of the face spanned by the vertices (vi)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 Rd, then there are r pairwise-disjoint faces of ΔN whose images under ƒ intersect. That is: there exist faces F1,...,Fr of ΔN such that [math]\displaystyle{ \forall i,j\in[r]: F_i\cap F_j = \emptyset }[/math] and [math]\displaystyle{ f(F_1)\cap\cdots\cap f(F_r)\neq \emptyset }[/math].
Proofs
The topological Tverberg theorem was proved for prime r by Barany, Shlosman and Szucs.[2] Matousek[3]:{{{1}}} 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]
See also
- Rota's basis conjecture
- Tverberg-type theorems and the Fractional Helly property.[7]
References
- ↑ "A generalization of Radon's theorem", Journal of the London Mathematical Society 41: 123–128, 1966, doi:10.1112/jlms/s1-41.1.123, http://jlms.oxfordjournals.org/cgi/reprint/s1-41/1/123.pdf
- ↑ Bárány, I.; Shlosman, S. B.; Szücs, A. (1981-02-01). "On a Topological Generalization of a Theorem of Tverberg" (in en). Journal of the London Mathematical Society s2-23 (1): 158–164. doi:10.1112/jlms/s2-23.1.158. http://doi.wiley.com/10.1112/jlms/s2-23.1.158.
- ↑ Template:Cite Matousek 2007, Section 4.3
- ↑ Ozaydin, Murad (1987) (in en-US). Equivariant Maps for the Symmetric Group. https://minds.wisconsin.edu/handle/1793/63829.
- ↑ Volovikov, A. Yu. (1996-03-01). "On a topological generalization of the Tverberg theorem" (in en). Mathematical Notes 59 (3): 324–326. doi:10.1007/BF02308547. ISSN 1573-8876. https://doi.org/10.1007/BF02308547.
- ↑ Sarkaria, K. S. (2000-11-01). "Tverberg partitions and Borsuk–Ulam theorems". Pacific Journal of Mathematics 196 (1): 231–241. doi:10.2140/pjm.2000.196.231. ISSN 0030-8730. https://msp.org/pjm/2000/196-1/p11.xhtml.
- ↑ Hell, S. (2006), Tverberg-type theorems and the Fractional Helly property, Dissertation, TU Berlin, doi:10.14279/depositonce-1464
![]() | Original source: https://en.wikipedia.org/wiki/Tverberg's theorem.
Read more |