Above and below
Wenchong Chen, Cosmin Pohoata · 2026
Read Above and below by Wenchong Chen, Cosmin Pohoata (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-27061.txt.
Introduction
In their 2026 paper, Chen and Pohoata study above-below Ramsey functions for point sequences in d-dimensional space whose projections have cyclic order type. For three dimensions, they prove the sharp estimate that the function equals two raised to two raised to a linear function of k. More generally, the higher-dimensional functions relate closely to the higher-order cup-cap function and the monotone Ramsey numbers of Balko.
Catalog record
| CREATOR | Wenchong Chen, Cosmin Pohoata |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31193 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.27061
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Above and below Wenchong Chen, Cosmin Pohoata Abstract We study a family of above-below Ramsey functions AB ( d ) ( k ) \operatorname{AB}^{(d)}(k) defined for sequences of points in ℝ d \mathbb{R}^{d} whose projections to ℝ d − 1 \mathbb{R}^{d-1} have cyclic order type. The case d = 3 d=3 is the above-below function AB ( k ) \operatorname{AB}(k) that was first introduced by Pohoata and Zakharov in their work on the Erdős–Szekeres problem in ℝ 3 \mathbb{R}^{3} . We prove the sharp estimate AB ( k ) = 2 2 Θ ( k ) , \operatorname{AB}(k)=2^{2^{\Theta(k)}}, and, more generally, show that AB ( d ) ( k ) \operatorname{AB}^{(d)}(k) is closely related to the higher-order cup-cap function of Eliáš and Matoušek and the monotone Ramsey numbers of Balko. 1 Introduction In a seminal paper [ 5 ] , Erdős and Szekeres initiated one of the central threads of combinatorial geometry by proving that every sufficiently large set of points in the plane in general position contains a large subset in convex position. More generally, for d\geq 2 , let ES_{d}(n) denote the smallest integer such that every set of at least ES_{d}(n) points in \mathbb{R}^{d} in general position contains n points in convex position. The existence of ES_{d}(n) follows from Ramsey’s theorem, but the asymptotic behavior of these functions remained mysterious until recent years. In the plane, it has been long known since 1935 that ES_{2}(n) is exponential in n , and in a celebrated paper from about ten years ago Suk [ 14 ] established that ES_{2}(n)=2^{n+o(n)} . See also [ 8 ] for the best known quantitative bound, as well as a generalization to the pseudoline setting. In higher dimensions, the situation is dramatically different. Answering a question of Erdős (see for instance [ 2 ] ), Pohoata and Zakharov established that ES_{d}(n)=2^{o(n)} for every fixed d\geq 3 , by showing that already in \mathbb{R}^{3} substantially fewer points are needed to force a convex polytope on n vertices than are required in the plane [ 11 ] . One of the ingredients in the proof from [ 11 ] is a Ramsey-type statement about points in space with convexly ordered planar projections. Let x_{1},\dots,x_{N}\in\mathbb{R}^{3} be points in general position whose orthogonal projections onto the first two coordinates \pi(x_{1}),\dots,\pi(x_{N})\in\mathbb{R}^{2} are the consecutive vertices of a convex polygon. If i<i^{\prime}<j<j^{\prime} , then the projected segments \pi(x_{i})\pi(x_{j}) and \pi(x_{i^{\prime}})\pi(x_{j^{\prime}}) cross in exactly one point. We say that the segment x_{i}x_{j} is above x_{i^{\prime}}x_{j^{\prime}} if, over this crossing point, the point of x_{i}x_{j} has larger third coordinate than the corresponding point of x_{i^{\prime}}x_{j^{\prime}} . Otherwise, we say that x_{i}x_{j} is below x_{i^{\prime}}x_{j^{\prime}} . For k\geq 4 , let \operatorname{AB}(k) be the smallest integer N such that every such sequence x_{1},\dots,x_{N}\in\mathbb{R}^{3} contains indices 1\leq i_{1}<\cdots<i_{k}\leq N for which either x_{i_{r}}x_{i_{t}}\text{ is above }x_{i_{s}}x_{i_{u}}\qquad\text{for all }1\leq r<s<t<u\leq k, or x_{i_{r}}x_{i_{t}}\text{ is below }x_{i_{s}}x_{i_{u}}\qquad\text{for all }1\leq r<s<t<u\leq k. In [ 11 ] , this function is bounded by a straightforward application of Ramsey’s theorem for 4 -uniform Ramsey numbers: \operatorname{AB}(k)\leq R_{4}(k,k) . This was sufficient for the qualitative subexponential bound on ES_{3}(n) , but the problem of determining the asymptotic value of \operatorname{AB}(k) as k\to\infty remained an intriguing open question (one which the authors of [ 11 ] also highlighted). The main goal of this note is to solve this problem, by establishing the following sharp asymptotic estimate. Theorem 1 . There exist absolute constants c,C>0 such that for all k\geq 4 , 2^{2^{ck}}\leq\operatorname{AB}(k)\leq 2^{2^{Ck}}. Equivalently, \operatorname{AB}(k)=2^{2^{\Theta(k)}}. Theorem 1 comes from a new connection that we will establish with the work of Eliáš and Matoušek [ 6 ] . In their setting, one starts with a planar sequence of points p_{i}=(t_{i},h_{i}) , where t_{1}<\cdots<t_{N} , and two-colors each ordered 4 -tuple i<j<k<\ell according to the sign of the expression \Delta_{3}(p_{i},p_{j},p_{k},p_{\ell})=\sum_{a\in\{i,j,k,\ell\}}\frac{h_{a}}{\prod_{b\in\{i,j,k,\ell\}\setminus\{a\}}(t_{a}-t_{b})}. (1) This is the so-called third divided difference of p_{i},p_{j},p_{k},p_{\ell} , which we will review more closely in Section 2. A subsequence of points is called third-order monotone if all of its 4 -tuples have the same color, and we denote by \operatorname{EM}^{(3)}(k) the smallest integer N such that every planar sequence p_{1},\dots,p_{N} , with p_{i}=(t_{i},h_{i}) , and t_{1}<\cdots<t_{N} , in 3 -general position contains a third-order monotone subsequence of size k . In [ 6 ] , Eliáš and Matoušek proved that this function is doubly exponential in k . Their construction turns out to be the main input behind the lower bound in Theorem 1 . The main idea is roughly as follows. If we restrict to points of the form x_{1}=(t_{1},t_{1}^{2},h_{1}),\ldots,x_{N}=(t_{N},t_{N}^{2},h_{N})\in\mathbb{R}^{3} in the definition of \operatorname{AB}(k) , then the projections \pi(x_{i}) lie on the parabola y=x^{2} . For a quadruple i<j<k<\ell , a direct calculation shows that the above–below comparison between the two crossing lifted diagonals x_{i}x_{k} and x_{j}x_{\ell} is dictated by the sign of a single determinant. A direct calculation then shows that this determinant equals a positive Vandermonde factor times the third divided difference \Delta_{3}(p_{i},p_{j},p_{k},p_{\ell}) . Consequently, up to a global interchange of the two colors, the above–below coloring in the parabola model is exactly the third-order divided-difference coloring from ( 1 ). Before we make things more precise, let us introduce a natural higher-dimensional version of the above-below problem, for which we can establish the connection with the higher-order cup-cap functions of Eliáš and Matoušek in much greater generality. Higher-dimensional above and below. Let d\geq 2 , and write points of \mathbb{R}^{d} as x_{i}=(z_{i},h_{i}) , with z_{i}\in\mathbb{R}^{d-1} and h_{i}\in\mathbb{R} . Let \pi:\mathbb{R}^{d}\to\mathbb{R}^{d-1},\qquad\pi(z,h)=z be the projection onto the first d-1 coordinates. We say that a sequence x_{1},\dots,x_{N}\in\mathbb{R}^{d} has cyclic projections if the projected sequence z_{i}=\pi(x_{i})\in\mathbb{R}^{d-1} has the same order type as points \gamma(t_{i})=(t_{i},t_{i}^{2},\dots,t_{i}^{d-1}) , t_{1}<\cdots<t_{N} on the moment curve. For points on the moment curve, it is known that the primitive Radon partitions of the cyclic polytope C(n,d-1) are exactly the alternating partitions along the moment curve (see for example, the work of Breen [ 3 ] ). In particular, every ordered (d+1) -tuple z_{i_{0}},z_{i_{1}},\dots,z_{i_{d}} , with i_{0}<i_{1}<\cdots<i_{d} has Radon partition \{z_{i_{j}}:j\ \mathrm{even}\} versus \{z_{i_{j}}:j\ \mathrm{odd}\} , up to swapping the two parts. Since Radon partitions of minimally dependent subsets are determined by the order type 1 1 1 This follows from the uniqueness (up to swapping sides) of the Radon partition in Radon’s theorem [ 12 ] for d+1 points in general position in \mathbb{R}^{d-1} . Indeed, for such a (d+1) -tuple in \mathbb{R}^{d-1} , the signs of the coefficients in its affine dependence are determined by the signs of the d\times d minors obtained by deleting one point at a time. These signs are part of the order type. Thus configurations with the same order type have the same Radon partitions on all minimally dependent subsets. See also [ 15 ] for more background on cyclic polytopes. , the same statement holds for any projected sequence with cyclic order type. For such a tuple, let \rho\in\mathbb{R}^{d-1} be the Radon point. After a normalization, this means that there exist positive coefficients \alpha_{j},\beta_{j} , such that \sum_{j\ \mathrm{even}}\alpha_{j}=1 and \sum_{j\ \mathrm{odd}}\beta_{j}=1 , and such that \rho=\sum_{j\ \mathrm{even}}\alpha_{j}z_{i_{j}}=\sum_{j\ \mathrm{odd}}\beta_{j}z_{i_{j}}. Writing x_{i}=(z_{i},h_{i}) , define the two lifted heights over \rho by H_{\mathrm{even}}=\sum_{j\ \mathrm{even}}\alpha_{j}h_{i_{j}},\qquad H_{\mathrm{odd}}=\sum_{j\ \mathrm{odd}}\beta_{j}h_{i_{j}}.