Tehtävä, jolla on onnellinen loppu

Onnellisen lopun ongelmana on väite, että missä tahansa viiden pisteen joukossa tasossa yleisasemassa [1] on neljän pisteen osajoukko, jotka ovat kuperan nelikulmion kärkipisteitä .

Historia

Tätä kombinatorisen geometrian tulosta Pal Erdős kutsuu "onnellisen lopun ongelmaksi", koska ongelman ratkaisu päättyi György Sekeresin ja Esther Kleinin ( Hung. Eszter Klein ) häihin. Tunnetaan myös nimellä Erdős-Szekeres kupera monikulmiolause .

Tuloksen yleistäminen mielivaltaiseen määrään pisteitä kiinnostaa 1900- ja 2000-luvun matemaatikoita.

Todiste

Jos vähintään neljä pistettä muodostaa kuperan rungon , niin mikä tahansa neljän rungon pisteen joukko voidaan valita kuperaksi nelikulmioksi. Muuten siinä on kolmio ja kaksi pistettä sen sisällä. Kahden sisäpisteen kautta kulkeva suora ei leikkaa yhtäkään kolmion sivua pisteiden yleisen sijainnin vuoksi. Tämän sivun kärjet ja kaksi sisäpistettä muodostavat kuperan nelikulmion.

Monikulmiot, joissa on mielivaltainen määrä pisteitä

Erdős ja Szekeres yleistivät tämän tuloksen mielivaltaiseen määrään pisteitä, Ramseyn teorian alkuperäinen kehitys . He esittivät myös "Erdős-Szekeres-oletuksen" - tarkan kaavan kuperan monikulmion huippupisteiden enimmäismäärälle, jonka on oltava tietyn määrän pisteitä yleisessä sijainnissa.

Teoksessa ( Erdős & Szekeres 1935 ) todistettiin seuraava yleistys: jokaiselle luonnolliselle , jokaisella riittävän suurella pistejoukolla yleisessä sijainnissa tasossa on osajoukko pisteitä, jotka ovat kuperan monikulmion kärkipisteitä. Tämä todistus ilmestyi samassa artikkelissa, jossa todistetaan Erdős-Szekeres-lause monotonisista osasarjoista numeerisissa sekvensseissä. $N$ $N$

Aseta koko polygonipisteiden lukumäärän funktiona

Olkoon se minimi , jolle mikä tahansa yleisen sijainnin pistejoukko sisältää konveksin -gonin. On tiedossa, että: $f(N)$ $M$ $M$ $N$

$f(3)=3$ , ilmeisesti.
$f(4) = 5$ , todisti Esther Sekeres.
$f(5) = 9$ ( Erdős & Szekeres 1935 ) mukaan E. Makai oli ensimmäinen, joka todisti tämän; ensimmäinen julkaistu todiste ilmestyi vuonna ( Kalbfleisch, Kalbfleisch & Stanton 1970 ). Kahdeksan pisteen joukko, joka ei sisällä kuperaa viisikulmiota kuvassa, osoittaa, että ; on vaikeampaa todistaa, että mikä tahansa yhdeksän pisteen joukko yleisessä sijainnissa sisältää kuperan viisikulmion. $f(5)>8$
$f(6) = 17$ , tämä on todistettu vuonna ( Szekeres & Peters 2006 ). Paperi toteuttaa lyhennetyn tietokoneluettelon mahdollisista kokoonpanoista 17 pisteestä.
Arvot ovat tuntemattomia . $f(N)$ $N>6$

Erdős-Szekeres-oletus pisteiden vähimmäismäärästä

Erdős ja Székeres ehdottivat tunnettujen arvojen perusteella , että: $f(N)$ $N = 3,4,5$

f(N)=1+2^{{N-2}}

kaikille .

N

Tätä olettamusta ei ole todistettu, mutta ylä- ja alarajat tunnetaan.

Arviot kasvunopeudesta f(N)

Konstruktiivisen konstruktion avulla olettamuksen tekijät pystyivät myöhemmin todistamaan alemman arvion, joka osuu yhteen hypoteettisen tasa-arvon kanssa:

f(N)\geq 1+2^{{N-2}}

, ( Erdős & Szekeres 1961 )

Tunnetuin yläraja ei kuitenkaan ole lähellä: $N\geq 7$

f(N)\leq {2N-5 \choose N-2}+1=O\left({\frac {4^{N}}{{\sqrt N}}}\oikea)

, ( Toth & Valtr 2005 )

(käytetty binomiaalikertoimia ).

Tyhjät polygonit

Mielenkiintoinen on myös kysymys siitä, sisältääkö riittävän suuri joukko yleisasemassa olevia pisteitä tyhjän kuperan nelikulmion, viisikulmion ja niin edelleen. Eli monikulmio, joka ei sisällä sisäpisteitä.

Jos nelikulmion sisällä on piste, joka on olemassa onnellisen lopun lauseen mukaan, niin yhdistämällä tämä piste diagonaalin kahteen kärkeen, saadaan kaksi nelikulmiota, joista toinen on kupera ja tyhjä. Siten viisi pistettä yleisasemassa sisältävät tyhjän kuperan nelikulmion, kuten kuvasta näkyy. Mikä tahansa kymmenen pistettä yleisasemassa sisältää tyhjän kuperan viisikulmion ( Harborth 1978 ). Yleisessä asemassa on kuitenkin mielivaltaisen suuria pisteitä, jotka eivät sisällä tyhjää kuperaa seitsekulmiota ( Horton 1983 ) .

Siten tyhjien polygonien ongelma ei ole Ramseyn teorian ongelma ja se on periaatteessa ratkaistu.

Kysymys tyhjän kuusikulmion olemassaolosta jäi avoimeksi pitkään. Mutta teoksissa ( Nicolás 2007 ) ja ( Gerken 2008 ) todistettiin, että jokainen riittävän suuri pistejoukko yleisasemassa sisältää tyhjän kuusikulmion. Nykyään tiedetään, että tämän joukon tulisi sisältää enintään f (9) (oletettavasti 129) ja vähintään 30 pistettä ( Overmars 2003 ).

Muistiinpanot

↑ Tässä yhteydessä yleinen sijainti tarkoittaa, että kolmea pistettä ei ole samalla suoralla.

Kirjallisuus

Chung, FRK & Graham, R. L. (1998), Forced convex n-gons in the plane , Discrete and Computational Geometry , osa 19 (3): 367-371 , DOI 10.1007/PL00009353 .
Erdős, P. & Szekeres, G. (1935), A kombinatorinen ongelma geometriassa , Compositio Math vol. 2: 463-470 , < http://www.numdam.org/item?id=CM_1935__2__463_0 > .
Erdős, P. & Szekeres, G. (1961), Joistain alkeisgeometrian ääripäätehtävistä, Ann. Univ. sci. Budapest. Eötvös Sect. Matematiikka. T. 3–4: 53–62 . Uusintapainos: Erdős, P. (1973), Spencer, J., toim., The Art of Counting: Selected Writings , Cambridge, MA: MIT Press, s. 680–689 .
Gerken, Tobias (2008), Tyhjät kuperat kuusikulmiot tasopistejoukoissa , Discrete and Computational Geometry , osa 39 (1–3): 239–272 , DOI 10.1007/s00454-007-9018-x .
Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor & Ziegler, Günter M. , toim., Convex Polytopes , voi. 221 (2. painos), Graduate Texts in Mathematics, Springer-Verlag , ISBN 0-387-00424-6 .
Harborth, Heiko (1978), Konvexe Fünfecke in ebenen Punktmengen, Elem. Matematiikka. T. 33(5): 116–118 .
Horton, JD (1983), Sarjat, joissa ei ole tyhjiä kuperaa 7-kulmaista , Canadian Mathematical Bulletin T. 26 (4): 482–484 , DOI 10.4153/CMB-1983-077-8 .
Kalbfleisch, JD; Kalbfleisch, JG & Stanton, RG (1970), A kombinatorinen ongelma konveksilla alueilla, Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing , voi. 1, Congressus Numerantium, Baton Rouge, La.: Louisiana State Univ., s. 180-188 .
Kleitman, DJ & Pachter, L. (1998), Konveksien joukkojen löytäminen tasossa olevien pisteiden joukosta , Discrete and Computational Geometry, osa 19 (3): 405–410 , DOI 10.1007/PL00009358 .
Morris, W. & Soltan, V. (2000), Erdős-Szekeres-ongelma kuperassa asemassa olevissa pisteissä – tutkimus , Bulletin of the American Mathematical Society , osa 37 (04): 437–458, doi : 10.1090/S0273- 0979-00-00877-6 , < http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html > .
Nicolás, Carlos M. (2007), Tyhjä kuusikulmiolause , Discrete and Computational Geometry , osa 38 (2): 389–397 , DOI 10.1007/s00454-007-1343-6 .
Overmars, M. (2003), Pistejoukkojen etsiminen ilman tyhjiä kuperaa 6-kulmaista , Diskreetti ja laskennallinen geometria , osa 29 (1): 153–158, DOI 10.1007/s00454-002-2829-x .
Peterson, Ivars (2000), Planes of Budapest , MAA Online , < http://www.maa.org/mathland/mathtrek_10_3_00.html > .
Scheinerman, Edward R. & Wilf, Herbert S. (1994), Täydellisen kaavion suoraviivainen risteysluku ja Sylvesterin geometrisen todennäköisyyden "neljän pisteen ongelma" , American Mathematical Monthly (Mathematical Association of America). - T. 101 (10): 939–943 , DOI 10.2307/2975158 .
Szekeres, G. & Peters, L. (2006), Tietokoneratkaisu 17-pisteen Erdős-Szekeres-ongelmaan , ANZIAM Journal, osa 48 (02): 151–164, doi : 10.1017/S144618110000300X , < http://www. .austms.org.au/Publ/ANZIAM/V48P2/2409.html > Arkistoitu 13. joulukuuta 2019 Wayback Machinessa .
Tóth, G. & Valtr, P. (1998), Huomautus Erdős-Szekeres-lauseesta , Discrete and Computational Geometry, osa 19 (3): 457–459 , DOI 10.1007/PL00009363 .
Tóth, G. & Valtr, P. (2005), Erdős-Szekeres-lause: ylärajat ja niihin liittyvät tulokset, Kombinatorinen ja laskennallinen geometria , Matemaattisten tieteiden tutkimuslaitoksen julkaisut, no. 52, s. 557-568 .
Valtr, P. (2006), On the hexagons , < http://kam.mff.cuni.cz/~valtr/h.ps > .

Linkit

Happy ending problem Arkistoitu 25. syyskuuta 2006 Wayback Machinessa ja Ramsey-teoreettinen todistus Erdős-Szekeres- lauseesta PlanetMathissa
Weisstein, Eric W. Happy End Problem (englanniksi) Wolfram MathWorld -verkkosivustolla .