An Erdős-Szekeres-type question - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T19:15:45Z http://mathoverflow.net/feeds/question/67762 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/67762/an-erds-szekeres-type-question An Erdős-Szekeres-type question Roland Bacher 2011-06-14T13:56:56Z 2011-11-04T13:13:04Z <p>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?</p> <p>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?</p> <p>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.</p> <p>(The Erdős-Szekeres Theorem shows of course that it is enough to consider points in convex position for all questions mentioned above.)</p> http://mathoverflow.net/questions/67762/an-erds-szekeres-type-question/67766#67766 Answer by Timothy Chow for An Erdős-Szekeres-type question Timothy Chow 2011-06-14T14:18:26Z 2011-06-14T14:18:26Z <p>Without the constraint of being simplices, this looks like <a href="http://en.wikipedia.org/wiki/Tverberg%27s_theorem" rel="nofollow">Tverberg's theorem</a>. I think that the case of simplices follows by triangulation.</p> http://mathoverflow.net/questions/67762/an-erds-szekeres-type-question/67790#67790 Answer by domotorp for An Erdős-Szekeres-type question domotorp 2011-06-14T18:16:21Z 2011-06-14T18:16:21Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/67762/an-erds-szekeres-type-question/67800#67800 Answer by Martin Tancer for An Erdős-Szekeres-type question Martin Tancer 2011-06-14T20:05:51Z 2011-06-14T20:05:51Z <p>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).</p> <p>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.)</p> http://mathoverflow.net/questions/67762/an-erds-szekeres-type-question/67803#67803 Answer by Gil Kalai for An Erdős-Szekeres-type question Gil Kalai 2011-06-14T20:30:27Z 2011-06-15T18:39:13Z <p>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.</p> <p>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.</p> <p>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$.</p> http://mathoverflow.net/questions/67762/an-erds-szekeres-type-question/67881#67881 Answer by mikhail skopenkov for An Erdős-Szekeres-type question mikhail skopenkov 2011-06-15T18:40:54Z 2011-06-15T18:40:54Z <p>The answer is YES in the case $k=3, d=3, d_1=d_2=d_3=2$.</p> <p>A required number N is given by </p> <p>The Negami Theorem [1]. <em>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.</em> </p> <p>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.</p> <p>[1] S. Negami, Ramsey-type theorem for spatial graphs, Graphs and Combin. 14 (1998), 75–80.</p> http://mathoverflow.net/questions/67762/an-erds-szekeres-type-question/74140#74140 Answer by Günter M. Ziegler for An Erdős-Szekeres-type question Günter M. Ziegler 2011-08-31T07:08:36Z 2011-08-31T07:08:36Z <p>The answer is YES if all the $d_i$ are at least $\lfloor d/2\rfloor$, and NO otherwise.</p> <p>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.</p> <p>For the YES: We rely on the high-dimensional version of Erdös-Szekeres as quoted by Gil Kalai.<br> (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.)</p> <p>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.</p>