Erd?s-Szekeres-Type Question – Combinatorial Analysis

co.combinatorics

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

Best Answer

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

Related Question