← All problems

Erdős Problem #838 — Convex subsets of planar point sets

47 years old · documented by

Let nn be a positive integer. The question is: “Let f(n)f(n) be maximal such that any nn points in R2\mathbb{R}^2, with no three on a line, determine at least f(n)f(n) different convex subsets. Estimate f(n)f(n)—in particular, does there exist a constant cc such that

lim⁡n→∞log⁡f(n)(log⁡n)2=c?\lim_{n\to\infty}\frac{\log f(n)}{(\log n)^2}=c?

” Here f(n)f(n) 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 nn: Erdős’s bounds place the minimum between quantities of the form nc1log⁡nn^{c_1\log n} and nc2log⁡nn^{c_2\log n}. 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

Progress summary

Never refreshed

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.