ON GEOMETRICAL PROPERTIES OF RANDOM TORI AND RANDOM GRAPH MODELS

Martin Nehéz

   In this paper we prove that for a given random d-dimensional torus T of order n^d, the upper bound on the size r of the largest d-dimensional grid that is asymptotically almost surely contained in T is O([log n]^1/d). To prove this result we use both probabilistic and Kolmogorov complexity arguments. Possible applications are indicated.

Keywords: torus, grid, random graph, Kolmogorov complexity

[full-paper]