Erdős–Szőkefalvi-Nagy-tétel
Az Erdős–Nagy-tétel vagy Erdős–Szőkefalvi-Nagy-tétel a matematika, azon belül a diszkrét geometria eredménye. A tétel kimondja, hogy bármely nem konvex egyszerű sokszög átfordítások („flips”) véges sorozatával konvex sokszöggé alakítható. Egy „átfordítás” alatt az értendő, hogy a sokszög konvex burkát véve a sokszög valamely zsebét a határoló élre tengelyesen tükrözzük. A tétel Erdős Pál és Szőkefalvi-Nagy Béla magyar matematikusokról kapta a nevét.
Az Erdős-féle eredeti felvetés szerint egyszerre történt volna meg az összes átfordítás – ilyenkor elképzelhetőek olyan lépések, melynek során a sokszög önmagát metszővé válik. Szőkefalvi-Nagy ezért egyszerre egy átfordítást végzett.
Történet
[szerkesztés]Erdős Pál 1935-ben mondta ki a sejtést az American Mathematical Monthly-ban,[1] Szőkefalvi-Nagy Béla 1939-ben bizonyította.[2] A probléma kacifántos utat járt be, újra és újra felfedezték.
1957-ben Jurij Grigorjevics Resetnyak[3] és A. Ya. Yusupov, a buharai geometria tanszék vezetője [4] Erdősék munkájától függetlenül újra felfedezték és bizonyították a sejtést.
1959-ben Nicholas D. Kazarinoff és R. H. Bing újra felfedezte a problémát,[5] amire két évvel később megoldást is adtak.[6] Sejtésük szerint minden egyszerű sokszög legfeljebb 2n átfordítással konvexszé tehető.
1973-ban a Washingtoni Egyetemen Grünbaum két diákja, R. R. Joss és R. W. Shannon ellenpéldát találtak Kazarinoff és Bing sejtésére.[7]
1981-ben Theodor Kaluza ismét felfedezi a problémát, egyben felteszi a kérdést, hogy vajon a szükséges átfordítások számára felállítható-e korlát a sokszög csúcsai számának függvényében.[8]
1993-ban Bernd Wegner erősen technikai cikkében bizonyítja Kaluza sejtését.[9]
1999-ben Therese Biedl és tsai ismét újrafelfedezik a problémát, Wegnerrel nagyjából megegyező eredményre jutva.[10]
1999-ben Godfried Toussaint az addigi bizonyítások elemi, egyszerű és rövid szintézisét próbálja adni.[11] Bizonyítása hibát tartalmaz, amit 2006-ban javítanak.[12]
Változatok és általánosítások
[szerkesztés]- A csomóelméletben hasznos változatban az Erdős-féle átfordítások helyett száj-átfordításokat alkalmaznak (mouth-flip), ami nem a teljes zsebet, hanem csak egy csúcsot fordít át.
- A probléma általánosítható 3, illetve több dimenziós sokszögekre.
- Flip (átfordítás) helyett flipturn (át- és megfordítás, azaz az átfordítás után az él középpontja körüli 180°-os megfordítás) alkalmazása
Jegyzetek
[szerkesztés]- ↑ Paul Erdős. Problem number 3763. American Mathematical Monthly, 42:627, 193
- ↑ Bela Nagy. Solution of problem 3763. American Mathematical Monthly, 46:176–177, 1939.
- ↑ Yu. G. Reshetnyak. On a method of transforming a nonconvex polygonal line into a convex one. Uspehi Mat. Nauk, 12(3):189–191, 1957. In Russian.
- ↑ A. Ya. Yusupov. A property of simply-connected nonconvex polygons. Uchen. Zapiski Buharsk. Gos. Pedagog., pages 101–103, 1957. In Russian
- ↑ N. D. Kazarinoff and R. H. Bing. A finite number of reflections render a nonconvex plane polygon convex. Notices of the American Mathematical Society, 6:834, 1959.
- ↑ R. H. Bing and N. D. Kazarinoff. On the finiteness of the number of reflections that change a nonconvex plane polygon into a convex one. Matematicheskoe Prosveshchenie, 6:205–207, 1961. In Russian.
- ↑ Branko Grünbaum, How to convexify a polygon, Geombinatorics, 5 (1995), 24–30.
- ↑ T. Kaluza. Problem 2: Konvexieren von Polygonen. Math. Semesterber., 28:153–154, 1981.
- ↑ Bernd Wegner. Partial inflation of closed polygons in the plane. Contributions to Algebra and Geometry, 34(1):77–85, 1993.
- ↑ T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. T. Toussaint, and S. Whitesides. Locked and unlocked polygonal chains in 3d. In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, pages 866–867, 1999
- ↑ Godfried Toussaint, The Erdős–Nagy Theorem and its Ramifications, Proc. 11th Canadian Conference on Computational Geometry (1999), 219–236.
- ↑ D. Demaine, Erik & Gassend, Blaise & O'Rourke, Joseph & T. Toussaint, Godfried. (2006). Polygons Flip Finitely: Flaws and a Fix.
Irodalom
[szerkesztés]- Branko Grünbaum, How to convexify a polygon, Geombinatorics, 5 (1995), 24–30.
- Godfried Toussaint, The Erdős–Nagy Theorem and its Ramifications, Proc. 11th Canadian Conference on Computational Geometry (1999), 219–236.
- Branko Grünbaum and Joseph Zaks, Convexification of polygons by flips and by flipturns Archiválva 2013. május 30-i dátummal a Wayback Machine-ben, Discrete Math. 241 (2001), 333–342.
- E.D. Demaine, B. Gassend, J. O'Rourke, G.T. Toussaint, All polygons flip finitely right? Surveys on discrete and computational geometry, 231–255, in Contemp. Math., 453, Amer. Math. Soc., Providence, RI, 2008.