Geodesic
Estimate of the Number of Edges in Special Subgraphs of a Distance Graph
Matematičeskie zametki, Tome 107 (2020) no. 2, pp. 286-298.

Voir la notice de l'article provenant de la source Math-Net.Ru

The classical problem of estimating the number of edges in a subgraph of a special distance graph is considered. Old results are significantly improved.
Keywords: extremal combinatorics, Turán theorem. 
@article{MZM_2020_107_2_a10,
     author = {Ph. A. Pushnyakov and A. M. Raigorodskii},
     title = {Estimate of the {Number} of {Edges} in {Special} {Subgraphs} of a {Distance} {Graph}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {286--298},
     publisher = {mathdoc},
     volume = {107},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2020_107_2_a10/}
}
TY  - JOUR
AU  - Ph. A. Pushnyakov
AU  - A. M. Raigorodskii
TI  - Estimate of the Number of Edges in Special Subgraphs of a Distance Graph
JO  - Matematičeskie zametki
PY  - 2020
SP  - 286
EP  - 298
VL  - 107
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2020_107_2_a10/
LA  - ru
ID  - MZM_2020_107_2_a10
ER  - 
%0 Journal Article
%A Ph. A. Pushnyakov
%A A. M. Raigorodskii
%T Estimate of the Number of Edges in Special Subgraphs of a Distance Graph
%J Matematičeskie zametki
%D 2020
%P 286-298
%V 107
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2020_107_2_a10/
%G ru
%F MZM_2020_107_2_a10
Ph. A. Pushnyakov; A. M. Raigorodskii. Estimate of the Number of Edges in Special Subgraphs of a Distance Graph. Matematičeskie zametki, Tome 107 (2020) no. 2, pp. 286-298. http://geodesic.mathdoc.fr/item/MZM_2020_107_2_a10/

[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, “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 (337) (2001), 107–146 | DOI | MR | Zbl

[4] A. M. Raigorodskii, “O khromaticheskikh chislakh sfer v evklidovykh prostranstvakh”, Dokl. AN, 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. V. Kostochka, A. M. 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. AN, 457:4 (2014), 383–387 | DOI | 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 | MR | Zbl

[9] L. I. Bogolyubskii, A. M. Raigorodskii, “Zamechanie o nizhnikh otsenkakh khromaticheskikh chisel prostranstv maloi razmernosti s metrikami $\ell_1$ i $\ell_2$”, Matem. zametki, 105:2 (2019), 187–213 | DOI

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

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

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

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

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

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

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

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

[18] A. A. Sagdeev, A. M. Raigorodskii, “O khromaticheskom chisle prostranstva s zapreschennym pravilnym simpleksom”, Dokl. AN, 472:2 (2017), 127–129 | MR | Zbl

[19] A. M. Raigorodskii, A. A. Sagdeev, “Ob odnoi otsenke v ekstremalnoi kombinatorike”, Dokl. AN, 478:3 (2018), 271–273 | DOI | Zbl

[20] A. M. Raigorodskii, A. A. Sagdeev, “On a Frankl–Wilson theorem and its geometric corollaries”, Acta Math. Univ. Comenianae, 88:3 (2019), 1029–1033 http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1216/758

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

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

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

[24] A. A. Sagdeev, “O kolichestve nenulevykh kubicheskikh summ”, Algebra i teoriya chisel. 1, Zap. nauchn. sem. POMI, 469, POMI, SPb., 2018, 160–174

[25] D. A. Zakharov, A. M. Raigorodskii, “Kliko-khromaticheskie chisla grafov peresechenii”, Matem. zametki, 105:1 (2019), 142–144 | DOI | Zbl

[26] A. M. Raigorodskii, T. V. Trukhan, “O khromaticheskikh chislakh nekotorykh distantsionnykh grafov”, Dokl. AN, 482:6 (2018), 648–650 | DOI

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

[28] L. E. Shabanov, A. M. Raigorodskii, “Turán type results for distance graphs”, Discrete Comput. Geom., 56:3 (2016), 814–832 | DOI | MR | Zbl

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

[30] M. Tikhomirov, “O zadache proverki distantsionnoi i multidistantsionnoi vlozhimosti grafa”, Dokl. AN, 468:3 (2016), 261–263 | MR | Zbl

[31] M. Tikhomirov, “On complexity of multidistance graph recognition in $\mathbb R^1$”, Electron. Notes Discrete Math., 61 (2017), 1039–1045 | DOI | Zbl

[32] N. Frankl, A. Kupavskii, K. J. Swanepoel, “Embedding graphs in Euclidean space”, Electron. Notes Discrete Math., 61 (2017), 475–481 | DOI | Zbl

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

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

[35] A. V. Bobu, A. E. Kupriyanov, “Uluchshenie nizhnikh otsenok khromaticheskogo chisla prostranstva s zapreschennymi odnotsvetnymi treugolnikami”, Matem. zametki, 105:3 (2019), 349–363 | DOI | Zbl

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

[37] J. Balogh, D. Cherkashin, S. Kiselev, “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, European J. Combin., 79 (2019), 228–236 | DOI | MR | Zbl

[38] A. M. Raigorodskii, “Ob ustoichivosti chisla nezavisimosti sluchainogo podgrafa”, Dokl. AN, 477:6 (2017), 649–651 | DOI | Zbl

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

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

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

[42] R. I. Prosanov, “Kontrprimery k gipoteze Borsuka, imeyuschie bolshoi obkhvat”, Matem. zametki, 105:6 (2019), 890–898 | DOI | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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