Об оценках в проблеме Борсука
Автор: Боголюбский Л.И., Райгородский А.М.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 3 (43) т.11, 2019 года.
Бесплатный доступ
Обсуждаются различные оценки, связанные с проблемой Борсука. Рассматриваются некоторые серии дистанционных графов и индуцированные ими двойственные конфигурации в пространствах «малых» размерностей и при росте размерности. К графам применяется модификация линейно-алгебраического метода, в результате получаются нижние оценки f(d) - минимального числа частей множеств«меньшего диаметра» из проблемы Борсука в Rd.
Гипотеза борсука, число борсука, хроматическое число пространства, число независимости, проблема нелсона-эрдёша-хадвигера, дистанционный граф, разбиение, запрещённое расстояние, граф диаметров
Короткий адрес: https://sciup.org/142223074
IDR: 142223074 | УДК: 519.174.7
On bounds in Borsuk's problem
In this work we discuss various estimates connected with Borsuk’s conjecture. We consider some series of distance graphs and corresponding induced dual configurations embedded to the spaces of "small dimensions" as well as in case of growing dimension. We then apply a modification of the linear algebra method to the graphs. This leads us to lower estimates of f(d) - the minimal possible number of subsets of "smaller diameter" in terms of Borsuk’s problem in Rd.
Список литературы Об оценках в проблеме Борсука
- Kahn J., Kalai G. A counterexample to Borsuk's conjecture // Bull. Amer. Math. Soc. (N.S.). 1993. V. 29. P. 60-62.
- Borsuk K. Drei S¨atzeu¨ber die n-dimensionale euklidische Sph¨are // Fundamenta Mathematicae. 1933. V. 20, I. 1. P. 177-190.
- Perkal J. Sur la subdivision des ensembles en parties de diam'etre inf'erieur // Colloquium Mathematicum. 1947. V. 1. P. 45.
- Hadwiger H. U¨berdeckung einer Menge durch Mengen kleineren Durchmessers // Commentarii Mathematici Helvetici. 1945. V. 18. P. 73-75.
- Riesling A.S. Borsuk's problem in three-dimensional spaces of constant curvature // Ukr. Geom. Sbornik. 1971. V. 11 P. 78-83.
- Dekster B. The Borsuk conjecture holds for bodies of revolution // Journal of Geometry. 1995. V. 52, I. 1-2. P. 64-73.
- Rogers C.A. Symmetrical sets of constant width and their partitions // Mathematika. 1971. V. 18. P. 105-111.
- Nilli A. On Borsuk's problem // Jerusalem Combinatorics '93: an international conference in combinatorics. 1994. P. 209-210.
- Райгородский А.М. О размерности в проблеме Борсука // УМН. 1997. Т. 52, вып. 6(318). С. 181-182.
- Weißbach B. Sets with large Borsuk number // Beitr¨age Algebra Geom. 2000. V. 41. P. 417- 423.
- Hinrichs A. Spherical codes and Borsuk's conjecture // Discrete Math. 2002. V. 243. P. 253- 256.
- Pikhurko O. Borsuk's conjecture fails in dimensions 321 and 322 // arXiv preprint math/0202112. 2002.
- Hinrichs A., Richter C. New sets with large Borsuk numbers // Discrete Mathematics. 2003. V. 270, I. 1-3. P. 137-147.
- Bondarenko A. On Borsuk's Conjecture for Two-Distance Sets // Discrete
- Jenrich T., Brouwer A.E. A 64-Dimensional Counterexample to Borsuk's Conjecture // Electronic Journal of Combinatorics. 2014. V. 21, I. 4. #P4.29.
- Райгородский А.М. Вокруг гипотезы Борсука // Геометрия и механика. 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. Cliques and cycles in distance graphs and graphs of diameters // Discrete Geometry and Algebraic Combinatorics. 2014. V. 625. P. 93-109.
- Raigorodskii A.M. Coloring Distance Graphs and Graphs of Diameters // Thirty Essays on Geometric Graph Theory. / J. Pach ed. Springer, 2013. P. 429-460.
- Raigorodskii A.M. Combinatorial geometry and coding theory // Fundamenta Informatica. 2016. V. 145. P. 359-369.
- Schramm O. Illuminating sets of constant width // Mathematika. 1988. V. 35, I. 2. P. 180- 189.
- Райгородский А.М. Об одной оценке в проблеме Борсука // Успехи математических наук. 1999. Т. 54, вып. 2(326). С. 185-186.
- Райгородский А.М. Гипотеза Кнезера и топологические методы в комбинаторике. Москва: МЦНМО, 2011.
- Боголюбский Л.И., Райгородский А.М. Замечание о нижних оценках хроматических чисел пространств малой размерности с метриками ℓ1 и ℓ2 // Математические заметки. 2019. Т. 105. С. 187-213.
- Райгородский А.М. Линейно-алгебраический метод в комбинаторике. Москва: МЦНМО, 2007.
- Гервер М.Л. О разбиении множеств на части меньшего диаметра: теоремы и контрпримеры // Математическое просвещение. 1999. Сер. 3, вып. 3. С. 168-183.
- https://github.com/LevBogolubsky/Borsuk_lower_linear_algebra
