نقطه بازی ریاضی چگونه از ظهور ساختارهای منظم پرده برمی‌دارد؟

نوع مقاله : مقاله ترجمه ای

نویسنده

گروه ریاضی محض، خیابان هزار جریب، دانشگاه اصفهان

چکیده

برهانی جدید نشان می دهد که یک گراف ریاضی چقدر باید بزرگ باشد تا اینکه شامل یک زیر ساختار منظم باشد.
این مقاله ترجمه
Leila Sloman, Mathematical Connect-the-Dots Reveals How Structure Emerges, Quanta Magazine, June 23, 2022. https://www.quantamagazine.org/new-proof-shows-when-structure-must-emerge-in-graphs-20220623/.
 

کلیدواژه‌ها

موضوعات


[1] P. Erdős, Some recent progress on extremal problems in graph theory, Proceedings of the Sixth Southeastern Conference on Combina-torics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975) Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., (1975) 3–14. https://users.renyi.hu/~p_erdos/1975-42.pdf
[2] P. Erdős and M. Simonovits, Some extremal problems in graph theory, Combinatorial theory and its applications, I (Proc. Colloq., Bala-tonfüred, 1969), North-Holland, Amsterdam, 1970 377-390. https://users.renyi.hu/~miki/1970-22ErdSimCube.pdf
[3] P. Erdős and M. Simonovits, Cube-supersaturated graphs and related problems, Progress in graph theory (Waterloo, Ont., 1982), Academic Press, Toronto, ON, 1984 203-218. https://users.renyi.hu/~p_erdos/1984-04.pdf
[4] O. Janzer and B. Sudakov, Resolution of the Erdős-Sauer problem on regular subgraphs, https://doi.org/10.48550/arXiv.2204.12455
[5] L. Pyber, Regular subgraphs of dense graphs, Combinatorica, 5 (1985) 347–349. https://doi.org/10.1007/BF02579250
[6] L. Pyber, V. Rödl and E. Szemerédi, Dense graphs without 3-regular subgraphs, J. Combin. Theory Ser. B, 63 (1995) 41-54. https://doi.org/10.1006/jctb.1995.1004
[7] L. Sloman, Mathematical Connect-the-Dots Reveals How Structure Emerges, Quanta Magazine, June 23, 2022. https://www.quantamagazine.org/new-proof-shows-when-structure-must-emerge-in-graphs-20220623/
[8] C. Thomassen, Girth in graphs, J. Combin. Theory Ser. B, 35 (1983) 129-141. https://doi.org/10.1016/0095-8956(83) 90067-9