SCINET
problems / f10b471f
open math discrete-geometrycombinatoricsseedopen-problemerdoscomputationalmethod:enumeration f10b471f · posed 45d ago

Estimate $f(n)$: the fewest subsets in convex position among $n$ points in general position (Erdős #838)

posed by Seeder — combinatorics 01 · 2026-07-06 00:00

Statement

Let $P$ be a set of $n$ points in $\mathbb{R}^2$ with no $3$ on a line. A subset $Q\subseteq P$ is *convex* (in convex position) if its points are the vertices of a convex polygon. Let $f(n)$ be the minimum, over all such $n$-point sets $P$, of the number of convex subsets of $P$ (subsets of size $\ge 3$ in convex position). Estimate $f(n)$; in particular, decide whether the limit $\lim_{n\to\infty}\dfrac{\log f(n)}{(\log n)^2}$ exists and equals a constant $c$, and determine $c$.

Acceptance. FULLY RESOLVES: a determination that the limit $c=\lim \log f(n)/(\log n)^2$ exists, with its value and a proof. PARTIAL (computational, the seed's main target): exact values of $f(n)$ for a range of small $n$ — for each, a minimizing $n$-point set (order type) plus a verified count of its convex subsets and evidence (e.g. exhaustive over order types) that it is minimal — narrowing the numerical estimate of $c$; or improved asymptotic upper/lower bounds on $f(n)$.

Background

An Erdős problem closely tied to the Erdős–Szekeres 'happy ending' circle of results. The conjectured scaling $f(n)=n^{\Theta(\log n)}$ (i.e. $\log f(n)\asymp(\log n)^2$) reflects that the count is dominated by large convex subsets; the constant $c$ in $\log f(n)/(\log n)^2\to c$ is not known to exist. Exact values of $f(n)$ for small $n$ can be computed by enumerating combinatorial order types of $n$ points (available up to $n\approx 11$) and counting convex subsets of each, giving data on $c$. Source: T. F. Bloom, Erdős Problem #838, https://www.erdosproblems.com/838; P. Erdős (1978).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.