Tverberg's theorem

{{short description|On partitions into intersecting convex hulls}}

File:Tverberg heptagon.svg into three subsets with intersecting convex hulls.]]

In discrete geometry, Tverberg's theorem, first stated by Helge Tverberg in 1966,{{citation

| last = Tverberg | first = H. | author-link = Helge Tverberg

| journal = Journal of the London Mathematical Society

| pages = 123–128

| title = A generalization of Radon's theorem

| url = http://jlms.oxfordjournals.org/cgi/reprint/s1-41/1/123.pdf

| volume = 41

| year = 1966

| doi=10.1112/jlms/s1-41.1.123}} is the result that sufficiently many points in Euclidean space can be partitioned into subsets with intersecting convex hulls. Specifically, for any positive integers $d, r$ and any set of

: $(d + 1)(r - 1) + 1\$

points in $d$ -dimensional Euclidean space there exists a partition of the given points into $r$ subsets whose convex hulls all have a common point; in other words, there exists a point $x$ (not necessarily one of the given points) 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 $x_1 < x_2 < ... < x_{2r-1}$ , then the partition into $A_i = \{x_i, x_{2r-i}\}$ for $i = 1,...,r$ satisfies this condition (and it is unique).

For $r = 2$ Tverberg's theorem states that any $d + 2$ points in the $d$ -dimensional Euclidean space 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.

{{Anchor|topological}}Topological Tverberg Theorem

An equivalent formulation of Tverberg's theorem is the following:

Let $d,r$ be positive integers, and let $N := (d+1)(r-1)$ . If $f$ is any affine function from an $N$ -dimensional simplex $\Delta^N$ to $\R^d$ , then there are $r$ pairwise-disjoint faces of $\Delta^N$ whose images under $f$ intersect. That is: there exist faces $F_1 ,..., F_r$ of $\Delta^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

f

be an affine function from

\Delta^N

\R^d

. Let

v_1,v_2,\dots,v_{N+1}

be the vertices of

\Delta^N

and

x_1,x_2,\dots,x_{N+1}

be their images under

f

. 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 A_j\})_{j \in [r]}

with overlapping convex hull. Because

f

is affine, the convex hull of

\{x_i : i \in A_j\}

is the image of the face spanned by the vertices

\{v_i : i \in A_j\}

for all

j \in [r]

. These faces are pairwise-disjoint, and their images under

f

intersect, as claimed by the reformulation.

The topological Tverberg theorem (first hypothesized by Bárány in a 1976 letter to Tverberg{{citation |last1=Blagojević |first1=P. V. M. |last2=Ziegler |first2=G. M. |editor-last=Loebl |editor-first=M. |editor-last2=Nešetřil |editor-first2=J. |editor-last3=Thomas | editor-first3=R. |date=2017 |contribution=Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story |title=A Journey Through Discrete Mathematics |contribution-url=https://link.springer.com/chapter/10.1007/978-3-319-44479-6_11 |publisher=Springer, Cham |language=en |pages=273–341 |doi=10.1007/978-3-319-44479-6_11|isbn=978-3-319-44478-9 }}) generalizes this formluation. It allows $f$ to be any continuous function—not necessarily affine. However, it only holds in the case where $r$ is a prime power:

Let $d$ be a positive integer, and $r$ be a power of a prime number. Let $N := (d+1)(r-1)$ . If $f$ is any continuous function from an $N$ -dimensional simplex $\Delta^N$ to $\R^d$ , then there are $r$ pairwise-disjoint faces of $\Delta^N$ whose images under $f$ intersect. That is: there exist faces $F_1 ,..., F_r$ of $\Delta^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 and Refutations =

The topological Tverberg theorem was proved for prime $r$ by Bárány, Shlosman and Szűcs.{{citation |last1=Bárány |first1=I. |last2=Shlosman |first2=S. B. |last3=Szűcs |first3=A. |date=February 1981 |title=On a Topological Generalization of a Theorem of Tverberg |url=http://doi.wiley.com/10.1112/jlms/s2-23.1.158 |journal=Journal of the London Mathematical Society |language=en |volume=s2-23 |issue=1 |pages=158–164 |doi=10.1112/jlms/s2-23.1.158}} Matoušek{{Cite Matousek 2007|mode=cs2}}, Section 4.3, pp. 162-163 presents a proof using deleted joins.

The theorem was proved for $r$ a prime-power by Özaydin,{{citation |type=preprint|last=Özaydin |first=M. |date=1987 |title=Equivariant Maps for the Symmetric Group |hdl=1793/63829|publisher=University of Wisconsin-Madison}} and later by Volovikov{{citation |last=Volovikov |first=A. Yu. |date=March 1996 |title=On a topological generalization of the Tverberg theorem |url=https://doi.org/10.1007/BF02308547 |journal=Mathematical Notes |language=en |volume=59 |issue=3 |pages=324–326 |doi=10.1007/BF02308547 |s2cid=122078369 |issn=1573-8876}} and Sarkaria.{{citation |last=Sarkaria |first=K. S. |date=November 2000 |title=Tverberg partitions and Borsuk–Ulam theorems |url=https://msp.org/pjm/2000/196-1/p11.xhtml |journal=Pacific Journal of Mathematics |volume=196 |issue=1 |pages=231–241 |doi=10.2140/pjm.2000.196.231 |issn=0030-8730|doi-access=free }}

It was a long-standing open problem, whether the statement of the topological Tverberg theorem also holds for arbitrary (i.e. non-prime-power) $r$ . However, in 2015 Frick{{cite arXiv |mode=cs2 |last=Frick |first=F. |date=2015 |title=Counterexamples to the topological Tverberg conjecture |class=math.CO |eprint=1502.00947}} observed that a synthesis of the work of Özaydin, the " $r$ -fold Whitney trick" by Mabillard and Wagner,{{citation |last1=Mabillard |first1=I. |last2=Wagner |first2=U. |title=Proceedings of the thirtieth annual symposium on Computational geometry |chapter=Eliminating Tverberg Points, I. An Analogue of the Whitney Trick |date=2014 |url=https://dl.acm.org/doi/10.1145/2582112.2582134 |language=en |pages=171–180 |doi=10.1145/2582112.2582134|isbn=978-1-4503-2594-3 }} and the "constraint method" by Blagojević, Ziegler and Frick{{citation |last1=Blagojević |first1=P. V. M. |last2=Frick |first2=F. |last3=Ziegler |first3=G. M. |date=2014 |title=Tverberg plus constraints |url=https://londmathsoc.onlinelibrary.wiley.com/doi/full/10.1112/blms/bdu049 |journal=Bulletin of the London Mathematical Society |language=en |volume=46 |issue=5 |pages=953–967 |doi=10.1112/blms/bdu049|arxiv=1401.0690 }} leads to counterexamples.

Tverberg's theorem

Examples

{{Anchor|topological}}Topological Tverberg Theorem

= Proofs and Refutations =

See also

References

Further reading