Estimates of the Number of Edges in Subgraphs of Johnson Graphs

E. A. Neustroeva ; A. M. Raigorodskii

Matematičeskie zametki, Tome 115 (2024) no. 2, pp. 266-275.

Résumé

We consider special distance graphs and estimate the number of edges in their subgraphs. The estimates obtained improve some known results.

Détail

Keywords: distance graph, Johnson graph, Turan's theorem, number of edges of a subgraph.

Bibliographie

[1] L. A. Székely, “Erdös on unit distances and the Szemerédi–Trotter theorems”, Paul Erdös and His Mathematics (Budapest, 1999), v. 2, Bolyai Soc. Math. Stud., 11, 11, J. Bolyai Math. Soc., Budapest, 2002, 649–666 | MR

[2] 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

[3] A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters”, Thirty Essays on Geometric Graph Theory, Springer, New York, 2013, 429–460 | DOI | MR

[4] A. M. Raigorodskii, “O khromaticheskikh chislakh sfer v evklidovykh prostranstvakh”, Dokl. RAN, 2010, no. 432, 174–177 | DOI | MR

[5] A. M. Raigorodskii, “Vokrug gipotezy Borsuka”, Geometriya i mekhanika, SMFN, 23, RUDN, M., 2007, 147–164 | MR | Zbl

[6] A. M. Raigorodskii, “Three lectures on the Borsuk partition problem”, Surveys in Contemporary Mathematics, London Math. Soc. Lecture Note Ser., 347, Cambridge Univ. Press, Cambridge, 2007, 202–247 | MR

[7] F. Dzh. Mak-Vilyams, N. Dzh. A. Sloen, Teoriya kodov, ispravlyayuschikh oshibki, Radio i svyaz, M., 1979 | MR

[8] L. Bassalygo, G. Cohen, G. Zémor, “Codes with forbidden distances”, Selected Topics in Discrete Mathematics (Warsaw, 1996), Discrete Math., 213, 2000, 3–11 | DOI | MR

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

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

[11] K. A. Mikhailov, A. M. Raigorodskii, “O chislakh Ramseya dlya polnykh distantsionnykh grafov s vershinami v $\{0,1\}^n$”, Matem. sb., 200:12 (2009), 63–80 | DOI | MR

[12] M. Koshelev, “Spectrum of Johnson graphs”, Discrete Math., 346:3 (2023), 113262 | DOI | MR

[13] S. Arora, B. Barak, Computational Complexity. A Modern Approach, Cambridge Univ. Press, Cambridge, 2009 | MR

[14] S. P. Vadhan, “Pseudorandomness”, Found. Trends Theor. Comput. Sci., 7:1–3 (2011), 1–336 | DOI | MR

[15] Ya. K. Shubin, “O minimalnom chisle reber v indutsirovannykh podgrafakh spetsialnykh distantsionnykh grafov”, Matem. zametki, 111:6 (2022), 929–939 | DOI

[16] F. A. Pushnyakov, “O kolichestvakh reber v porozhdennykh podgrafakh nekotorykh distantsionnykh grafov”, Matem. zametki, 105:4 (2019), 592–602 | DOI | MR

[17] F. A. Pushnyakov, A. M. Raigorodskii, “Otsenka chisla reber v osobykh podgrafakh nekotorogo distantsionnogo grafa”, Matem. zametki, 107:2 (2020), 286–298 | DOI | MR

[18] F. A. Pushnyakov, A. M. Raigorodskii, “Otsenka chisla reber v podgrafakh grafa Dzhonsona”, Dokl. RAN. Matem., inform., prots. upr., 499 (2021), 40–43 | DOI | MR | Zbl

[19] N. A. Dubinin, “Novye otsenki turanovskogo tipa dlya grafov Dzhonsona”, Probl. peredachi inform., 57:4 (2021), 79–86 | DOI