The thresholds for diameter 2 in random Cayley graphs

Details The thresholds for diameter 2 in random Cayley graphs The thresholds for diameter 2 in random Cayley graphs

2011-08-17

arxiv.org/abs/1108.3547v1

Mathematics

Combinatorics

Scientific paper

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. 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 \to \infty$, a graph $\Gamma_k \in \mathcal{G}(G_k,p)$ with high probability has diameter at most 2 if $p \geqslant \sqrt{(2 + \epsilon) \frac{\log{n_k}}{n_k}}$ and with high probability has diameter greater than 2 if $p \leqslant \sqrt{(1/4 + \epsilon)\frac{\log{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 Erd\H{o}s-Renyi random graphs.

Affiliated with

Also associated with

No associations

Rating

The thresholds for diameter 2 in random Cayley graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The thresholds for diameter 2 in random Cayley graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The thresholds for diameter 2 in random Cayley graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-541350