Independence Numbers of Random Subgraphs of Distance Graphs

M. M. Pyaderkin

Matematičeskie zametki, Tome 99 (2016) no. 4, pp. 564-573

Résumé

We consider the distance graph $G(n,r,s)$, whose vertices can be identified with $r$-element subsets of the set $\{1,2,\dots,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 $\Theta(\log_2n)$ times as large as that of the graph $G(n,r,s)$ itself for $r \le 2s+1$, while for $r > 2s+1$ one has asymptotic stability: the two independence numbers asymptotically coincide.

Détail

Keywords: distance graph, random subgraph, independence number, Erdős–Ko–Rado problem, Erdős–Rényi model.