The range of thresholds for diameter 2 in random Cayley graphs

DOI10.1016/J.EJC.2013.06.030MaRDI QIDQ2509744zbMATH OpenOpenAlexFDO

Authors Demetres Christofides, Klas Markström

Publication date 29 July 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

probability space

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: Given a group G, the model mathcal{G}(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. Given a family of groups (G_k) and a c in mathbb{R}_+ we say that c is the threshold for diameter 2 for (G_k) if for any varepsilon > 0 with high probability Gamma in mathcal{G}(G_k,p) has diameter greater than 2 if p leqslant sqrt{(c - eps)frac{log{n}}{n}} and diameter at most 2 if p geqslant sqrt{(c + eps)frac{log{n}}{n}}. In [5] we proved that if c is a threshold for diameter 2 for a family of groups (G_k) then c in [1/4,2] and provided two families of groups with thresholds 1/4 and 2 respectively. In this paper we study the question of whether every c in [1/4,2] is the threshold for diameter 2 for some family of groups. Rather surprisingly it turns out that the answer to this question is negative. We show that every c in [1/4,4/3] is a threshold but a c in (4/3,2] is a threshold if and only if it is of the form 4n/(3n-1) for some positive integer n.

Recommendations

• The thresholds for diameter 2 in random Cayley graphs
• Random Cayley digraphs of diameter 2 and given degree
• The diameters of almost all Cayley digraphs
• The diameter of a random Cayley graph of \({\mathbb{Z}}_q\)
• Diameters of random Cayley graphs of finite nilpotent groups

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 3314393 (Why is no real title available?)
• Random Cayley digraphs of diameter 2 and given degree
• Random graphs.
• Random Latin square graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The probability that a pair of elements of a finite group are conjugate.
• The thresholds for diameter 2 in random Cayley graphs
• What is the probability that two elements of a finite group commute?
• What is the Probability that Two Group Elements Commute?

Cited in

(4)

• Diameters of random Cayley graphs of finite nilpotent groups
• The thresholds for diameter 2 in random Cayley graphs
• The diameters of almost all bi-Cayley graphs
• Cutoff for a stratified random walk on the hypercube

This page was built for publication: The range of 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 Q2509744)