مسألة نهاية سعيدة

في الرياضيات، مسألة النهاية السعيدة، سميت بهذا الاسم من قبل بول إيردوس لأنها أدت إلى زواج جورج سيكيرس من إيستير كلاين، تنص على ما يلي:

مسألة النهاية السعيدة، كل مجموعة من خمس نقاط في موضع عام تضم أربع نقاط تشكل مضلع محدب.

أي مجموعة من خمس نقاط في المستوي في مواضع عامة تحوي على مجموعة جزئية من أربع نقاط تشكل رؤوس مضلع محدب.

كانت هذه واحدة من النتائج الأصلية التي أدت إلى تطوير نظرية رمزي.

بالإمكان إثبات مبرهنة النهاية السعيدة عن طريق تحليل حالة بسيطة: إذا كان أربع نقاط أو أكثر رؤوس لانغلاق محدب، يمكن اختيار أية أربع نقاط منهم. أما من ناحية أخرى لمجموعة النقط شكل مثلث مع نقتطين بداخله، يمكن اختيار النقتطين الداخليتين وواحد من جوانب المثلث. راجع Peterson (2000) للشرح المصور للاثبات، و Morris & Soltan (2000) للمزيد من الدراسة المفصلة للمسألة التي نقدمها هنا.

مضلعات أكبر
مجموعة من ثمانية نقط في مواضع عامة بدون مثمن محدب.

برهن أيردوش & سكريش (1935) التعميم التالي:

لأي عدد صحيح موجب N، أي مجموعة نقاط محدودة كبيرة بما فيه الكفاية في المستوي في مواضع عامة لها مجموعة جزئية من N نقط التي تشكل مضلع محدب.

يظهر البرهان في نفس المقال الذي يبرهن نظرية إيردوس-سيكيرس على مجموعات جزئية رتيبة في تسلسل أعداد.

نرمز بـ (f(N لأدنى قيمة لـ M بحيث لمجموعة من M نقط في مواضع عامة يجب أن تحتوي على محدب بـ N رؤوس، معروف أن:

على أساس القيم (f(N المعروفة لكل N = 3, 4 و 5، حزر إيدرش وسكريش في مقالهما الأصلي أن

برهنوا لاحقا، عن طريق بناء أمثلة واضحة، أن:

[4]

ولكن الحد الأعلى الأفضل المعروف لـ N ≥ 7 هو:

[5]

مراجع
  1. This was the original problem, proved by Esther Klein.
  2. According to Erdős & Szekeres (1935), this was first proved by E. Makai; the first published proof appeared in Kalbfleisch, Kalbfleisch & Stanton (1970).
  3. This has been proved by Szekeres & Peters (2006). 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.
  4. Erdős & Szekeres (1961)
  5. Tóth & Valtr (2005). See معامل ثنائي and رمز O الكبير for notation used here and عدد كاتالانs or تقريب ستيرلينغ for the asymptotic expansion.
    • Chung, F.R.K.; Graham, R.L. (1998), "Forced convex n-gons in the plane", Discrete and Computational Geometry, 19 (3): 367–371, doi:10.1007/PL00009353 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Erdős, P.; Szekeres, G. (1935), "A combinatorial problem in geometry", Compositio Math, 2: 463–470, مؤرشف من الأصل في 19 فبراير 2019 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Erdős, P.; Szekeres, G. (1961), "On some extremum problems in elementary geometry", Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 3–4: 53–62 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link). Reprinted in: Erdős, P. (1973), Spencer, J. (المحرر), The Art of Counting: Selected Writings, Cambridge, MA: MIT Press, صفحات 680–689 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Gerken, Tobias (2008), "Empty convex hexagons in planar point sets", Discrete and Computational Geometry, 39 (1–3): 239–272, doi:10.1007/s00454-007-9018-x الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor; Ziegler, Günter M. (المحررون), Convex Polytopes, 221 (الطبعة 2nd), سبرنجر, ISBN 0-387-00424-6 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Harborth, Heiko (1978), "Konvexe Fünfecke in ebenen Punktmengen", Elem. Math., 33 (5): 116–118 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Horton, J. D. (1983), "Sets with no empty convex 7-gons", Canadian Mathematical Bulletin, 26 (4): 482–484, doi:10.4153/CMB-1983-077-8 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Kalbfleisch, J.D.; Kalbfleisch, J.G.; Stanton, R.G. (1970), "A combinatorial problem on convex regions", Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, 1, Baton Rouge, La.: Louisiana State Univ., صفحات 180–188 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Kleitman, D.J.; Pachter, L. (1998), "Finding convex sets among points in the plane", Discrete and Computational Geometry, 19 (3): 405–410, doi:10.1007/PL00009358 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Morris, W.; Soltan, V. (2000), "The Erdős-Szekeres problem on points in convex position—A survey", Bulletin of the American Mathematical Society, 37 (04): 437–458, doi:10.1090/S0273-0979-00-00877-6, مؤرشف من الأصل في 08 ديسمبر 2008 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Nicolás, Carlos M. (2007), "The empty hexagon theorem", Discrete and Computational Geometry, 38 (2): 389–397, doi:10.1007/s00454-007-1343-6 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Overmars, M. (2003), "Finding sets of points without empty convex 6-gons", Discrete and Computational Geometry, 29 (1): 153–158, doi:10.1007/s00454-002-2829-x الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Peterson, Ivars (2000), "Planes of Budapest", MAA Online, مؤرشف من الأصل في 21 يناير 2001 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Scheinerman, Edward R.; Wilf, Herbert S. (1994), "The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability", الرياضيات الأمريكية الشهرية, Mathematical Association of America, 101 (10): 939–943, doi:10.2307/2975158, JSTOR 2975158 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Szekeres, G.; Peters, L. (2006), "Computer solution to the 17-point Erdős-Szekeres problem", ANZIAM Journal, 48 (02): 151–164, doi:10.1017/S144618110000300X, مؤرشف من الأصل في 13 ديسمبر 2019 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Tóth, G.; Valtr, P. (1998), "Note on the Erdős-Szekeres theorem", Discrete and Computational Geometry, 19 (3): 457–459, doi:10.1007/PL00009363 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Tóth, G.; Valtr, P. (2005), "The Erdős-Szekeres theorem: upper bounds and related results", Combinatorial and computational geometry, Mathematical Sciences Research Institute Publications, no. 52, صفحات 557–568 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Valtr, P. (2006), On the empty hexagons, مؤرشف من الأصل في 03 مارس 2016 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • بوابة رياضيات
    • بوابة هندسة رياضية
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.