Independence numbers of random subgraphs of distance graphs.

Pyaderkin, M.

We consider the distance graph G( n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erdős-Ko-Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G( n, r, s) in the Erdős-Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G( n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log n) times as large as that of the graph G( n, r, s) itself for r ≤ 2 s 1, while for r > 2 s 1 one has asymptotic stability: the two independence numbers asymptotically coincide.

RANDOM graphs; SUBGRAPHS; DISTANCES; ASYMPTOTIC distribution; GEOMETRIC vertices; EDGES (Geometry)

Mathematical Notes, 2016, Vol 99, Issue 3/4, p556

0001-4346

Academic Journal

10.1134/S0001434616030299