Erdős Problem #838 — Convex subsets of planar point sets
Let be a positive integer. The question is: “Let be maximal such that any points in , with no three on a line, determine at least different convex subsets. Estimate —in particular, does there exist a constant such that
” Here is the largest guaranteed number, with the guarantee taken over all configurations satisfying the stated no-three-collinear condition. Erdős Problem #838 Erdős, Some More Problems on Elementary Geometry
Background
Erdős posed the problem in connection with J. Hammer. The question asks for the least number of convex subsets forced by an arbitrary point configuration, rather than the number attainable in a particularly favorable arrangement. Its natural scale is much larger than a power of : Erdős’s bounds place the minimum between quantities of the form and . In a later discussion he described an asymptotic formula as difficult, while expressing the expectation that the normalized logarithm has a limit. Erdős, Some More Problems on Elementary Geometry Erdős, Some Applications of Graph Theory and Combinatorial Methods to Number Theory and Geometry Erdős, Some Old and New Problems in Combinatorial Geometry (1984)
The bounds connect the counting question to the classical theorem of Erdős and Szekeres on convex subsets: every sufficiently large point set in general position contains a convex subset whose size is at least a constant times the logarithm of the number of points. Applying that guarantee repeatedly to smaller selections gives many convex subsets, while constructions with no large convex subset constrain how many can occur. Erdős, Some More Problems on Elementary Geometry Erdős, Some Old and New Problems in Combinatorial Geometry (1984)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.