The thresholds for diameter 2 in random Cayley graphs (Q2925523)

Given a group \(G\), the model \(\mathcal{G}(G,p)\) denotes the probability space of all Cayley graphs of \(G\) with each generator chosen independently with probability \(p\) from \(G\). The authors investigate the properties of graphs \(\Gamma\in \mathcal{G}(G,p)\) for an arbitrary group \(G\), \(|G|=n\rightarrow \infty\). In particular they prove that with high probability the diameter of \(\Gamma\) is at most 2 when \(p\geq \sqrt{(2+\epsilon)\frac{\log{n}}{n}}\) and this result is best possible as with high probability the diameter of \(\Gamma\) is greater than 2 when \(\Gamma\in \mathcal{G}(\mathbb{Z}_2^n,p)\) and \(p\leq \sqrt{(2-\epsilon)\frac{\log{2^n}}{2^n}}\).NEWLINENEWLINENEWLINE They also prove that with high probability the diameter of \(\Gamma\) is greater than 2 when \(p\leq \sqrt{(\frac{1}{4}-\epsilon)\frac{\log{n}}{n}}\) in the case of a general group \(G\) and when \(p\leq \sqrt{(\frac{1}{2}-\epsilon)\frac{\log{n}}{n}}\) in the case of an abelian group \(G\). Also, these results are best possible. Namely, if \(G\) is a cyclic group and \(p\geq \sqrt{(\frac{1}{2}+\epsilon)\frac{\log{n}}{n}}\), then with high probability the diameter of \(\Gamma\) is at most 2. Similarly, if \(0<\epsilon<1/4\), \(G\) has at most \(O(n^{(1+\epsilon)/2})\) involutions, at most \(O(n^{(1+\epsilon)/2})\) elements \(x\) with \(\mathrm{cl}(x)\leq 1/\epsilon\), at most \(O(n^{(1+\epsilon)/4})\) involutions \(x\) with \(\mathrm{cl}(x)\leq 1/\epsilon\) and at most \(\epsilon^2 n/49\) conjugacy classes, then with high probability the diameter of \(\Gamma\) is at most 2, when \(p\geq \sqrt{(\frac{1}{4}+\epsilon)\frac{\log{n}}{n}}\).NEWLINENEWLINENEWLINE The authors consider also the model \(\mathcal{G}(L,p)\), where \(L\) is a Latin square. In this model the set of vertices is \([n]\) and two vertices are adjacent if and only if \(L_{ij}\in S\) or \(L_{ji}\in S\), where the elements of \(S\) are chosen from \([n]\) independently with probability \(p\). The authors prove that in this case with high probability the diameter of \(\Gamma\in \mathcal{G}(L,p)\) is at most 2 when \(p\geq \sqrt{(26+\epsilon)\frac{\log{n}}{n}}\) and with high probability is greater than 2 when \(p\leq \sqrt{(\frac{1}{4}-\epsilon)\frac{\log{n}}{n}}\).