The Number of Edges in Induced Subgraphs of Some Distance Graphs

Ph. A. Pushnyakov

Matematičeskie zametki, Tome 105 (2019) no. 4, pp. 592-602.

Résumé

We obtain new estimates for the number of edges in induced subgraphs of some distance graph.

Détail

Keywords: distance graph, Turán's theorem.

Bibliographie

[1] 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 | DOI | MR | Zbl

[2] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1 (337) (2001), 107–146 | DOI | MR | Zbl

[3] J. Pach, P. K. Agarwal, Combinatorial Geometry, John Wiley Sons, New York, 1995 | DOI | MR | Zbl

[4] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and His Mathematics, II, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002, 649–666 | MR | Zbl

[5] A. Soifer, The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of Its Creators, Springer, New York, 2009 | MR | Zbl

[6] V. Klee, S. Wagon, Old and New Unsolved Problems in Plane Geometry and Number Theory, Dolciani Math. Expos., 11, Math. Assoc. Amer., Washington, DC, 1991 | MR | Zbl

[7] M. M. Pyadërkin, “Chisla nezavisimosti sluchainykh podgrafov nekotorogo distantsionnogo grafa”, Matem. zametki, 99:2 (2016), 288–297 | DOI | MR | Zbl

[8] D. D. Cherkashin, A. M. Raigorodskii, “O khromaticheskikh chislakh prostranstv maloi razmernosti”, Dokl. AN, 472:1 (2017), 11–12 | MR | Zbl

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

[10] L. E. Shabanov, A. M. Raigorodskii, “Turanovskie otsenki dlya distantsionnykh grafov”, Dokl. AN, 475:3 (2017), 254–256 | MR | Zbl

[11] L. E. Shabanov, “Turanovskie otsenki dlya distantsionnykh grafov v tonkoi sloike”, Kombinatorika i teoriya grafov. IX, Zap. nauchn. sem. POMI, 464, POMI, SPb., 2017, 132–168

[12] 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 | MR | Zbl

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

[14] A. Ya. Kanel-Belov, V. A. Voronov, D. D. Cherkashin, “O khromaticheskom chisle ploskosti”, Algebra i analiz, 29:5 (2017), 68–89 | MR

[15] S. G. Kiselev, A. M. Raigorodskii, “O khromaticheskom chisle sluchainogo podgrafa knezerovskogo grafa”, Dokl. AN, 476:4 (2017), 375–376 | MR | Zbl

[16] V. G. Boltyanski, H. Martini, P. S. Soltan,, Excursions into Combinatorial Geometry, Springer, Berlin, 1997 | DOI | MR | Zbl

[17] 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, 2008, 202–247 | MR | Zbl

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

[19] R. Graham, B. Rothschild, J. Spencer, Ramsey Theory, John Wiley Sons, Inc., New York, 1990 | MR | Zbl

[20] A. A. Sagdeev, “O khromaticheskikh chislakh, sootvetstvuyuschikh eksponentsialno ramseevskim mnozhestvam”, Zap. nauchn. sem. POMI, 475, POMI, SPb., 2018, 174–189

[21] A. A. Sagdeev, “Eksponentsialno ramseevskie mnozhestva”, Probl. peredachi inform., 54:4 (2018), 82–109

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

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

[24] L. Bassalygo, G. Cohen, G. Zémor, “Codes with forbidden distances”, Discrete Math., 213:1-3 (2000), 3–11 | DOI | MR | Zbl

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

[26] F. A. Pushnyakov, “O chisle reber v indutsirovannykh podgrafakh spetsialnogo distantsionnogo grafa”, Matem. zametki, 99:4 (2016), 550–558 | DOI | MR | Zbl

[27] F. A. Pushnyakov, “Novaya otsenka chisla reber v indutsirovannykh podgrafakh spetsialnogo distantsionnogo grafa”, Probl. peredachi inform., 51:4 (2015), 71–77 | Zbl

[28] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “O khromaticheskikh chislakh distantsionnykh grafov, blizkikh k knezerovskim”, Dokl. AN, 468:3 (2016), 247–250 | MR | Zbl

[29] A. A. Sagdeev, “O teoreme Frankla–Redla”, Izv. RAN. Ser. matem., 82:6 (2018), 128–157 | DOI | Zbl

[30] A. A. Sagdeev, “Uluchshennaya teorema Frankla–Redlya i nekotorye ee geometricheskie sledstviya”, Probl. peredachi inform., 54:2 (2018), 45–72

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