Several Directions of Computer-Aided Investigations in Combinatorics and Geometry
Keywords:
distance graph, graph of diameters, Ramsey number, chromatic number, Borsuk’s problem
Abstract
Andrey M. Raigorodskiy: In the paper we present some classical problems of combinatorics, which admit computer-aided solutions. Among these problems, we have Borsuk’s problem on partitioning sets into parts of smaller diameter and problems of Ramsey theory.
References
[1] A. M. Raigorodskii, Problema Borsuka [Borsuk partition problem], Moscow, Russia: MCCME, 2015 (in Russian).
[2] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters,” in Discrete Geometry and Algebraic Combinatorics (Contemporary Mathematics), vol. 625, AMS, 2014, pp. 93–109; doi: 10.1090/conm/625
[3] A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters,” in Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer, 2013, pp. 429–460; doi: 10.1007/978-1-4614-0110-0_23
[4] A. M. Raigorodskii, “Three lectures on the Borsuk partition problem,” in London Mathematical Society Lecture Note Series, vol. 347, Cambridge University Press, 2007, pp. 202–248.
[5] A. M. Raigorodskii, “The Borsuk partition problem: the seventieth anniversary,” Mathematical Intelligencer, vol. 26, no. 3, pp. 4‒12, 2004; doi:10.1007/BF02986745
[6] A. M. Raigorodskii, “Vokrug gipotezy Borsuka” [Around Borsuk’s hypothesis], Contemporary Mathematics. Fundamental Directions, vol. 23 Geometry and Mechanics, pp. 147–164, 2007 (in Russian).
[7] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv” [Borsuk's problem and the chromatic numbers of some metric spaces], RUSS MATH SURV, vol. 56, no. 1, pp. 107–146, 2001 (in Russian); doi:10.1070/RM2001v056n01ABEH000358
[8] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike [The linear algebraic method in combinatorics], 2nd ed. Moscow, Russia: MCCME, 2015 (in Russian).
[9] V. G. Boltyanskii and I. Ts. Gokhberg, Teoremy i zadachi kombinatornoi geometrii [Theorems and problems of combinatorial geometry], Moscow, Russia: Nauka, 1965.
[10] P. Brass, W. Moser and J. Pach, Research problems in discrete geometry, NY: Springer, 2005.
[11] V. G. Boltyanski, H. Martini, and P. S. Soltan, Excursions into combinatorial geometry. Universitext, Berlin: Springer, 1997.
[12] G. M. Ziegler, “Coloring Hamming graphs, optimal binary codes, and the 0/1 ‒ Borsuk problem in low dimensions” in Computational Discrete Mathematics (Lecture Notes in Computer Science), vol. 2122, 2001, pp. 159–171.
[13] V. B. Goldshteyn, “O problemakh Borsuka i Gryunbauma dlya (0,1)- i (¡1,0,1)-mnogogrannikov v prostranstvakh maloi razmernosti” [Borsuk's and Grunbaum’s problems for (0, 1)- and (¡1, 0, 1)-polyhedrons in low dimensions], Ph.D. dissertation, CC RAS, Moscow, Russia, 2013 (in Russian).
[14] A. M. Raigorodskii, Modeli sluchainykh grafov [The models of random graphs], 2nd ed. Moscow, Russia: MCCME, 2016 (in Russian).
[15] A. M. Raigorodskii, Veroyatnost' i algebra v kombinatorike [The probability and algebra in combinatorics], 3rd ed. Moscow, Russia: MCCME, 2016 (in Russian).
[16] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, 2nd ed. NY: John Wily and Sons, 1990.
[17] S. Radziszowski, “Small Ramsey Numbers,” Electronic Journal of Cominatorics, Revision #14, Dynamic Survey #DS1: Jan 12, 2014.
[18] A. M. Raigorodskii, Khromaticheskie chisla [Chromatic numbers], 2nd ed. Moscow, Russia: MCCME, 2016 (in Russian).
[19] M. V. Titova, “Kombinatornye i veroyatnostnye metody v zadachakh o geometricheskikh chislakh Ramseya” [Combinatorial and probabilistic methods in problems of geometric Ramsey Numbers], Ph.D. dissertation, MSU, Moscow, Russia, 2013 (in Russian).
[20] N. Alon and A. Kupavskii, “Two notions of unit distance graphs”, Journal of Combinatorial Theory, Series A, vol. 125, pp. 1–17, 2014; doi: 10.1016/j.jcta.2014.02.006.
[2] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters,” in Discrete Geometry and Algebraic Combinatorics (Contemporary Mathematics), vol. 625, AMS, 2014, pp. 93–109; doi: 10.1090/conm/625
[3] A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters,” in Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer, 2013, pp. 429–460; doi: 10.1007/978-1-4614-0110-0_23
[4] A. M. Raigorodskii, “Three lectures on the Borsuk partition problem,” in London Mathematical Society Lecture Note Series, vol. 347, Cambridge University Press, 2007, pp. 202–248.
[5] A. M. Raigorodskii, “The Borsuk partition problem: the seventieth anniversary,” Mathematical Intelligencer, vol. 26, no. 3, pp. 4‒12, 2004; doi:10.1007/BF02986745
[6] A. M. Raigorodskii, “Vokrug gipotezy Borsuka” [Around Borsuk’s hypothesis], Contemporary Mathematics. Fundamental Directions, vol. 23 Geometry and Mechanics, pp. 147–164, 2007 (in Russian).
[7] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv” [Borsuk's problem and the chromatic numbers of some metric spaces], RUSS MATH SURV, vol. 56, no. 1, pp. 107–146, 2001 (in Russian); doi:10.1070/RM2001v056n01ABEH000358
[8] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike [The linear algebraic method in combinatorics], 2nd ed. Moscow, Russia: MCCME, 2015 (in Russian).
[9] V. G. Boltyanskii and I. Ts. Gokhberg, Teoremy i zadachi kombinatornoi geometrii [Theorems and problems of combinatorial geometry], Moscow, Russia: Nauka, 1965.
[10] P. Brass, W. Moser and J. Pach, Research problems in discrete geometry, NY: Springer, 2005.
[11] V. G. Boltyanski, H. Martini, and P. S. Soltan, Excursions into combinatorial geometry. Universitext, Berlin: Springer, 1997.
[12] G. M. Ziegler, “Coloring Hamming graphs, optimal binary codes, and the 0/1 ‒ Borsuk problem in low dimensions” in Computational Discrete Mathematics (Lecture Notes in Computer Science), vol. 2122, 2001, pp. 159–171.
[13] V. B. Goldshteyn, “O problemakh Borsuka i Gryunbauma dlya (0,1)- i (¡1,0,1)-mnogogrannikov v prostranstvakh maloi razmernosti” [Borsuk's and Grunbaum’s problems for (0, 1)- and (¡1, 0, 1)-polyhedrons in low dimensions], Ph.D. dissertation, CC RAS, Moscow, Russia, 2013 (in Russian).
[14] A. M. Raigorodskii, Modeli sluchainykh grafov [The models of random graphs], 2nd ed. Moscow, Russia: MCCME, 2016 (in Russian).
[15] A. M. Raigorodskii, Veroyatnost' i algebra v kombinatorike [The probability and algebra in combinatorics], 3rd ed. Moscow, Russia: MCCME, 2016 (in Russian).
[16] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, 2nd ed. NY: John Wily and Sons, 1990.
[17] S. Radziszowski, “Small Ramsey Numbers,” Electronic Journal of Cominatorics, Revision #14, Dynamic Survey #DS1: Jan 12, 2014.
[18] A. M. Raigorodskii, Khromaticheskie chisla [Chromatic numbers], 2nd ed. Moscow, Russia: MCCME, 2016 (in Russian).
[19] M. V. Titova, “Kombinatornye i veroyatnostnye metody v zadachakh o geometricheskikh chislakh Ramseya” [Combinatorial and probabilistic methods in problems of geometric Ramsey Numbers], Ph.D. dissertation, MSU, Moscow, Russia, 2013 (in Russian).
[20] N. Alon and A. Kupavskii, “Two notions of unit distance graphs”, Journal of Combinatorial Theory, Series A, vol. 125, pp. 1–17, 2014; doi: 10.1016/j.jcta.2014.02.006.
Published
2017-06-03
How to Cite
Райгородский, А. М. (2017). Several Directions of Computer-Aided Investigations in Combinatorics and Geometry. Computer Tools in Education, (3), 25-31. Retrieved from http://cte.eltech.ru/ojs/index.php/kio/article/view/1399
Issue
Section
Unsolved Problems for Young Scientists
This work is licensed under a Creative Commons Attribution 4.0 International License.
