Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I (North-Holland Publ., Amsterdam, 1977).
Z. Nagy, “A certain constructive estimate of the Ramsey number,” Mat. Lapok 23, 301–302 (1972).
P. Frankl and R. Wilson, “Intersection theorems with geometric consequences,” Combinatorica 1 (4), 357–368 (1981).
A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters,” in Discrete Geometry and Algebraic Combinatorics, Contemp. Math. (Amer. Math. Soc., Providence, RI, 2014), Vol. 625, pp. 93–109.
A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters,” in Thirty Essays on Geometric Graph Theory (Springer, New York, 2013), pp. 429–460.
B. Bollobás, B. P. Narayanan, and A. M. Raigorodskii, “On the stability of the Erdős—Ko—Rado theorem,” J. Combin.Theory Ser. A 137, 64–78 (2016).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, “Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection,” Mat. Zametki 207 (5), 17–42 (2016).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, Math. Notes 207 (5), 652–677 (2016).
A. M. Raigorodskii, “Combinatorial geometry and coding theory,” Fund. Inform. 145 (3), 359–369 (2016).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, “On the maximal number of edges in a uniform hypergraph with one forbidden intersection,” Dokl. Akad. Nauk 463 (1), 11–13 (2015).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, Dokl. Math. 92 (1), 401–403 (2015).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, “On the number of edges of a uniform hypergraph with a range of allowed intersections,” Problemy Peredachi Informatsii 53 (4), 16–42 (2017).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, Probl. Inform. Transm. 53 (4), 319–342 (2017).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, “On the number of edges in a uniform hypergraph with a range of permitted intersections,” Dokl. Akad. Nauk 475 (4), 365–368 (2017).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, Dokl. Math. 96 (1), 354–357 (2017).
R. I. Prosanov, A. A. Sagdeev, and A. M. Raigorodskii, “Improvements of the Frankl—Rödl theorem and geometric consequences,” Dokl. Akad. Nauk 475 (2), 137–139 (2017).
R. I. Prosanov, A. A. Sagdeev, and A. M. Raigorodskii, Dokl. Math. 96 (1), 336–338 (2017).
D. Cherkashin, A. Kulikov and A. Raigorodskii, “On the chromatic numbers of small-dimensional Euclidean spaces,” Discrete Appl. Math. 243, 125–131 (2018).
L. I. Bogolyubskii, A. S. Gusev, M. M. Pyaderkin, and A. M. Raigorodskii, “Independence numbers and chromatic numbers of the random subgraphs of some distance graphs,” Mat. Sb. 206 (10), 3–36 (2015).
L. I. Bogolyubskii, A. S. Gusev, M. M. Pyaderkin, and A. M. Raigorodskii, Sb. Math. 206 (10), 1340–1374 (2015).
A. V. Bobu, O. A. Kostina, and A. E. Kupriyanov, “Independence numbers and chromatic numbers of some distance graphs,” Problemy Peredachi Informatsii 51 (2), 86–98 (2015).
A. V. Bobu, O. A. Kostina, and A. E. Kupriyanov, Probl. Inform. Transm. 51 (2), 165–176 (2015).
M. M. Pyaderkin, “Independence numbers of random subgraphs of distance graphs,” Mat. Zametki 99 (4), 564–573 (2016).
M. M. Pyaderkin, Math. Notes 99 (4), 556–563 (2016).
J. Balogh, A. Kostochka, and A. Raigorodskii, “Coloring some finite sets in ℝn,” Discuss. Math. Graph Theory 33 (1), 25–31 (2013).
R. C. Baker, G. Harman, and J. Pintz, “The difference between consecutive primes. II,” Proc. London Math. Soc. (3) 83 (3), 532–562 (2001).
H. Cramer, “Some theorems concerning prime numbers,” Ark. Mat., Astron. Fys. 15 (5) (1921).
I. M. Vinogradov, Foundations of Number Theory (“Regular and Chaotic Dynamics,” Moscow—Izhevsk, 2003) [in Russian].
R. C. Bose and S. Chowla, “Theorems in the additive theory of numbers,” Comment. Math. Helv. 37, 141–147 (1962).
Author information
Authors and Affiliations
Corresponding author
Additional information
Russian Text © The Author(s), 2020, published in Matematicheskie Zametki, 2020, Vol. 107, No. 2, pp. 210–220.
Rights and permissions
About this article
Cite this article
Zakharov, D.A. Chromatic Numbers of Some Distance Graphs. Math Notes 107, 238–246 (2020). https://doi.org/10.1134/S000143462001023X
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S000143462001023X