On the Realization of Subgraphs of a Random Graph by Diameter Graphs in Euclidean Spaces

A. A. Kokotkin^a, A. M. Raigorodskii<sup>ab

a</sup> Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
^b Lomonosov Moscow State University

Abstract: 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.

UDC: 519.174

Received: 25.05.2014
Revised: 26.10.2014

DOI: 10.4213/mzm10559

 English version: Mathematical Notes, 2015, 97:5, 709–724

Bibliographic databases:

• 
• 
• 
•