Английская Википедия:Happy ending problem

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:For Шаблон:Redirect

Файл:Happy-End-problem.svg
The happy ending problem: every set of five points in general position contains the vertices of a convex quadrilateral

In mathematics, the "happy ending problem" (so named by Paul Erdős because it led to the marriage of George Szekeres and Esther Klein[1]) is the following statement:

Шаблон:Math theorem

This was one of the original results that led to the development of Ramsey theory.

The happy ending theorem can be proven by a simple case analysis: if four or more points are vertices of the convex hull, any four such points can be chosen. If on the other hand, the convex hull has the form of a triangle with two points inside it, the two inner points and one of the triangle sides can be chosen. See Шаблон:Harvtxt for an illustrated explanation of this proof, and Шаблон:Harvtxt for a more detailed survey of the problem.

The Erdős–Szekeres conjecture states precisely a more general relationship between the number of points in a general-position point set and its largest subset forming a convex polygon, namely that the smallest number of points for which any general position arrangement contains a convex subset of <math>n</math> points is <math>2^{n-2} + 1</math>. It remains unproven, but less precise bounds are known.

Larger polygons

Файл:8-points-no-pentagon.svg
A set of eight points in general position with no convex pentagon

Шаблон:Harvtxt proved the following generalisation:

Шаблон:Math theorem

The proof appeared in the same paper that proves the Erdős–Szekeres theorem on monotonic subsequences in sequences of numbers.

Let Шаблон:Math denote the minimum Шаблон:Mvar for which any set of Шаблон:Mvar points in general position must contain a convex N-gon. It is known that


On the basis of the known values of Шаблон:Math for N = 3, 4 and 5, Erdős and Szekeres conjectured in their original paper that

A set of sixteen points in general position with no convex hexagon
A set of sixteen points in general position with no convex hexagon

<math display="block">f(N) = 1 + 2^{N-2} \quad \text{for all } N \geq 3.</math> They proved later, by constructing explicit examples, that[5] <math display="block">f(N) \geq 1 + 2^{N-2}</math>. In 2016 Andrew Suk[6] showed that for Шаблон:Math <math display="block">f(N) \leq 2^{N + o(N)}.</math>

Suk actually proves, for N sufficiently large, <math display="block">f(N) \leq 2^{N + 6N^{2/3}logN}.</math>

A 2020 preprint[7] by Andreas F. Holmsen, Hossein Nassajian Mojarrad, János Pach and Gábor Tardos claims an improvement on Suk:

<math display="block">f(N) \leq 2^{N + O(\sqrt{NlogN})}.</math>

Empty convex polygons

There is also the question of whether any sufficiently large set of points in general position has an "empty" convex quadrilateral, pentagon, etc., that is, one that contains no other input point. The original solution to the happy ending problem can be adapted to show that any five points in general position have an empty convex quadrilateral, as shown in the illustration, and any ten points in general position have an empty convex pentagon.[8] However, there exist arbitrarily large sets of points in general position that contain no empty convex heptagon.[9]

For a long time the question of the existence of empty hexagons remained open, but Шаблон:Harvtxt and Шаблон:Harvtxt proved that every sufficiently large point set in general position contains a convex empty hexagon. More specifically, Gerken showed that the number of points needed is no more than f(9) for the same function f defined above, while Nicolás showed that the number of points needed is no more than f(25). Шаблон:Harvtxt supplies a simplification of Gerken's proof that however requires more points, f(15) instead of f(9). At least 30 points are needed; there exists a set of 29 points in general position with no empty convex hexagon.[10]

Related problems

The problem of finding sets of n points minimizing the number of convex quadrilaterals is equivalent to minimizing the crossing number in a straight-line drawing of a complete graph. The number of quadrilaterals must be proportional to the fourth power of n, but the precise constant is not known.[11]

It is straightforward to show that, in higher-dimensional Euclidean spaces, sufficiently large sets of points will have a subset of k points that forms the vertices of a convex polytope, for any k greater than the dimension: this follows immediately from existence of convex Шаблон:Nowrap in sufficiently large planar point sets, by projecting the higher-dimensional point set into an arbitrary two-dimensional subspace. However, the number of points necessary to find k points in convex position may be smaller in higher dimensions than it is in the plane, and it is possible to find subsets that are more highly constrained. In particular, in d dimensions, every d + 3 points in general position have a subset of d + 2 points that form the vertices of a cyclic polytope.[12] More generally, for every d and k > d there exists a number m(d, k) such that every set of m(d, k) points in general position has a subset of k points that form the vertices of a neighborly polytope.[13]

Notes

Шаблон:Reflist

References

Шаблон:Refbegin

Шаблон:Refend

External links

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ A world of teaching and numbers - times two, Michael Cowling, The Sydney Morning Herald, 2005-11-07, cited 2014-09-04
  2. ↑ This was the original problem, proved by Esther Klein.
  3. ↑ According to Шаблон:Harvtxt, this was first proved by E. Makai; the first published proof appeared in Шаблон:Harvtxt.
  4. ↑ This has been proved by Шаблон:Harvtxt. They carried out a computer search which eliminated all possible configurations of 17 points without convex hexagons while examining only a tiny fraction of all configurations.
  5. ↑ Шаблон:Harvtxt
  6. ↑ Шаблон:Harvtxt. See binomial coefficient and big O notation for notation used here and Catalan numbers or Stirling's approximation for the asymptotic expansion.
  7. ↑ Шаблон:Cite arXiv
  8. ↑ Шаблон:Harvtxt.
  9. ↑ Шаблон:Harvtxt
  10. ↑ Шаблон:Harvtxt.
  11. ↑ Шаблон:Harvtxt
  12. ↑ Шаблон:Harvtxt, Ex. 6.5.6, p.120. Grünbaum attributes this result to a private communication of Micha A. Perles.
  13. ↑ Шаблон:Harvtxt, Ex. 7.3.6, p. 126. This result follows by applying a Ramsey-theoretic argument similar to Szekeres's original proof together with Perles's result on the case k = d + 2.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Happy_ending_problem&oldid=15136332