On the Number of Edges in Induced Subgraphs of a Special Distance Graph

Ph. Pushnyakov

Matematičeskie zametki, Tome 99 (2016) no. 4, pp. 550-558.

Résumé

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

Détail

Keywords: distance graph, cycle, coloring, Borsuk problem.
Mots-clés : clique

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 | MR

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

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

[4] A. M. Raigorodskii, “O khromaticheskikh chislakh sfer v evklidovykh prostranstvakh”, Dokl. RAN, 432:2 (2010), 174–177 | MR | Zbl

[5] A. M. Raigorodskii, “On the chromatic numbers of spheres in ${\mathbb R}^n$”, Combinatorica, 32:1 (2012), 111–123 | DOI | MR | Zbl

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

[7] L. I. Bogolyubskii, A S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Chisla nezavisimosti i khromaticheskie chisla sluchainykh podgrafov v nekotorykh posledovatelnostyakh grafov”, Dokl. RAN, 457:4 (2014), 383–387 | DOI | MR | Zbl

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

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

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

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

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

[13] V. Boltyanski, H. Martini, P. S. Soltan, Excursions into Combinatorial Geometry, Universitext, Springer-Verlag, Berlin, 1997 | MR | Zbl

[14] 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–248 | MR | Zbl

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

[16] R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey Theory, John Wiley and Sons, New York, 1990 | MR | Zbl

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

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

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

[20] E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distantsionnye grafy, imeyuschie bolshoe khromaticheskoe chislo i ne soderzhaschie klik ili tsiklov zadannogo razmera”, Matem. sb., 204:4 (2013), 49–78 | DOI | MR | Zbl

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