Geodesic
On the Realization of Subgraphs of a Random Graph by Diameter Graphs in Euclidean Spaces
Matematičeskie zametki, Tome 97 (2015) no. 5, pp. 699-717.

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

The present paper is motivated by Borsuk's classical problem of the partition of sets in spaces into parts of smaller diameter. We obtain sharp estimates for the maximal number of vertices of the induced subgraph of a random graph that, with high probability, is isomorphic to the diameter graph with given chromatic number in a space of any fixed dimension.
Keywords: random graph, diameter graph, Euclidean space, Borsuk problem, chromatic number, independence number. 
@article{MZM_2015_97_5_a5,
     author = {A. A. Kokotkin and A. M. Raigorodskii},
     title = {On the {Realization} of {Subgraphs} of a {Random} {Graph} by {Diameter} {Graphs} in {Euclidean} {Spaces}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {699--717},
     publisher = {mathdoc},
     volume = {97},
     number = {5},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2015_97_5_a5/}
}
TY  - JOUR
AU  - A. A. Kokotkin
AU  - A. M. Raigorodskii
TI  - On the Realization of Subgraphs of a Random Graph by Diameter Graphs in Euclidean Spaces
JO  - Matematičeskie zametki
PY  - 2015
SP  - 699
EP  - 717
VL  - 97
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2015_97_5_a5/
LA  - ru
ID  - MZM_2015_97_5_a5
ER  - 
%0 Journal Article
%A A. A. Kokotkin
%A A. M. Raigorodskii
%T On the Realization of Subgraphs of a Random Graph by Diameter Graphs in Euclidean Spaces
%J Matematičeskie zametki
%D 2015
%P 699-717
%V 97
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2015_97_5_a5/
%G ru
%F MZM_2015_97_5_a5
A. A. Kokotkin; A. M. Raigorodskii. On the Realization of Subgraphs of a Random Graph by Diameter Graphs in Euclidean Spaces. Matematičeskie zametki, Tome 97 (2015) no. 5, pp. 699-717. http://geodesic.mathdoc.fr/item/MZM_2015_97_5_a5/

[1] K. Borsuk, “Drei Sätze über die $n$-dimensionale euklidische Sphäre”, Fundam. Math., 20 (1933), 177–190 | Zbl

[2] A. M. Raigorodskii, “O razmernosti v probleme Borsuka”, UMN, 52:6 (1997), 181–182 | DOI | MR | Zbl

[3] A. M. Raigorodskii, “Ob odnoi otsenke v probleme Borsuka”, UMN, 54:2 (1999), 185–186 | DOI | MR | Zbl

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

[5] A. M. Raigorodskii, “Kontrprimery k gipoteze Borsuka na sferakh malogo radiusa”, Dokl. RAN, 434:2 (2010), 161–163 | MR | Zbl

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

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

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

[9] J. Matoušek, Using the Borsuk–Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer-Verlag, Berlin, 2003 | MR | Zbl

[10] B. Bollobás, Random Graphs, Cambridge Stud. Adv. Math., 73, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[11] A. A. Kokotkin, A. M. Raigorodskii, “O realizatsii sluchainykh grafov grafami diametrov”, Tr. MFTI, 4:1 (2012), 19–28

[12] A. A. Kokotkin, A. M. Raigorodskii, “O realizatsii podgrafov sluchainogo grafa grafami diametrov na poluosi i v prostranstve”, Tr. MFTI, 6:2 (2014), 44–60

[13] A. M. Raigorodskii, “Problema Nelsona–Erdesha–Khadvigera i realizatsiya sluchainogo grafa v prostranstve”, UMN, 61:4(370) (2006), 195–196 | DOI | MR | Zbl

[14] S. V. Nagaeva, A. M. Raigorodskii, “O vlozhimosti konechnykh grafov rasstoyanii s bolshim khromaticheskim chislom v sluchainye grafy”, Itogi nauki i tekhn. Ser.Sovrem. matem., 62, 2009, 47–66

[15] S. V. Nagaeva, A. M. Raigorodskii, “O realizatsii sluchainykh grafov grafami rasstoyanii v prostranstvakh fiksirovannoi razmernosti”, Dokl. RAN, 424:3 (2009), 315–317 | MR | Zbl

[16] A. B. Kupavskii, A. M. Raigorodskii, M. V. Titova, “New bounds for the distance Ramsey number”, Discrete Math., 313:22 (2013), 2566–2574 | DOI | MR | Zbl

[17] D. Achlioptas, A. Naor, “The two possible values of the chromatic number of a random graph”, Ann. of Math. (2), 162:3 (2005), 1335–1351 | DOI | MR | Zbl

[18] V. Rödl, “On a packing and covering problem”, Eur. J. Combin., 6:1 (1985), 69–78 | DOI | MR | Zbl

[19] N. Alon, J. H. Spencer, The Probabilistic Method, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley and Sons, New York, 2000 | MR | Zbl

[20] H. J. Prömel, A. Steger, “On the asymptotic structure of sparse triangle free graphs”, J. Graph Theory, 21:2 (1996), 137–151 | 3.0.CO;2-S class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[21] N. N. Kuzjurin, “On the difference between asymptotically good packings and coverings”, Eur. J. Combin., 16:1 (1995), 35–40 | DOI | MR | Zbl