Экспоненциально рамсеевские множества

Изучены хроматические числа пространств Rnp = (Rn,p) с запрещенными одноцветными множествами. Для некоторых множеств впервые получены явные нижние экспоненциально растущие оценки соответствующих хроматических чисел, для других – ранее известные оценки были значительно усилены.

Ключевые слова

Источник финансирования

Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (номер проекта 18-01-00355) и гранта Президента Российской Федерации для государственной поддержки ведущих научных школ (номер гранта НШ-6760.2018.1).

Получено

13.12.2018

Дата публикации

13.12.2018

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Сагдеев А. А. Экспоненциально рамсеевские множества // Проблемы передачи информации – 2018. – Tом 54. – Выпуск 4 C. 82-109 [Электронный ресурс]. URL: http://ras.jes.su/ppi/s055529230003080-2-1 (дата обращения: 06.05.2024). DOI: 10.31857/S055529230003080-2
MLA	Sagdeev, Arseny "Exponentially Ramsey Sets." Problemy peredachi informatsii 54.4 (2018):82-109. DOI: 10.31857/S055529230003080-2
APA	Sagdeev A. (2018). Exponentially Ramsey Sets. Problemy peredachi informatsii 54(4), pp.82-109 DOI: 10.31857/S055529230003080-2

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 1024

Оценка читателей: голосов 0

1. Сойфер А. Хроматическое число плоскости: его прошлое, настоящее и будущее // Матем. просвещение. Сер. 3. Вып. 8. М.: Изд-во МЦНМО, 2004. С. 186–221.

2. de Grey A.D.N.J. The Chromatic Number of the Plane Is at Least 5 // arXiv:1804.02385v2 [math.CO], 2018.

3. Frankl P., Wilson R.M. Intersection Theorems with Geometric Consequences // Combinatorica. 1981. V. 1. № 4. P. 357–368.

4. Kupavskiy A. On the Chromatic Number of Rn with an Arbitrary Norm // Discrete Math. 2011. V. 311. № 6. P. 437–440.

5. Райгородский А.М. Ох роматическом числе пространства // УМН. 2000. Т. 55. № 2. С. 147–148.

6. Larman D.G., Rogers C.A. The Realization of Distances within Sets in Euclidean Space // Mathematika. 1972. V. 19. № 1. P. 1–24.

7. Райгородский А.М. Охро матическом числе пространства с метрикой lq // УМН. 2004. Т. 59. № 5 (359). С. 161–162.

8. Sz?ekely L.A. Erd?os on Unit Distances and the Szemer?edi–Trotter Theorems // Paul Erd?os and His Mathematics, II (Proc. Conf. Held in Budapest, Hungary. July 4–11, 1999). Bolyai Soc. Math. Stud. V. 11. Berlin: Springer; Budapest: J?anos Bolyai Math. Soc., 2002. P. 649–666.

9. Graham R.L., Rothschild B.L., Spencer J.H. Ramsey Theory // New York: John Wiley & Sons, 1990.

10. Erd?os P., Graham R.L., Montgomery P., Rothschild B.L., Spencer J., Straus E.G. Euclidean Ramsey Theorems. I // J. Combin. Theory Ser. A. 1973. V. 14. P. 341–363.

11. Erd?os P., Graham R.L., Montgomery P., Rothschild B.L., Spencer J., Straus E.G. Euclidean Ramsey Theorems. II, III // Infinite and Finite Sets (Colloq. dedicated to P. Erd?os on his 60th birthday. Keszthely, Hungary. June 25 – July 1, 1973). V. 1. Colloq. Math. Soc. J?anos Bolyai. V. 10. Amsterdam: North-Holland, 1975. P. 529–557, 559–583.

12. Frankl P., R?odl V. All Triangles Are Ramsey // Trans. Amer. Math. Soc. 1986. V. 297. № 2. P. 777–779.

13. Frankl P., R?odl V. A Partition Property of Simplices in Euclidean Space // J. Amer. Math. Soc. 1990. V. 3. № 1. P. 1–7.

14. Frankl P., R?odl V. Strong Ramsey Properties of Simplices // Israel J. Math. 2004. V. 139. № 1. P. 215–236. 107

15. K?r???z I. Permutation Groups in Euclidean Ramsey Theory // Proc. Amer. Math. Soc. 1991. V. 112. № 3. P. 899–907.

16. K?r???z I. All Trapezoids Are Ramsey // Discrete Math. 1992. V. 108. № 1–3. P. 59–62.

17. Cantwell K. Edge-Ramsey Theory // Discrete Comput. Geom. 1996. V. 15. №3. P. 341–352.

18. Cantwell K. All Regular Polytopes Are Ramsey // J. Combin. Theory Ser. A. 2007. V. 114. № 3. P. 555–562.

19. Frankl P., R?odl V. Forbidden Intersections // Trans. Amer. Math. Soc. 1987. V. 300. № 1. P. 259–286.

20. Звонарев А.Е., Райгородский А.М., Самиров Д.В., Харламова А.А. Ох роматическом числе пространства с запрещенным равносторонним треугольником // Матем. сб. 2014. Т. 205. № 9. С. 97–120.

21. Звонарев А.Е., Райгородский А.М. Улучшения теоремы Франкла –Рёдля о числе ребер гиперграфа с запрещенным пересечением и их следствия в задаче о хроматическом числе пространства с запрещенным равносторонним треугольником // Тр. МИАН. 2015. Т. 288. С. 109–119.

22. Райгородский А.М., Сагдеев А.А. Охро матическом числе пространства с запрещенным правильным симплексом // ДАН. 2017. Т. 472. № 2. С. 127–129.

23. Просанов Р.И., Райгородский А.М., Сагдеев А.А. Улучшения теоремы Франкла –Рёдля и геометрические следствия // ДАН. 2017. Т. 475. № 2. С. 137–139.

24. Сагдеев А.А. Отеореме Франкла – Рэдла // Изв. РАН. Сер. матем. 2018. Т. 82. № 6. С. 128–157.

25. Сагдеев А.А. Улучшенная теорема Франкла –Рёдля и некоторые ее геометрические следствия // Пробл. передачи информ. 2018. Т. 54. № 2. С. 45–72.

26. Райгородский А.М. Проблема Борсука и хроматические числа некоторых метрических пространств // УМН. 2001. Т. 56. № 1 (337). С. 107–146.

27. Райгородский А.М. Вокруг гипотезы Борсука // Современная математика. Фундаментальные направления. 2007. Т. 23. С. 147–164.

28. Raigorodskii A.M. Coloring Distance Graphs and Graphs of Diameters // Thirty Essays on Geometric Graph Theory. New York: Springer, 2013. P. 429–460.

29. Raigorodskii A.M. Cliques and Cycles in Distance Graphs and Graphs of Diameters // Discrete Geometry and Algebraic Combinatorics. Contemp. Math. V. 625. Providence, RI: Amer. Math. Soc., 2014. P. 93–109.

30. Raigorodskii A.M. Combinatorial Geometry and Coding Theory // Fund. Inform. 2016. V. 145. № 3. P. 359–369.

31. Cherkashin D., Kulikov A., Raigorodskii A. On the Chromatic Numbers of Small-Dimensional Euclidean Spaces // Discrete Appl. Math. 2018. V. 243. P. 125–131.

32. Просанов Р.И. Верхние оценки хроматических чисел евклидовых пространств с запрещенными рамсеевскими множествами // Матем. заметки. 2018. Т. 103. № 2. С. 248–257.

33. Прахар К. Распределение простых чисел. М.: Мир, 1967.

34. Baker R.C., Harman G., Pintz J. The Difference between Consecutive Primes, II // Proc. London Math. Soc. 2001. V. 83. № 3. P. 532–562.

35. Райгородский А.М. Линейно-алгебраический метод в комбинаторике. М.: МЦНМО, 2015.

36. Пономаренко Е.И., Райгородский А.М. Новые оценки в задаче о числе ребер гиперграфа с запретами на пересечения // Пробл. передачи информ. 2013. Т. 49. № 4. С. 98–104.

37. Райгородский А.М., Сагдеев А.А. Об одной оценке в экстремальной комбинаторике // ДАН. 2018. Т. 478. № 3. С. 271–273.

38. Бобу А.В., Куприянов А.Э., Райгородский А.М. Ом аксимальном числе ребер однородного гиперграфа с одним запрещенным пересечением // ДАН. 2015. Т. 463. № 1. С. 11–13.

39. Бобу А.В., Куприянов А.Э., Райгородский А.М. Асимптотическое исследование задачи о максимальном числе ребер однородного гиперграфа с одним запрещенным пересечением // Матем. сб. 2016. Т. 207. № 5. С. 17–42.

40. Бобу А.В., Куприянов А.Э., Райгородский А.М. Очис ле ребер однородного гиперграфа с диапазоном разрешенных пересечений // Пробл. передачи информ. 2017. Т. 53. № 4. С. 16–42.

41. Бобу А.В., Куприянов А.Э., Райгородский А.М. Очис ле ребер однородного гиперграфа с диапазоном разрешенных пересечений // ДАН. 2017. Т. 475. № 4. С. 365–368.

42. Холл М. Комбинаторика. М.: Мир, 1970.

43. Paley R.E.A.C. On Orthogonal Matrices // J. Math. Phys. Mass. Inst. Techn. 1933. V. 12. P. 311–320.