# An Erdős-Szekeres-type 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.)

-

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.)

-

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.

-
Welcome to Mathoverflow! –  David Speyer Aug 31 '11 at 16:37

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$.

-
This seems an interesting approach which reduces all considerations to the cyclic case. Thank you. –  Roland Bacher Jun 15 '11 at 7:16
Just for k=2. For larger k we need more. –  Gil Kalai Jun 15 '11 at 18:40

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.

-

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

-
Tverberg's Theorem has indeed a very similar flavour but I do not see a direct connection. –  Roland Bacher Jun 14 '11 at 14:33
My mistake. I was thinking that Tverberg gives you two intersecting polytopes, and by triangulation this gives you two intersecting simplices $S_1$ and $S_2$; then I thought this would imply that some facet of $S_1$ must intersect some facet of $S_2$, and so on down the dimensions. However, now I see that this reasoning is flawed. If one simplex is entirely contained in another then the facets don't have to intersect. Still, maybe there's some argument along these lines. –  Timothy Chow Jun 14 '11 at 15:06
Dear Timothy, the question is certainly related to Radon's partitions (for k=2), and Tverberg's partition (for karger k). –  Gil Kalai Jun 15 '11 at 15:51

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.

-