Избранные задачи комбинаторной геометрии и теории графов

Автор: Райгородский А.М.

Журнал: Труды Московского физико-технического института @trudy-mipt

Статья в выпуске: 4 (12) т.3, 2011 года.

Бесплатный доступ

Рассматривается несколько современных направлений в комбинаторной геометрии и теории графов. Приводятся основные проблемы и обсуждаются наиболее перспек- тивные области исследований.

Короткий адрес: https://sciup.org/142185784

IDR: 142185784

Список литературы Избранные задачи комбинаторной геометрии и теории графов

Borsuk K. Drei SЁatze Ёuber die..-dimensionale euklidische SphЁare//Fundamenta Math. -1933. -V. 20. -P. 177-190.
Hadwiger H. ЁUberdeckung einer Menge durch Mengen kleineren Durchmessers//Comm. Math. Helv. -1945/46. -V. 18. -P. 73-75.
Kahn J., Kalai G. A counterexample to Borsuks conjecture//Bulletin (new series) of the AMS. -1933. -V. 29, N 1. -P. 60-62.
Frankl P., Wilson R.M. Intersection theorems with geometric consequences//Combinatorica. -1981. -V. 1. -P. 357-368.
Райгородский А.М. Об одной оценке в проблеме Борсука//Успехи матем. наук. -1999. -Т. 54, вып. 2. -С. 185-186.
Schramm O. Illuminating sets of constant width//Mathematika. -1988. -V. 35. -P. 180-189.
Bourgain J., Lindenstrauss J. On covering a set in R. by balls of the same diameter//Lecture Notes in Math. -1991. -V. 1469. -P. 138-144.
Райгородский А.М. Проблема Борсука и хроматические числа метрических пространств//Успехи матем. наук. -2001. -Т. 56, вып. 1. -С. 107-146.
Райгородский А.М. Проблема Борсука. -М.: МЦНМО, 2006. -56 с.
Райгородский А.М. Вокруг гипотезы Борсука//Итоги науки и техники. -2007. -Т. 23. -С. 147-164.
Raigorodskii A.M. Three lectures on the Borsuk partition problem//London Mathematical Society Lecture Note Series. -2007. -V. 347. -P. 202-248.
Raigorodskii A.M. The Borsuk partition problem: the seventieth anniversary//Mathematical Intelligencer. -2004. -V. 26, N 3. -P. 4-12.
Raigorodskii A.M. Coloring distance graphs and graphs of diameters//to appear.
Boltyanski V.G., Martini H., Soltan P.S. Excursions into combinatorial geometry. -Berlin: Springer, 1997. -500 c.
Brass P., Moser W., Pach J. Research problems in discrete geometry. -Berlin: Springer, 2005. -500 c.
Райгородский А.М. Хроматические числа. -М.: МЦНМО, 2003. -44 с.
Райгородский А.М. Линейно-алгебраический метод в комбинаторике. -М.: МЦНМО, 2007. -136 с.
Soifer A. The Mathematical Coloring Book. -Springer, 2009. -800 c.
ODonnell P. Arbitrary girth, 4-chromatic unit distnace graphs in the plane. Graph description//Geombinatorics. -2000. -V. 9. -P. 145-152.
ODonnell P. Arbitrary girth, 4-chromatic unit distance graphs in the plane. Graph embedding//Geombinatorics. -2000. -V. 9. -P. 180-193.
Bollobґas B. Random Graphs. -Cambridge Univ. Press, 2001. -520 c.
Колчин В.Ф. Случайные графы. -М.: Физматлит, 2004. -256 с.
Janson S., Luczak T., RuciЃLnski A. Random graphs.. New York: Wiley, 2000.. 333 „ѓ.
Райгородский А.М. Модели случайных графов. -М.: МЦНМО, 2011. -136 с.
ErdЅos P., Rґenyi A. On random graphs I//Publ. Math. Debrecen. -1959. -V. 6. -P. 290-297.
ErdЅos P., Rґenyi A. On the evolution of random graphs.//Publ. Math. Inst. Hungar. Acad. Sci. -1960. -V. 5. -P. 17-61.
Erd˝os P., R.enyi A. On the evolution of random graphs//Bull. Inst. Int. Statist. Tokyo. -1961. -V. 38. -P. 343-347.
Райгородский А.М. Модели случайных графов//Труды МФТИ. -2010. -Т. 2, № 4(8). -С. 130-140.
Алон Н., Спенсер Дж. Вероятностный метод. -М.: Бином. Лаборатория знаний, 2007. -320 с.
Barabґasi L.-A., Albert R. Emergence of scaling in random networks//Science. -1999. -V. 286. -P. 509-512.
Barab.asi L.-A., Albert R., Jeong H. Scale-free characteristics of random networks: the topology of the world-wide web//Physica. -2000. -V. A281. -P. 69-77.
Albert R., Jeong H., Barabґasi L.A. Diameter of the world-wide web//Nature. -1999. -V. 401. -P. 130-131.
Bollobґas B., Riordan O. Mathematical results on scale-free random graphs//Handbook of graphs and networks. -Weinheim: Wiley-VCH, 2003. -P. 1-34.
Райгородский А.М. Экстремальные задачи теории графов и анализ данных. -М.: Регулярная и хаотическая динамика, 2009. -120 с.
Bollobґas B., Riordan O. The diameter of a scale-free random graph//Combinatorica. -2004. -V. 24, N 1. -P. 5-34.
Bollob.as B., Riordan O., Spencer J., Tusn.ady G. The degree sequence of a scale-free random graph process//Random Structures Algorithms. -2001. -V. 18, N 3. -P. 279-290.
Grechnikov E.A. An estimate for the number of edges between vertices of given degrees in random graphs in the Bollob.as-Riordan model//Moscow Journal of Combinatorics and Number Theory. -2011. -V. 1, N 2.
Ostroumova L.A., Grechnikov E.A. The distribution of second degrees in the Bollobґas-Riordan random graph model//arXiv:1108.5585v1.
Radziszowski S.P. Small Ramsey Numbers//http://www.combinatorics.org/Surveys/ds1/sur.pdf.
Райгородский А.М. Вероятность и алгебра в комбинаторике. -М.: МЦНМО, 2010. -64 с.
Graham R.L., Rothschild B.L., Spencer J.H. Ramsey theory. -New York: John Wily and Sons, 1990. -300 с.
Erd˝os P., Szekeres G. A combinatorial problem in geometry//Compositio Math. -1935. -V. 2. -P. 463-470.
Conlon D. A new upper bound for the bipartite Ramsey problem//J. Graph Theory. -2000. -V. 58. -P. 351-356.
Morris W., Soltan V. The ErdЅos-Szekeres problem on points in convex position//Bulletin (new series) of the Amer. Math. Soc. -2000. -V. 37, N 4. -P. 437-458.
Кошелев В.А. Задача Эрдеша-Секереша о пустых шестиугольниках на плоскости//Моделирование и анализ информационных систем. -2009. -Т. 16, № 2. -С. 22-74.
Horton J.D. Sets with no empty 7-gons//Canad. Math. Bull. -1983. -V. 26. -P. 482-484.
Кошелев В.А. Почти пустые шестиугольники//Фундаментальная и прикладная математика. -2008. -Т. 14, № 6. -С. 91-120.
Кошелев В.А. Теорема Эрдеша-Секереша и сравнения//Математические заметки. В печати.
Райгородский А.М., Шабанов Д.А. Задача Эрдеша-Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы//Успехи матем. наук. -2011. -Т. 66.

Еще

Статья обзорная