An Erdős-Szekeres-type question

Question

Does there exist an integer $N$ such that every set of $\geq N$ points in $\mathbb R^4$ contains six distinct points which are vertices of two intersecting triangles?

More generally, given dimensions $d_1,\dots,d_k$ such that generic affine subspaces of $\mathbb R^d$ of dimensions $d_1,\dots,d_k$ intersect in a point, does every large enough (but finite) set of $\mathbb R^d$ contain $k+\sum_i d_i$ distinct points defining $k$ simplices of dimension $d_1,\dots,d_k$ intersecting in a point?

There are many variations on this problem. For example: Given an integer $k$, does every large enough subset of $\mathbb R^4$ contain the vertices of $k$ triangles (with all $3k$ vertices distinct) such that all triangles intersect pairwise? The corresponding planar problem has a positive answer: By the Erdős Szekeres theorem, every large enough subset of $\mathbb R^2$ (in generic positition) contains $2k$ points in convex position. This defines $k$ "diagonals" which are all pairwise intersecting.

(The Erdős-Szekeres Theorem shows of course that it is enough to consider points in convex position for all questions mentioned above.)

Answer 1

The answer to the first question is yes (with $N = 7$). Consider a $2$-dimensional simplicial complex $K$ with 7 vertices and with all possible triangles. Assume there are 7 points in $\mathbb R^4$. You can construct a linear mapping $f \colon |K| \rightarrow \mathbb R^4$ ($|K|$ denotes the geometric realization of the complex). It is well known that $K$ does not embed into $\mathbb R^4$. More precisely, so called Van Kampen obstruction of this complex is nonzero, and this implies that for any continuous map $f'\colon |K| \rightarrow \mathbb R^4$ there are two vertex disjoint simplices $\sigma, \tau$ of $K$ whose images $f(|\sigma|), f(|\tau|)$ intersect. If you aply this result on $f$ you get the desired conclusion. In an unlikely case that $\sigma$ or $\tau$ have smaller dimension then 2, you simply extend them to triangles (this may occur only if the points are not in generic position).

This reasoning extends to the case $k = 2$, $d_1, d_2 = m$ for some parameter $m$, $d = 2m$ and $N = 2m + 3$. (At the moment, I am not able to answer the general question, however.)

Answer 2

The answer is YES if all the $d_i$ are at least $\lfloor d/2\rfloor$, and NO otherwise.

For the NO: as the cyclic polytopes $C_d(n)$ are $\lfloor d/2\rfloor$-neighborly, there are arbitrarily large point sets where no simplex spanned by $\lfloor d/2\rfloor$ points intersects any simplex (even $d$-simplex) spanned by other points.

For the YES: We rely on the high-dimensional version of Erdös-Szekeres as quoted by Gil Kalai.
(For references, this is Exercise 6(i) of Section 7.3, page 126 of Grünbaum's polytopes book, where however only "neighborly" is claimed/stated. The full claim for "cyclic" with a proof is given in Proposition 9.4.7, page 398, of the five-author oriented matroid by Björner et al. Indeed we get - and will use - the stronger condition that also all subpolytopes will be cyclic.)

Thus we can assume that our point set contains/is the vertex set of of a $d$-dimensional cyclic polytope on $(d_1+1)+\cdots+(d_k+1)$ vertices. Also assume w.l.o.g. that $d_1\ge d_2\ge\cdots\ge d_k$. Now if we assign the vertices to simplices by taking rounds - that is, first vertex to $\Delta_1$, second to $\Delta_2$, ... , $k$-th to $\Delta_k$, $(k+1)$-st to $\Delta_1$ again etc., we get a partition of the vertex set into simplices. One checks that they pairwise intersect using the combinatorics of cyclic polytopes and the Gale evenness criterion. For this, the key fact is that when we look at the vertices of $\Delta_i$ and $\Delta_j$, then they come in alternating order on the cyclic polytope. Together, they have at least $d+2$ vertices. Finally, the combinatorics of a cyclic polytope on $d+2$ vertices is that of two simplices that intersect in point that is relative-interior to both of them.

Answer 3

It is useful to know the following Erdos-Szekeres fact: For every k > d there is N(k,d) so that every N points in general position in R^d contains k points in "cyclic position". We say that d points $x_1, x_2,...x_d$ are in cyclic position if all the simplices $x_{i_1},...,x_{i_{d+1}}$ have the same orientation. This fact follows from Ramsey's theorem. (With very large N(k,d).) It implies various results of the kind ask here if they refer to properties of points in cyclic positions.

This gives a complete answer for the case $k=2$ of the original question. Indeed it is useful to think about the original problem as for which sizes $d_1,d_2\dots,d_k$ whose sum is $(d+1)(k-1)+1$ if N is large enough and we have $N$ points in $R^d$ we can find a subset of $(d+1)(k-1)+1$ points with Tverberg partition of sizes $d_1,d_2,\dots,d_k$. When it comes to Radon partitions points in cyclic position are "cannonical". For larger values of $k$ I dont know the precise situation. We can look at lexicographic sequence of points on the moment curve and this is a property inherited by subsequences. (So it will exclude plenty of $d_i$ sequences.) But I am not sure every large set of points "contains" a lexicographic sequence of points on the moment curve. ("contains" in terms of having equivalent Tverberg's behavior.) So there is more to explore.

By the way, an interesting higher dimensional question is what is the number f(n,d) so that every f(n,d) points in general position in $R^d$ contains $n$ points in convex position. This is monotonic non-increasing in $d$.

Answer 4

Edit: The argument below is incorrect because 3 surfaces spanning Borromean rings do not necessarily have a common point. Thanks to Sergey Avvakumov for pointing out that. It is better to remove this answer.

The answer is YES in the case $k=3, d=3, d_1=d_2=d_3=2$.

A required number N is given by

The Negami Theorem [1]. For any link L there is a number N such that for any set of N generic points in 3-space there is a link L' isotopic to L formed by broken lines with all the vertices belonging to the given set.

To apply the theorem take L to be, e.g., Borromean rings. It is easy to span each component of L' by a surface formed by triangles with vertices belonging to the given set. Since L' is isotopic to Borromean rings it follows that 3 constructed surfaces have a common point. Thus there must be 3 triangles with a common point.

[1] S. Negami, Ramsey-type theorem for spatial graphs, Graphs and Combin. 14 (1998), 75–80.

Answer 5

Without the constraint of being simplices, this looks like Tverberg's theorem. I think that the case of simplices follows by triangulation.

Answer 6

In 3-dim, it is true that there is a segment intersecting a triangle. Proof: Take many points in convex position. These define a polytope. If this polytope has a large face, then we can use the planar version and find two intersecting segments, which can be, of course, extended to an intersecting triangle and segment. Take one of the vertices of the polytope, v. If v does not have many neighbors, then since every face is small, there is a u that does not appear on the same face as v, so int(uv) is in the interior of the polytope, in which case we are easily done. If v has many neighbors, then project them from v to a plane and find two intersecting segments. One is behind the other, adding v to it we get a triangle intersecting a segment.

I am not sure if one can make this work in 4-dim, as there we have an intersecting triangle and segment and these are not symmetric.

Answer 7

For the particular question on $N$ points in 4-space one can take $N=7$ (as answered by Martin Tancer). Observe that there is a much simpler proof (based on the idea of Mikhail Skopenkov), see survey [1, $\S$2.3]. (I plan to update [1] simplifying that proof even further.)

Let me provide some optimal bounds for certain values of the parameters. This paragraph is a complement to the answer of G\"unter Ziegler, but can be read independently. The van Kampen-Flores theorem on 7 points in 4-space generalizes to the general question on points in $d$-space. Assume that $d=kn$, $d_1=\ldots=d_k=(k-1)n+1$. Then clearly one cannot take $N=(kn+2)(k-1)$. But if $N=(kn+2)(k-1)+1$, the answer to the general question is yes for $k$ a prime power! This is the $k$-fold linear van Kampen-Flores theorem proved by Karanbir Sarkaria ($k$ prime) and Alexey Volovikov ($k$ prime power). Analogous statement is an unsolved problem when $k$ is not a prime power. I presume that for a prime power $k$ generalization to arbitrary $d_1,\ldots,d_k$ would be not hard (but worth writing a paper). See surveys [2, Conjectures 3.1.4 and 3.1.8], [3, Remark 1.1.d].

There is analogous interesting question for intersection replaced by linking. E.g. see [1, Linear Conway-Gordon-Sachs Theorem 1.1], [3, Problem 4.4.d]. In particular, what is the minimal $N$ in the Negami Theorem (cited above by Mikhail Skopenkov) for Borromean rings $L$? Can one take $N=9$? See https://en.wikipedia.org/wiki/Valknut.

[1] https://arxiv.org/pdf/1402.0658.pdf

[2] https://arxiv.org/pdf/1805.10237.pdf, Conjectures 3.1.4 and 3.1.8,

[3] A. Skopenkov, A user's guide to the topological Tverberg Conjecture, Russian Math. Surveys, 73:2 (2018), 323-353, Remark 1.1.d (will soon be available as an update of https://arxiv.org/pdf/1605.05141.pdf).

(I plan to update [2] and [3] adding reference to K. S. Sarkaria. A generalized Van Kampen-Flores theorem, Proc. Amer. Math. Soc.111 (1991), 559–565.)