2
$\begingroup$

Suppose I have a random 3 regular graph - there are many results about the expected number of cycles of given length in such a graph, and also about things like the probability that any two cycles of given length will intersect (the best resource I know of is a paper of McKay, Wormold and Wysocka, plus of course Bollobas). My question is the following - if I randomly choose an edge $e$, what is the expected number of cycles of some given length containing that edge? I guess the best way to formulate this might be to consider the set consisting of the number of (simple) cycles each edge is on, and ask is it known what the distribution of those numbers is?

Thanks

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The expected number of $k$-cycles can be calculated using the pairing (configuration) model and one of the references in the paper you mention will explain it. It has been calculated lots of times but I can't recall any of the places it is explicitly stated. The expected number of $k$-cycles using a random edge is $k/(3n/2)$ times the expected number of $k$-cycles altogether, by symmetry. The same approach will handle subgraphs other than cycles, for example a subgraph formed by two overlapping cycles. If you want the distribution (not just the expectation) of the number of $k$-cycles using an edge it gets trickier. You can get it (a Poisson distribution) for bounded $k$ by the pairing model. For slightly larger $k$, the switching method used in the paper you mention will also give a Poisson distribution. For quite a bit larger $k$ the methods of Garmo should work and the distribution will be more complicated. For very large cycles, it could be difficult. Sorry this answer is vague; I don't know where anyone has set this all out in a form you can just reference.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks so much, I have been trying to put this together, and didn't know of Garmo's work, I will check it out. I know about the Poisson distribution, I'm just having trouble working out how it works if you start with an edge first. FYI, I cited your paper mentioned above in my paper with Makover, we use graphs to get results about geodesics on Riemann surfaces. What I'm thinking of now is the following, which might make it clearer what I'm looking for - if I have a 3 regular graph, and I cut edges until I get a spanning tree, that corresponds to a fundamental domain on the surface $\endgroup$
    – Jeff McGowan
    Commented May 10, 2012 at 14:57
  • $\begingroup$ The edges of that domain are identified in pairs based on the edges which were cut, and the cycles joining those paired edges correspond to elements of the homology basis. So if an edge is on very few (short) cycles then that basis element will not intersect many other basis elements. Not sure if that makes any sense. I should add that Makover and I thought the paper of yours mentioned above was great, and we were able to use your techniques to get results where we allowed cycles to intersect once. $\endgroup$
    – Jeff McGowan
    Commented May 10, 2012 at 15:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .