On Cycles in Random Graphs

Details On Cycles in Random Graphs On Cycles in Random Graphs

2010-09-30

arxiv.org/abs/1009.6046v1

Mathematics

Combinatorics

17 pages, 4 figures

Scientific paper

We consider the geometric random (GR) graph on the $d-$dimensional torus with the $L_\sigma$ distance measure ($1 \leq \sigma \leq \infty$). Our main result is an exact characterization of the probability that a particular labeled cycle exists in this random graph. For $\sigma = 2$ and $\sigma = \infty$, we use this characterization to derive a series which evaluates to the cycle probability. We thus obtain an exact formula for the expected number of Hamilton cycles in the random graph (when $\sigma = \infty$ and $\sigma = 2$). We also consider the adjacency matrix of the random graph and derive a recurrence relation for the expected values of the elementary symmetric functions evaluated on the eigenvalues (and thus the determinant) of the adjacency matrix, and a recurrence relation for the expected value of the permanent of the adjacency matrix. The cycle probability features prominently in these recurrence relations. We calculate these quantities for geometric random graphs (in the $\sigma = 2$ and $\sigma = \infty$ case) with up to $20$ vertices, and compare them with the corresponding quantities for the Erd\"{o}s-R\'{e}nyi (ER) random graph with the same edge probabilities. The calculations indicate that the threshold for rapid growth in the number of Hamilton cycles (as well as that for rapid growth in the permanent of the adjacency matrix) in the GR graph is lower than in the ER graph. However, as the number of vertices $n$ increases, the difference between the GR and ER thresholds reduces, and in both cases, the threshold $\sim \log(n)/n$. Also, we observe that the expected determinant can take very large values. This throws some light on the question of the maximal determinant of symmetric $0/1$ matrices.

Affiliated with

Also associated with

No associations

Rating

On Cycles in Random 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 On Cycles in Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Cycles in Random Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-242578