Chromatic Numbers of Some Distance Graphs

D. A. Zakharov

Matematičeskie zametki, Tome 107 (2020) no. 2, pp. 210-220.

Résumé

For positive integers $n>r>s$, $G(n,r,s)$ is the graph whose vertices are the $r$-element subsets of an $n$-element set, two subsets being adjacent if their intersection contains exactly $s$ elements. We study the chromatic numbers of this family of graphs. In particular, the exact value of the chromatic number of $G(n,3,2)$ is found for infinitely many $n$. We also improve the best known upper bounds for chromatic numbers for many values of the parameters $r$ and $s$ and for all sufficiently large $n$.

Détail

Keywords: chromatic number, distance graph, upper bound.

Bibliographie

[1] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Publ., Amsterdam, 1977 | MR | Zbl

[2] Z. Nagy, “A certain constructive estimate of the Ramsey number”, Mat. Lapok, 23 (1972), 301–302 | MR

[3] P. Frankl, R. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368 | DOI | MR | Zbl

[4] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete Geometry and Algebraic Combinatorics, Contemp. Math., 625, Amer. Math. Soc., Providence, RI, 2014, 93–109 | MR | Zbl

[5] A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters”, Thirty Essays on Geometric Graph Theory, Springer, New York, 2013, 429–460 | MR | Zbl

[6] B. Bollobás, B. P. Narayanan, A. M. Raigorodskii, “On the stability of the Erdős–Ko–Rado theorem”, J. Combin. Theory Ser. A, 137 (2016), 64–78 | DOI | MR | Zbl

[7] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “Asimptoticheskoe issledovanie zadachi o maksimalnom chisle reber odnorodnogo gipergrafa s odnim zapreschennym peresecheniem”, Matem. sb., 207:5 (2016), 17–42 | DOI | MR | Zbl

[8] A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fund. Inform., 145:3 (2016), 359–369 | DOI | MR | Zbl

[9] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “O maksimalnom chisle reber odnorodnogo gipergrafa s odnim zapreschennym peresecheniem”, Dokl. AN, 463:1 (2015), 11–13 | DOI | Zbl

[10] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “O chisle reber odnorodnogo gipergrafa s diapazonom razreshennykh peresechenii”, Probl. peredachi inform., 53:4 (2017), 16–42

[11] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “O chisle reber odnorodnogo gipergrafa s diapazonom razreshennykh peresechenii”, Dokl. AN, 475:4 (2017), 365–368 | DOI | Zbl

[12] R. I. Prosanov, A. A. Sagdeev, A. M. Raigorodskii, “Uluchsheniya teoremy Frankla–Redlya i geometricheskie sledstviya”, Dokl. AN, 475:2 (2017), 137–139 | DOI | Zbl

[13] D. Cherkashin, A. Kulikov, A. Raigorodskii, “On the chromatic numbers of small-dimensional Euclidean spaces”, Discrete Appl. Math., 243 (2018), 125–131 | DOI | MR | Zbl

[14] L. I. Bogolyubskii, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Chisla nezavisimosti i khromaticheskie chisla sluchainykh podgrafov nekotorykh distantsionnykh grafov”, Matem. sb., 206:10 (2015), 3–36 | DOI | MR | Zbl

[15] A. V. Bobu, O. A. Kostina, A. E. Kupriyanov, “Chisla nezavisimosti i khromaticheskie chisla nekotorykh distantsionnykh grafov”, Probl. peredachi inform., 51:2 (2015), 86–98 | Zbl

[16] M. M. Pyaderkin, “Chisla nezavisimosti sluchainykh podgrafov distantsionnykh grafov”, Matem. zametki, 99:4 (2016), 564–573 | DOI | MR | Zbl

[17] J. Balogh, A. Kostochka, A. Raigorodskii, “Coloring some finite sets in ${\mathbb R}^n$”, Discuss. Math. Graph Theory, 33:1 (2013), 25–31 | DOI | MR | Zbl

[18] R. C. Baker, G. Harman, J. Pintz, “The difference between consecutive primes. II”, Proc. London Math. Soc. (3), 83:3 (2001), 532–562 | DOI | MR | Zbl

[19] H. Cramèr, “Some theorems concerning prime numbers”, Ark. Mat., Astron. Fys., 15:5 (1921) | Zbl

[20] I. M. Vinogradov, Osnovy teorii chisel, NITs “Regulyarnaya i khaoticheskaya dinamika”, M.–Izhevsk, 2003

[21] R. C. Bose, S. Chowla, “Theorems in the additive theory of numbers”, Comment. Math. Helv., 37 (1962), 141–147 | DOI | MR | Zbl