Order of magnitude of the Erdős–Szekeres function $N(k,d,n)$ for $k$-flats in $\mathbb{R}^d$

Bárány, Kalai, and Pór (2023) extended the Erdős–Szekeres theorem from points to $k$-flats (affine $k$-dimensional subspaces) of $\mathbb{R}^d$: for $n\ge d-k+1$ there is a smallest integer $N(k,d,n)$ such that every family of $N(k,d,n)$ $k$-flats in general position contains $n$ members in convex position, meaning that some $d$-dimensional polytope meets each of them in a $k$-dimensional face. The asymptotic behavior of $N(k,d,n)$ is wide open. For intermediate dimensions $0<k<d-1$ the only upper bound is $N(k,d,n)\le N(0,d-k,n)\le 2^{n+o(n)}$, inherited from the point case by a reduction that discards all geometry of the flats, and no nontrivial lower bound is known; the authors explicitly ask what the value of $N(d/2,d,n)$ could be. For hyperplanes ($k=d-1$, $d\ge 3$) the upper bound $\binom{2n-4}{n-2}$, of order $4^n$ up to polynomial factors, is inherited from the planar line case and its tightness is unknown. The problem is to determine the order of magnitude of $N(k,d,n)$ in these regimes. The problem remains open.

Background

The classical Erdős–Szekeres theorem (1935) states that for every $n\ge 3$ there is an integer $N(n)$ such that any $N(n)$ points in general position in the plane (no three collinear) contain $n$ points in convex position, that is, the vertex set of a convex $n$-gon. Erdős and Szekeres proved $N(n)\le\binom{2n-4}{n-2}+1$ and, in 1960/61, constructed $2^{n-2}$ points with no $n$ in convex position, giving $2^{n-2}+1\le N(n)$; the conjectured equality $N(n)=2^{n-2}+1$ is the famous 'happy ending' conjecture. Suk (2017) nearly closed the gap by proving $N(n)\le 2^{n+o(n)}$.

Bárány, Kalai, and Pór (2023) extended the theorem to flats. A $k$-flat in $\mathbb{R}^d$ is a $k$-dimensional affine subspace. A family of $n$ $k$-flats $\{U_1,\dots,U_n\}$ is in convex position if there is a $d$-dimensional polytope $P\subset\mathbb{R}^d$ such that $U_i\cap P$ is a $k$-dimensional face of $P$ for every $i$; equivalently (their Lemma 2.1), there is a strictly convex body meeting each $U_i$ in exactly one point. For $k=0$ this recovers the usual notion for points. General position for $0\le k\le d-2$ with $d\ge 3$ means that some $(d-k)$-flat meets every $U_i$ in a single point and these points are in general position (no three collinear) and span that flat; for hyperplanes ($k=d-1$) it means every $d$ of them intersect in a single point and these $\binom{n}{d}$ points are distinct. Their Theorem 1.1 shows that $N(k,d,n)$ is finite for all $0\le k\le d-1$ and $n\ge d-k+1$, and their Theorems 1.2 and 2.2 show that convex position is not automatic: for all large enough $n$ there are general-position families of $n$ $k$-flats that are not in convex position (via a construction using an $\varepsilon$-net in the Grassmannian $\mathrm{Gr}(k,d)$, the compact space of $k$-dimensional linear subspaces of $\mathbb{R}^d$ equipped with the angular metric).

The quantitative bounds, however, are far apart, and all of them are inherited from other problems. For points, $N(0,d,n)\le N(n)\le 2^{n+o(n)}$ by projection to a generic plane; moreover Zoltán Füredi conjectured (under a slightly stronger general-position assumption, as reported in Károlyi–Valtr 2003) that $N(0,d,n)=O(2^{n^{1/(d-1)}})$ for $d\ge 3$, matching a lower bound of the same order due to Károlyi and Valtr — so for points, higher dimension is expected to reduce $N$ dramatically. For lines in the plane ($d=2$, $k=1$), Bárány, Roldán-Pensado, and Tóth (2015) proved almost matching bounds $2\binom{n-4}{\lceil n/2\rceil-1}^{2}\le N(1,2,n)\le\binom{2n-4}{n-2}$ (the lower bound is of order $4^n/n$ and the upper one of order $4^n/\sqrt{n}$), that is, $N(1,2,n)$ is of order $4^n$ up to polynomial factors. For intermediate flats ($0<k<d-1$), the reduction $N(k,d,n)\le N(0,d-k,n)\le 2^{n+o(n)}$ discards all information about $k$ and $d$. For hyperplanes ($k=d-1$), $N(d-1,d,n)\le N(1,2,n)\le\binom{2n-4}{n-2}$ by intersecting the hyperplanes with a generic 2-plane; the authors remark that it is not clear how good this bound is, and their only explicit non-convex example is a family of $2^d+d$ hyperplanes (obtained by perturbing the facet planes of a cross-polytope, the $d$-dimensional analogue of the octahedron), which yields nothing asymptotic. They close the reduction discussion with the words: 'We wonder for instance what the value of $N(d/2,d,n)$ could be.'

The same paper explicitly raises one further question that is related but a genuinely distinct problem and lies outside what is asked here: whether the Helly number of convex position for $k$-flats in $\mathbb{R}^d$ is finite (for lines in the plane it equals 5, by the result of Bárány–Bunting–Larman–Pach 1995 that if every 5 lines of a suitable general-position family are in convex position then all of them are). Its cone theorem (Theorem 2.2) proves only that some $\varepsilon=\varepsilon(k,d)>0$ exists for which an $\varepsilon$-net of $\mathrm{Gr}(k,d)$ admits no polyhedral cone touching each of its members in a $k$-dimensional face; determining the maximal such $\varepsilon$ is a natural quantitative refinement, likewise outside what is asked here.

Problem Statement

Determine the asymptotic behavior of $N(k,d,n)$ — the smallest integer such that every family of that many $k$-flats in general position in $\mathbb{R}^d$ contains $n$ members in convex position — in the two regimes left open by Bárány–Kalai–Pór (2023): intermediate dimensions $0<k<d-1$ (so $d\ge 3$) and hyperplanes $k=d-1$ with $d\ge 3$, in each case for $n\ge d-k+1$, with general position and convex position defined exactly as in that paper. (The planar line case $d=2$, $k=1$ is excluded because it is already settled up to polynomial factors, as recalled below.) Concretely, with the common objective of pinning down the exponential order of $N(k,d,n)$ as a function of $n$ for each fixed pair $(k,d)$:

(1) Intermediate dimensions $0<k<d-1$: the only known upper bound is $N(k,d,n)\le N(0,d-k,n)\le 2^{n+o(n)}$, obtained by reduction to the point case, and no nontrivial lower bound is known. Is this bound essentially tight, or does the geometry of the flats yield a substantially smaller bound — for instance, does an analogue of the dimension-driven improvement conjectured for points (Füredi's $O(2^{n^{1/(d-1)}})$) hold for flats? In particular, the value, or at least the exponential order, of $N(d/2,d,n)$ — the case the authors explicitly single out — is a distinguished instance within this regime rather than a separate requirement.

(2) Hyperplanes $k=d-1$, $d\ge 3$: is the planar-lines upper bound $N(d-1,d,n)\le\binom{2n-4}{n-2}$, of order $4^n$ up to polynomial factors, tight in ambient dimension $d$, or does $N(d-1,d,n)$ grow substantially more slowly?

The objective is to establish upper and lower bounds for $N(k,d,n)$ that agree up to subexponential factors in the exponent (or up to polynomial factors where $4^n$-type bounds are at stake) in the stated regimes; both directions — improved upper bounds and growing lower-bound constructions — are part of the same quantitative objective.

References

1. Imre Bárány, Gil Kalai, Attila Pór, Erdős–Szekeres Theorem for k-Flats, Discrete & Computational Geometry 69(4):1232–1240, 2023. DOI: 10.1007/s00454-022-00450-4, https://doi.org/10.1007/s00454-022-00450-4 (preprint arXiv:2103.13185, https://arxiv.org/abs/2103.13185)
2. Imre Bárány, Edgardo Roldán-Pensado, Géza Tóth, Erdős–Szekeres Theorem for Lines, Discrete & Computational Geometry 54:669–685, 2015. DOI: 10.1007/s00454-015-9705-y, https://doi.org/10.1007/s00454-015-9705-y (preprint arXiv:1307.5666, https://arxiv.org/abs/1307.5666)
3. Andrew Suk, On the Erdős–Szekeres convex polygon problem, Journal of the American Mathematical Society 30:1047–1053, 2017. DOI: 10.1090/jams/869, https://doi.org/10.1090/jams/869
4. Paul Erdős, George Szekeres, A combinatorial problem in geometry, Compositio Mathematica 2:463–470, 1935. zbMATH Zbl 0012.27010 (zbMATH record 3019031), https://zbmath.org/?q=an%3A0012.27010; EuDML, https://eudml.org/doc/88611
5. Paul Erdős, George Szekeres, On some extremum problems in elementary geometry, Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös, Sectio Mathematica 3–4:53–62, 1960/61. zbMATH Zbl 0103.15502 (zbMATH record 3168302), https://zbmath.org/?q=an%3A3168302
6. Gyula Károlyi, Pavel Valtr, Point configurations in d-space without large subsets in convex position, Discrete & Computational Geometry 30:277–286, 2003. DOI: 10.1007/s00454-003-0009-4, https://doi.org/10.1007/s00454-003-0009-4
7. I. Bárány, H. Bunting, D. G. Larman, J. Pach, Rich cells in an arrangement of hyperplanes, Linear Algebra and its Applications 226–228:567–575, 1995. DOI: 10.1016/0024-3795(95)00244-L, https://doi.org/10.1016/0024-3795(95)00244-L
8. Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński, Erdős–Szekeres type theorems for ordered uniform matchings, Journal of Combinatorial Theory, Series B 170:225–259, 2025. DOI: 10.1016/j.jctb.2024.09.004, https://doi.org/10.1016/j.jctb.2024.09.004 (preprint arXiv:2301.02936, https://arxiv.org/abs/2301.02936)
9. Attila Jung, Dömötör Pálvölgyi, k-dimensional transversals for fat convex sets, arXiv:2311.15646, 2023, https://arxiv.org/abs/2311.15646
10. Attila Jung, Dömötör Pálvölgyi, A note on infinite versions of $(p,q)$-theorems, arXiv:2412.04066, 2024, https://arxiv.org/abs/2412.04066