Diameters of random distance graphs (Q1687985)

The theme of this paper is the diameter of a random subgraph of a certain class of disctance graphs. In the class that is considered, the vertices are \(n\)-tuples of 0,1 with \(r_n\) 1s and any two of them are joined by an edge if they have exactly \(s_n\) 1s in common. So when \(s_n=0\), such a graph represents a Kneser graph. Then a random subgraph is considered by retaining each edge independently with probability \(p_n\). The first theorem considers the property that the diameter of this random graph is at most 2. It turns out that there is a critical probability for this property. In fact, this is a sharp threshold. This holds under the assumption that \(r_n \ll n^{1/3}\) and also \(r_n >2s_n\). For \(s_n=r_n/2\) and \(r_n \geq f(n) + f_n\) for a certain function \(f(n)\) that is explicitly given in the paper and \(f_n\to \infty\), they show the existence of such a critical probability for having diameter at most 2. For \(r_n \leq f(n) - f_n\), then no such non-trivial threshold exists. For any \(p_n < c<1\), where \(c\) is a constant, the diameter is with high probability (as \(n\) grows) greater than 2.