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 Erdős Pál 1935-ben mondta ki a sejtést az American Mathematical Monthly-ban, Paul Erdős. Problem number 3763. American Mathematical Monthly, 42:627, 193 Szőkefalvi-Nagy Béla 1939-ben bizonyította.Bela Nagy. Solution of problem 3763. American Mathematical Monthly, 46:176–177, 1939. A probléma kacifántos utat járt be, újra és újra felfedezték.
1957-ben Jurij Grigorjevics ResetnyakYu. 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. és A. Ya. Yusupov, a buharai geometria tanszék vezetője A. Ya. Yusupov. A property of simply-connected nonconvex polygons. Uchen. Zapiski Buharsk. Gos. Pedagog., pages 101–103, 1957. In Russian 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,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. amire két évvel később megoldást is adtak. 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. 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.Branko Grünbaum, How to convexify a polygon, Geombinatorics, 5 (1995), 24–30.
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.T. Kaluza. Problem 2: Konvexieren von Polygonen. Math. Semesterber., 28:153–154, 1981.
1993-ban Bernd Wegner erősen technikai cikkében bizonyítja Kaluza sejtését.Bernd Wegner. Partial inflation of closed polygons in the plane. Contributions to Algebra and Geometry, 34(1):77–85, 1993.
1999-ben Therese Biedl és tsai ismét újrafelfedezik a problémát, Wegnerrel nagyjából megegyező eredményre jutva. 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
1999-ben Godfried Toussaint az addigi bizonyítások elemi, egyszerű és rövid szintézisét próbálja adni.Godfried Toussaint, The Erdős–Nagy Theorem and its Ramifications, Proc. 11th Canadian Conference on Computational Geometry (1999), 219–236. Bizonyítása hibát tartalmaz, amit 2006-ban javítanak.D. Demaine, Erik & Gassend, Blaise & O'Rourke, Joseph & T. Toussaint, Godfried. (2006). Polygons Flip Finitely: Flaws and a Fix.
Változatok és általánosítások 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 politópokra. 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
Irodalom 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 , 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.
További információk The convexification of a simple polygon
Kategória:Diszkrét geometriai tételek Kategória:Erdős Pál