The thresholds for diameter 2 in random Cayley graphs

DOI10.1002/RSA.20486MaRDI QIDQ2925523zbMATH OpenOpenAlexFDO

Authors Demetres Christofides, Klas Markström

Publication date 16 October 2014

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.3547

zbMATH Keywords

Cayley graphsdiameterrandom graphs

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Given a group G, the model $mathcalG(G,p)$ denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. In this article we show that for any $epsilon>0$ and any family of groups G_k of order n_k for which $n_{k}oinfty$, a graph $Gamm{a}_{k}inmathcalG(G_k,p)$ with high probability has diameter at most 2 if $pgeqslantsqrt(2+epsilon)fraclog{n}_k{n}_k$ and with high probability has diameter greater than 2 if $pleqslantsqrt(1/4+epsilon)fraclog{n}_k{n}_k$. We also provide examples of families of graphs which show that both of these results are best possible. Of particular interest is that for some families of groups, the corresponding random Cayley graphs achieve diameter 2 significantly faster than the ErdH{o}s-Renyi random graphs.

Review text

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}}\).

Recommendations

• The range of thresholds for diameter 2 in random Cayley graphs
• Random Cayley digraphs of diameter 2 and given degree
• The diameter of a random Cayley graph of \({\mathbb{Z}}_q\)
• The diameters of almost all Cayley digraphs
• On the Diameter of Random Cayley Graphs of the Symmetric Group

Cites work

• On the asymmetry of random regular graphs and random graphs
• Random Latin square graphs
• Sandwiching random graphs: universality between random graph models
• The range of thresholds for diameter 2 in random Cayley graphs

Cited in

(13)

• The diameters of almost all Cayley digraphs
• Almost all Cayley graphs have diameter 2
• Diameters of random Cayley graphs of finite nilpotent groups
• The range of thresholds for diameter 2 in random Cayley graphs
• Random Latin square graphs
• The diameters of almost all bi-Cayley graphs
• On the girth of random Cayley graphs
• The diameter of a random Cayley graph of \({\mathbb{Z}}_q\)
• Girth, words and diameter
• Optimal threshold for a random graph to be 2-universal
• Random Cayley digraphs of diameter 2 and given degree
• Geometry of random Cayley graphs of abelian groups
• Resistance diameters and critical probabilities of Cayley graphs on irreducible complex reflection groups

This page was built for publication: The thresholds for diameter 2 in random Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2925523)