On Covering of Random Tori by Maximal Subsquares
by
M. Nehéz
Bratislava
Coauthors: I. Dandul (Olomouc)

Covering problems are among the most studied topics in the graph theory. Lots of problems (concerning e. g. the design of Boolean functions) can be mapped onto the covering problems. In our contribution we deal with the covering of random tori by maximal subsquares. For a 2-dimensional torus T_{n ×n} of n² vertices we define the probabilistic space G (T_{n ×n}, p) of all random tori in which the occurrence of an edge (independently) is given by the probability p (0 < p < 1). For a given random torus T in G(T_{n ×n}, p) we study the number and sizes of maximal subsquares occurring in T. As a main result we estimate the bounds for complexity of covering the random torus by maximal subsquares. Given a graph G, let C_S(G) denote the complexity of covering the graph G by maximal subsquares. We show that for any random torus T in G (T_{n ×n}, p) the asymptotic equality C_S(T) = \Theta(n²) holds with a very high probability. (The lower and upper bounds are determined more precisely.)
We also mention the consequence for älmost all" random tori. We show that the following inequalities

0.7854 < CS(T)/n2 < 0.8472

hold with the probability tending to 1 as n --> \infty.

Date received: May 26, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafd-07.