Large cycles in random generalized Johnson graphs (Q2065901)

Given integers \(0 \leq s < r \leq n\), the generalised Johnson graph \(G(n,r,s)\) is the graph whose vertices are the \(r\)-subsets of \(\{1,\dots, n\}\) and two of them are connected by an edge if and only if the size of their intersection is exactly \(s\). This definition generalises the well-known Johnson graphs (when \(s = r-1\)) and Kneser graphs (when \(s = 0\)). For fixed \(r\), \(s\) and \(n\) tending to infinity, and given \(p = p(n) \in (0,1)\), the authors consider \(G_p(n,r,s)\), which is a random subgraph of \(G(n,r,s)\) obtained by keeping every edge independently with probability \(p\). The authors study properties which hold with high probability, meaning that the probability that \(G_p(n,r,s)\) satisfies the property tends to 1 as \(n\) tends to infinity. The specific object of study is the presence of long cycles in \(G_p(n,r,s)\). Note that generalised Johnson graphs are vertex-regular, let \(N_1\) be the degree of \(G(n,r,s)\). Suppose \(r\), \(s\) are fixed and \(n\) tends to infinity. The main result of the paper shows that for every sequence \(t = t(n) = o(\sqrt{N_1})\), the subgraph \(G_p(n,r,s)\) contains the cycle \(C_t\) on \(t\) vertices with high probability, as long as \(p \gg n^{s/t}/N_1\). Also, \(G_p(n,r,s)\) does not contain any \(C_t\) with high probablity whenever \(p \ll n^{s/t}/N_1\). Moreover, under extra conditions (\(s = 0\) together with \(t \rightarrow \infty\); or \(t = \omega(\ln n)\)) they find the ``sharp probability threshold'' for the property of containing a \(C_t\), which is a more specific property. The proofs proceed via applications of the first and second moment methods.