Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello, given graph $G=(V,E)$ with $n=|V|$ and $k=|E|$, what is the probability that it does not contain any cycle $C_l$ for $l\geq3?$

The requested clarification: My intention was to form the question in such a way, that there is no information about any distribution of the edges, and n and k are parameters. This lack of information should be in fact the information. You construct graphs in any possible ways, and you have to decide which constructs are more possible to occur and which are less expected. This probably implies the uniform distribution.

share|improve this question
5  
You need to specify how you are choosing your random graph, otherwise this isn't a well-posed question. Do you mean over the uniform distribution over all graphs with n vertices and k edges? –  Steve Flammia Mar 2 '11 at 0:44
4  
If $k\ge n$ then the graph is guaranteed to contain a cycle. Steve is right - this question needs work. –  Gerry Myerson Mar 2 '11 at 1:02
    
Usually you specify that given n vertices , you have a protocol to choose edges. For example on each doubleton of vertices I pick an edge with a uniform probability p (it may depend on n or not). If p =1/2 , the probability is rather low anyway. –  Jérôme JEAN-CHARLES Mar 2 '11 at 1:45

2 Answers 2

up vote 20 down vote accepted

I will assume the uniform distribution on all (labelled) graphs with $n$ vertices and $k$ edges. An acyclic graph on $n$ vertices has at most $n-1$ edges, so let me further assume $k< n$. More precisely, $k=n-c$, where $c$ is the number of connected components, i.e., the graph is acyclic iff it is union of $c$ disjoint trees. Now, the number of trees with $m$ vertices is $m^{m-2}$ by Cayley’s formula, hence the requested probability is

$$p_{n,k}=\frac1{(n-k)!\binom{\binom n2}k}\sum_{\substack{n_1+\cdots+n_{n-k}=n\\n_1,\dots,n_{n-k}>0}}\binom n{n_1\,\dots\,n_{n-k}}\prod_{i=1}^{n-k}n_i^{n_i-2}.$$

We have $\binom{\binom n2}k\approx\left(\frac{en^2}{2k}\right)^kk^{-1/2}$ by Stirling’s approximation (where $f\approx g$ means $c_1f\le g\le c_2f$ for some positive constants $c_1,c_2$), hence in the simplest case $k=n-1$,

$$p_{n,n-1}\approx\frac1{\sqrt n}\left(\frac2e\right)^n.$$

share|improve this answer

I will assume what seems the more natural question: uniform probability over all labeled graphs with exactly $k$ edges and $n$ vertices (rather than on isomorphism classes of graphs). The number of labeled forests with $k$ edges on $n$ vertices is the integer sequence http://oeis.org/A138464 which doesn't seem to indicate that a closed form expression is known. To obtain the probability divide this number by (($n$ choose 2) choose $k$).

share|improve this answer
    
Good - but it's not our job to write the question for the OP. Let's hope we get some clarification on what OP wants. –  Gerry Myerson Mar 2 '11 at 12:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.