## We found a match

Your institution may have access to this item. Find your institution then sign in to continue.

- Title
# Independence numbers of random subgraphs of distance graphs.

- Authors
## Pyaderkin, M.

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

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

- Publication
## Mathematical Notes, 2016, Vol 99, Issue 3/4, p556

- ISSN
## 0001-4346

- Publication type
## Academic Journal

- DOI
## 10.1134/S0001434616030299