Independence numbers and chromatic numbers of some distance graphs

Problems of Information Transmission - Tập 51 - Trang 165-176 - 2015
A. V. Bobu1, O. A. Kostina1, A. E. Kupriyanov1
1Department of Mathematical Statistics and Random Processes, Faculty of Mathematics and Mechanics, Lomonosov Moscow State University, Moscow, Russia

Tóm tắt

We study a family of distance graphs in ℝ n . We present bounds for independence numbers which are asymptotically tight as n → ∞. We substantially improve upper bounds on chromatic numbers of these graphs, and in a number of cases we give explicit constructions of independence sets.

Tài liệu tham khảo

Raigorodskii, A.M., The Borsuk Problem and the Chromatic Numbers of Some Metric Spaces, Uspekhi Mat. Nauk, 2001, vol. 56, no. 1, pp. 107–146 [Russian Math. Surveys (Engl. Transl.), 2001, vol. 56, no. 1, pp. 103–139].

Raigorodskii, A.M., Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometric Graph Theory, Pach, J., Ed., Berlin: Springer, 2013, pp. 429–460.

Brass, P., Moser, W., and Pach, J., Research Problems in Discrete Geometry, New York: Springer, 2005.

Soifer, A., The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, New York: Springer, 2009.

Raigorodskii, A.M., On the Chromatic Numbers of Spheres in Euclidean Spaces, Dokl. Akad. Nauk, 2010, vol. 432, no. 2, pp. 174–177 [Dokl. Math. (Engl. Transl.), 2010, vol. 81, no. 3, pp. 379–382].

Raigorodskii, A.M., On the Chromatic Numbers of Spheres in ℝn, Combinbatorica, 2012, vol. 32, no. 1, pp. 111–123.

Agarwal, P.K. and Pach, J., Combinatorial Geometry, New York: Wiley, 1995.

Székely, L.A., Erdős on Unit Distances and the Szemerédi-Trotter Theorems // Paul Erdős and His Mathematics, II (Proc. Conf. Held in Budapest, Hungary, July 4–11, 1999), Halász, G., Lovász, L., Simonovits, M., and Sós, V.T., Eds., Bolyai Soc. Math. Stud, vol. 11, Berlin: Springer; Budapest: János Bolyai Math. Soc., 2002, pp. 649–666.

Raigorodskii, A.M., On the Chromatic Number of a Space, Uspekhi Mat. Nauk, 2000, vol. 55, no. 2, pp. 147–148 [Russian Math. Surveys (Engl. Transl.), 2000, vol. 55, no. 2, pp. 351–352].

Larman, D.G. and Rogers, C.A., The Realization of Distances within Sets in Euclidean Space, Mathematika, 1972, vol. 19, no. 1, pp. 1–24.

Raiskii, D.E., Realization of All Distances in a Decomposition of the Space ℝn into n + 1 Parts, Mat. Zametki, 1970, vol. 7, no. 3, pp. 319–323 [Math. Notes (Engl. Transl.), 1970, vol. 7, no. 3, pp. 194–196].

Balogh, J., Kostochka, A.V., and Raigorodskii, A.M., Coloring Some Finite Sets in ℝN, Discuss. Math. Graph Theory, 2013, vol. 33, no. 1, pp. 25–31.

Frankl, P. and Wilson, R., Intersection Theorems with Geometric Consequences, Combinatorica, 1981, vol. 1, no. 4, pp. 357–368.

Kahn, J. and Kalai, G., A Counterexample to Borsuk’s Conjecture, Bull. Amer. Math. Soc. (N.S.), 1993, vol. 29, no. 1, pp. 60–62.

Raigorodskii, A.M., Around the Borsuk Conjecture, Sovrem. Mat. Fundam. Napravl., 2007, vol. 23, pp. 147–164 [J. Math. Sci. (N.Y.) (Engl. Transl.), 2007, vol. 154, no. 4, pp. 604–623].

Raigorodskii, A.M., Three Lectures on the Borsuk Partition Problem, Surveys in Contemporary Mathematics, Young, N. and Choi, Y., Eds., London Math. Soc. Lect. Note Ser., vol. 347. Cambridge: Cambridge Univ. Press, 2007, pp. 202–248.

Raigorodskii, A.M., The Borsuk Partition Problem: The Seventieth Anniversary, Math. Intelligencer, 2004, vol. 26, no. 3, pp. 4–12.

MacWilliams, F.J. and Sloane, N.J.A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977. Translated under the title Teoriya kodov, ispravlyayushchikh oshibki, Moscow: Svyaz’, 1979.

Raigorodskii, A.M. and Kharlamova, A.A., On Sets of (−1, 0, 1)-Vectors with Prohibited Values of Pairwise Inner Products, Tr. Sem. Vect. Tenz. Anal., vol. 29, Moscow: Moscow State Univ., 2013, pp. 130–146.

Ziegler, G.M., Coloring Hamming Graphs, Optimal Binary Codes, and the 0/1-Borsuk Problem in Low Dimensions, Computational Discrete Mathematics: Advanced Lectures, Alt, H., Ed., Lect. Notes Comp. Sci., vol. 2122, Berlin: Springer, 2001, pp. 159–171.

Raigorodskii, A.M., The Borsuk Problem for (0, 1)-Polyhedra and Cross Polytopes, Dokl. Akad. Nauk, 2000, vol. 371, no. 5, pp. 600–603 [Dokl. Math. (Engl. Transl.), 2000, vol. 61, no. 2, pp. 256–259].

Raigorodskii, A.M., The Borsuk Problem for Integral Polyhedra, Mat. Sb., 2002, vol. 193, no. 10, pp. 139–160 [Sb. Math. (Engl. Transl.), 2002, vol. 193, no. 9–10, pp. 1535–1556].

Raigorodskii, A.M., Borsuk’s Problem for (0, 1)-Polytopes and Cross Polytopes, Dokl. Akad. Nauk, 2002, vol. 384, no. 5, pp. 593–597 [Dokl. Math. (Engl. Transl.), 2002, vol. 65, no. 3, pp. 413–416].

Raigorodskii, A.M., The Erdős-Hadwiger Problem and the Chromatic Numbers of Finite Geometric Graphs, Dokl. Akad. Nauk, 2003, vol. 392, no. 3, pp. 313–317 [Dokl. Math. (Engl. Transl.), 2003, vol. 68, no. 2, pp. 216–220].

Raigorodskii, A.M., The Problems of Borsuk, Hadwiger, and Grünbaum for Some Classes of Polytopes and Graphs, Dokl. Akad. Nauk, 2003, vol. 388, no. 6, pp. 738–742 [Dokl. Math. (Engl. Transl.), 2003, vol. 67, no. 1, pp. 85–89].

Raigorodskii, A.M., The Borsuk and Grünbaum Problems for Lattice Polytopes, Izv. Ross. Akad. Nauk, Ser. Mat., 2005, vol. 69, no. 3, pp. 81–108 [Izv. Math. (Engl. Transl.), 2005, vol. 69, no. 3, pp. 513–537].

Raigorodskii, A.M., The Erdős-Hadwiger Problem and the Chromatic Numbers of Finite Geometric Graphs, Mat. Sb., 2005, vol. 196, no. 1, pp. 123–156 [Sb. Math. (Engl. Transl.), 2005, vol. 196, no. 1–2, pp. 115–146].

Frankl, P. and Füredi, Z., Forbidding Just One Intersection, J. Combin. Theory, Ser. A, 1985, vol. 39, no. 2, pp. 160–176.

Matoušek, J., Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Berlin: Springer, 2003.

Erdős, P., Ko, C., and Rado, R., Intersection Theorems for Systems of Finite Sets, Quart. J. Math. Oxford, Ser. 2, 1961, vol. 12, pp. 313–320.

Ahlswede, R. and Blinovsky, V., Lectures on Advances in Combinatorics, Berlin: Springer, 2008.

Ahlswede, R. and Khachatrian, L.H., The Complete Nontrivial-Intersection Theorem for Systems of Finite Sets, J. Combin. Theory, Ser. A, 1996, vol. 76, no. 1, pp. 121–138.

Ahlswede, R. and Khachatrian, L.H., The Complete Intersection Theorem for Systems of Finite Sets, European J. Combin., 1997, vol. 18, no. 2, pp. 125–136.

Lovász, L., Kneser’s Conjecture, Chromatic Number, and Homotopy, J. Combin. Theory, Ser. A, 1978, vol. 25, no. 3, pp. 319–324.

Tarakanov, V.E., Kombinatornye zadachi i (0, 1)-matritsy (Combinatorial Problems and (0, 1)-Matrices), Moscow: Nauka, 1985.

Sidorenko, A.F., What We Know and What We Do Not Know about Turán Numbers, Graphs Combin., 1995, vol. 11, no. 2, pp. 179–199.

Raigorodskii, A.M., Systemy obshchikh predstavitelei v kombinatorike i ikh prilozheniya v geometrii (Systems of Common Representatives in Combinatorics and Their Applications in Geometry), Moscow: MCCME, 2009.

Turán, P., Egy gráfelméleti szélsőérték-feladatról, Mat. Fiz. Lapok., 1941, vol. 48, no. 3, pp. 436–452.

Rödl, V., On a Packing and Covering Problem, European J. Combin., 1985, vol. 6, no. 1, pp. 69–78.

Alon, N. and Spencer, J.H., The Probabilistic Method, New York: Wiley, 2000, 2nd ed. Translated under the title Veroyatnostnyi metod, Moscow: BINOM, 2007..

Thông tin
Thông tin xuất bản

Problems of Information Transmission

Tập 51

165-176

Thông tin tác giả