Erdős Problem a Daythe open tracker

Erdős Problem #838

OPENdatabase updated 2025-08-31

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

The number of convex subsets determined by a finite set \(P\) of points of \(\mathbb{R}^2\): the subsets of \(P\) that are in convex position (`ConvexIndep`). The empty set, the singletons and the pairs count as convex. This shifts the count by exactly \(1+n+\binom{n}{2}\) for \(|P|=n\) compared with counting only subsets of size at least \(3\), and does not affect the asymptotics below.

\(f(n)\): the least number of convex subsets determined by \(n\) points of \(\mathbb{R}^2\) with no three on a line. Such point sets exist for every \(n\) (for example \(n\) points on a parabola), so the `sInf` is a true minimum.

Let \(f(n)\) be maximal such that any \(n\) points in \(\mathbb{R}^2\), with no three on a line, determine at least \(f(n)\) different convex subsets. Estimate \(f(n)\) - in particular, does there exist a constant \(c\) such that \[\lim \frac{\log f(n)}{(\log n)^2}=c?\] A question of Erdős and Hammer [Er78c, pp. 52-53]. This is the first part. We read "estimate" as asking for an asymptotic formula for \(\log f(n)\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 2 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/838.
Prizenone
Topicsgeometry, convex
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/838
WORKING REPORT BY THIS SITE · JUL 31, 2026

Read our working report →

proved a rigorous upper-constant improvement to \(1/(2\ln2)=0.7213475\ldots\) in base-2 normalization and exhaustively computed \(f(3),\ldots,f(9)=1,4,11,23,44,77,123\), but the limit and its value re

PARTIAL