Combinatorial Geometry and Coding Theory

Raigorodskii, A. M.

doi:10.3233/FI-2016-1365

Artykuł - szczegóły

Tytuł artykułu

Combinatorial Geometry and Coding Theory

Autorzy

Raigorodskii A. M.

Wybrane pełne teksty z tego czasopisma

https://fi.episciences.org/

Identyfikatory

DOI

10.3233/FI-2016-1365

Warianty tytułu

Języki publikacji

Abstrakty

In this paper, we overview three closely related problems: Nelson-Hadwiger problem on coloring spaces with forbidden monochromatics distances; Borsuk's problem on partitioning sets in spaces into parts of smaller diameter; problem of finding codes with forbidden Hamming distances.

Słowa kluczowe

hamming distance set theory problem solving coding theory combinatorial geometry topological spaces

Wydawca

IOS Press

Czasopismo

Fundamenta Informaticae

Rocznik

2016

Tom

Vol. 145, nr 3

Strony

359--369

Opis fizyczny

Bibliogr. 81 poz., tab.

Twórcy

autor

Raigorodskii A. M.

mraigor@yandex.ru

Moscow Institute of Physics and Technology, State University Dolgoprudny, Moscow, Russia
Lomonosov Moscow State University, Moscow, Russia

Bibliografia

[1] Soifer A. The Mathematical Coloring Book. Springer; 2009. ISBN-13: 978-0387746401, 10: 0387746404.
[2] Hadwiger H. Ein Überdeckungssatz für den Euklidischen Raum. Portugaliae Math. 1944; 4:140–144.
[3] Agarwal PK, Pach J. Combinatorial geometry. John Wiley and Sons Inc., New York; 1995.
[4] Brass P, Moser W, Pach J. Research problems in discrete geometry. Springer; 2005. ISBN: 978-0-387-23815-9, 978-0-387-29929-7.
[5] Klee V, Wagon S. Old and new unsolved problems in plane geometry and number theory. Math. Association of America; 1991. ISBN- 13:9780883853153, 10:0883853159.
[6] Raigorodskii AM. Borsuk’s problem and the chromatic numbers of metric spaces. Russian Math. Surveys. 2001; 56(N1):103–139. doi: 10.1070/RM2001v056n01ABEH000358.
[7] Raigorodskii AM. The chromatic numbers. Moscow Centre for Continuous Mathematical Education (MCCME), Moscow, Russia; 2015. Second edition (book in Russian).
[8] Raigorodskii AM. The linear algebra method in combinatorics. Moscow Centre for Continuous Mathematical Education (MCCME), Moscow, Russia; 2015. Second edition (book in Russian).
[9] Raigorodskii AM. Cliques and cycles in distance graphs and graphs of diameters. “Discrete Geometry and Algebraic Combinatorics”, AMS, Contemporary Mathematics. 2014; 625:93–109. doi:10.1090/conm/625/12493.
[10] Raigorodskii AM. Coloring Distance Graphs and Graphs of Diameters. Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer; 2013. p. 429–460. doi: 10.1007/978-1-4614-0110-0 23.
[11] Székely LA. Erdös on unit distances and the Szemerédi – Trotter theorems. Paul Erdös and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer. 2002; 11:649–666.
[12] Coulson D. A 15-coloring of 3-space omitting distance one. Discrete Math. 2002; 256:83–90. doi:10.1016/S0012-365X(01)00183-2.
[13] Radoičić R, Tóth G. Note on the chromatic number of the space. Discrete and Computational Geometry: The Goodman – Pollack Festschrift, 695–698. (Algorithms and Combinatorics, 25), Springer; 2003. doi:10.1007/978-3-642-55566-4 32.
[14] Nechushtan O. Note on the space chromatic number. Discrete Math. 2002; 256:499–507. doi: 10.1016/S0012-365X(00)00406-4.
[15] Cantwell K. Finite Euclidean Ramsey theory. J. Combin. Theory A. 1996; 73(N2):273–285.
[16] Ivanov LL. An estimate of the chromatic number of the space R4. Russian Math. Surveys. 2006; 61(N5):984–986. Available from: http://stacks.iop.org/0036-0279/61/i=5/a=L07.
[17] Kupavskiy AB. On coloring spheres embedded into Rn. Sb. Math. 2011; 202(N6):83–110. doi: 10.1070/SM2011v202n06ABEH004169.
[18] Cibulka J. On the chromatic number of real and rational spaces. Geombinatorics. 2008; 18(N2):53–66.
[19] Larman DG, Rogers CA. The realization of distances within sets in Euclidean space. Mathematika. 1972; 19:1–24.
[20] Kupavskiy AB, Raigorodskii AM. On the chromatic number of R9. J. of Math. Sci. 2009; 163(N6):720–731.
[21] Kupavskiy AB. On lifting of estimation of chromatic number of Rn in higher dimension. Doklady Math. 2009; 429(N3):305–308.
[22] Raigorodskii AM. On the chromatic number of a space. Russian Math. Surveys, 2000; 55(N2):351–352.
[23] Exoo G, Ismailescu D, Lim M. On the Chromatic Number of R4. Discrete and Computational Geometry. 2014; 52(N2):416–423. doi: 10.1007/s00454-014-9612-7.
[24] Exoo G, Ismailescu D. On the Chromatic Number of Rn for Small Values of n. arXiv:1408.2002.
[25] Borsuk K. Drei Sätze über die n-dimensionale euklidische Sphäre. Fundamenta Math. 1933; 20:177–190.
[26] Eggleston HG. Covering a three-dimensional set with sets of smaller diameter. J. London Math. Soc. 1955; 30:11–24.
[27] Raigorodskii AM. Around Borsuk’s conjecture. Journal of Math. Sci. 2008; 154(N4):604–623. doi: 10.1007/s10958-008-9196-y.
[28] Bondarenko A. On Borsuk’s conjecture for two-distance sets. Discrete and Comput. Geometry, 2014; 51:509–515. doi: 10.1007/s00454-014-9579-4.
[29] Jenrich T, Brouwer A. A 64-dimensional two-distance counterexample to Borsuk’s conjecture. The Electronic Journal of Combinatorics. 2014; 21(N4).
[30] Raigorodskii AM. On a bound in Borsuk’s problem. Russian Math. Surveys, 1999; 54(N2):453–454.
[31] Bourgain J, Lindenstrauss J. On covering a set in Rd by balls of the same diameter. Geometric Aspects of Functional Analysis (J. Lindenstrauss and V. Milman, eds.), Lecture Notes in Math., 1469, Springer-Verlag, Berlin; 1991. p. 138–144. Available from: http://dx.doi.org/10.1007/BFb0089220#sthash.9xuQLj7h.dpuf.
[32] Schramm O. Illuminating sets of constant width. Mathematika, 1988; 35:180–189.
[33] Hadwiger H. Überdeckung einer Menge durch Mengen kleineren Durchmessers. Comm. Math. Helv. 1945/46; 18:73–75; Mitteilung betreffend meine Note: Überdeckung einer Menge durch Mengen kleineren Durchmessers. Comm. Math. Helv. 1946/47; 19:72–73.
[34] Knast R. An approximative theorem for Borsuk’s conjecture. Proc. Cambridge Phil. Soc. 1974; N1:75–76.
[35] Rogers CA. Symmetrical sets of constant width and their partitions. Mathematika. 1971; 18:105–111.
[36] Raigorodskii AM. Borsuk’s problem for (0,1)-polyhedra and cross-polytopes. Doklady Math. 2000; 61:256–259. Available from: http://stacks.iop.org/0036-0279/56/i=1/a=R03.
[37] Raigorodskii AM. The Borsuk and Grünbaum problems for lattice polytopes. Izvestiya Math. 2005; 69(N3):513–537. Available from: http://stacks.iop.org/1064-5632/69/i=3/a=A03.
[38] Boltyanski VG, Martini H, Soltan PS. Excursions into combinatorial geometry. Universitext, Springer, Berlin; 1997. ISBN- 978-3-540-61341-1, 978-3-642-59237-9.
[39] Raigorodskii AM. Borsuk’s problem. Moscow Centre for Continuous Mathematical Education (MCCME), Moscow, Russia; 2015. Second edition (book in Russian).
[40] Raigorodskii AM. The Borsuk partition problem: the seventieth anniversary. Mathematical Intelligencer. 2004; 26(N3):4–12.
[41] Bassalygo L, Cohen G, Zémor G. Codes with forbidden distances. Discrete Mathematics. 2000; 213:3–11.
[42] Frankl P, Rödl V. Forbidden intersections. Trans. Amer. Math. Soc. 1987; 300(N1):259–286.
[43] MacWilliams FJ, Sloane NJA. The theory of error-correcting codes. North-Holland, Amsterdam; 1977. ISBN- 13:978-0444851932, 10:0444851933.
[44] Frankl P, Füredi Z. Forbidding just one intersection. Journal Combin. Theory A. 1985; 39:160–176.
[45] Erdös P, Ko Ch, Rado R. Intersection theorems for systems of finite sets. J. Math. Oxford, Sec. 1961; 12(48).
[46] Frankl P, Wilson R. Intersection theorems with geometric consequences . Combinatorica. 1981; 1:357–368.
[47] Nagy Z. A certain constructive estimate of the Ramsey number (in Hungarian). Matematikai Lapok. 1972; 23, N 301-302, 26.
[48] Bobu AV, Kostina OA, Kupriyanov AE. The independence numbers and the chromatic numbers of some distance graphs. Problems of Information Transmission. 2015; 51(N2):165–176. doi: 10.1134/S0032946015020076.
[49] Raigorodskii AM. Systems of common representatives in combinatorics and their applications to geometry. Moscow Centre for Continuous Mathematical Education (MCCME), Moscow, Russia; 2009. (book in Russian). ISBN- 10:5940575242, 13:978-5940575245.
[50] Sidorenko AF. What we know and what we do not know about Tur´an numbers. Graphs and Combinatorics. 1995; 11(N2):179–199. doi: 10.1007/BF01929486.
[51] Turán P. Egy gráfelmèleti szélsöértekfeladatrol. Mat. ´es Fiz. Lapok. 1941; 48(N3):436–453.
[52] Matoušek J. Using the Borsuk – Ulam theorem. Universitext, Springer, Berlin; 2003. ISBN- 978-3-540-00362-5, 978-3-540-76649-0.
[53] Balogh J, Kostochka AV, Raigorodskii AM. Coloring some finite sets in RN. Discussiones Mathematicae Graph Theory. 2013; 33(N1):25–31. doi: 10.7151/dmgt.1641.
[54] Ponomarenko EI, Raigorodskii AM. An improvement to Frankl–Wilson’s theorem on the number of edges of a hypergraph with forbidden intersections. Doklady Math. 2014; 89(N1):59–60.
[55] Ponomarenko EI, Raigorodskii AM. New estimates in the problem of the number of edges in a hypergraph with forbidden intersections. Problems of Information Transmission. 2013; 49(N4):384–390.
[56] Bobu AV, Kupriyanov AE, Raigorodskii AM. On the maximum number of edges in a uniform hypergraph with one forbidden intersection. Doklady Math. 2015; 92(N1):401–403. doi: 10.1134/S106456241504002X.
[57] Bobu AV, Kupriyanov AE, Raigorodskii AM. An asymptotic investigation of a problem concerning the maximum number of edges in a uniform hypergraph with one forbidden intersection. Sbornik Math. 2016; 207(N5).
[58] Ahlswede R, Blinovsky VM. Lectures on advances in combinatorics. Springer; 2008. ISBN- 13:978-3540786016, 10:3540786015.
[59] Ahlswede R, Khachatrian LH. The complete intersection theorem for systems of finite sets. Europ. J. Combin. 1997; 18:125–136.
[60] Harlamova AA, Samirov DV, Raigorodskii AM, Zvonarev AE. An improvement to a theorem of Frankl and Rödl on the number of edges in a hypergraph with forbidden intersections. Doklady Math. 2014; 90(N1):432–434. doi: 10.1134/S1064562414050068.
[61] Harlamova AA, Samirov DV, Raigorodskii AM, Zvonarev AE. On the chromatic number of a space with forbidden equilateral triangle. Sbornik Math. 2014; 205(N9):1310–1333.
[62] Raigorodskii AM, Zvonarev AE. Improvements to Frankl–Rödl’s theorem on the number of edges in a hypergraph with forbidden intersections, and their applications to the problem of finding the chromatic number of a space with forbidden equilateral triangles. Proceedings of the Steklov Mathematical Institute. 2015; 288:94–104. doi: 10.1134/S0081543815010071.
[63] Ziegler GM. Coloring Hamming graphs, optimal binary codes, and the 0/1 - Borsuk problem in low dimensions. Lect. Notes Comput. Sci. 2001; 2122:159–171. doi: 10.1007/3-540-45506-X 12.
[64] Alon N, Spencer J. The probabilistic method.Wiley - Interscience Series in Discrete Math. and Optimization, Second Edition; 2000.
[65] Bollobás B. Random Graphs. Cambridge Univ. Press, Second Edition; 2001.
[66] Erdös P, Rényi A. On random graphs I. Publ. Math. Debrecen. 1959; 6:290–297.
[67] Erdös P, Rényi A. On the evolution of random graphs. Bull. Inst. Int. Statist. Tokyo. 1961; 38:343–347.
[68] Janson S, Łuczak T, Ruciński A. Random graphs. Wiley, NY; 2000.
[69] Bogolyubskiy LI, Gusev AS, Pyaderkin MM, Raigorodskii AM. The independence numbers and the chromatic numbers of random subgraphs of some distance graphs. Doklady Math. 2014; 90(N1):462–465. doi:10.1134/S1064562414050147.
[70] Bogolyubskiy LI, Gusev AS, Pyaderkin MM, Raigorodskii AM. The independence numbers and the chromatic numbers of random subgraphs of some distance graphs. Sbornik Math. 2015; 206(N10):3–36. Available from: http://stacks.iop.org/1064-5616/206/i=10/a=1340.
[71] Bollobás B, Narayanan BP, Raigorodskii AM. On the stability of the Erdös–Ko–Rado theorem. J. Comb. Th. Ser. A. 2016; 137:64–78. doi: 10.1016/j.jcta.2015.08.002.
[72] Kupavskii AB. On random subgraphs of Kneser and Schrijver graphs. J. Comb. Th., Ser. A. 2016; 141. arXiv:1502.00699.
[73] Pyaderkin MM. Independence numbers of random subgraphs of distance graphs. Math. Notes. 2016; 99(N3):556–563. doi: 10.1134/S0001434616030299.
[74] Pyaderkin MM. Independence numbers of random subgraphs of a distance graph. Math. Notes. 2016; 99(N2):288–297.
[75] Gusev AS. New upper bound for the chromatic number of a random subgraph of a distance graph. Math. Notes. 2015; 97(N3):326–332. 10.1134/S0001434615030037.
[76] Ahlswede R, Khachatrian LH. The complete nontrivial-intersection theorem for systems of finite sets. J. Combin. Theory A. 1996; 76:125–136. doi: 10.1006/eujc.1995.0092.
[77] Erdös P, Rényi A. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 1960; 5:17–61.
[78] Raigorodskii AM. Three lectures on the Borsuk partition problem. London Mathematical Society Lecture Note Series. 2007; 347:202–248. Available from: http://dx.doi.org/10.1017/CBO9780511666315.007.
[79] Raigorodskii AM. The Borsuk problem for integral polytopes. Sbornik Math. 2002; 193:1535–1556.
[80] Raigorodskii AM. Borsuk’s problem for (0; 1)-polytopes and cross-polytopes. Doklady Math. 2002; 65:413–416.
[81] Raigorodskii AM. The Borsuk, Grünbaum, and Hadwiger problems for some classes of polytopes and graphs. Doklady Math. 2003; 67(N1):85–89.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-f87f7623-6500-47b9-9303-fe018ac074b9