4
$\begingroup$

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.

$\endgroup$
3
  • 5
    $\begingroup$ 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? $\endgroup$ Mar 2, 2011 at 0:44
  • 4
    $\begingroup$ If $k\ge n$ then the graph is guaranteed to contain a cycle. Steve is right - this question needs work. $\endgroup$ Mar 2, 2011 at 1:02
  • $\begingroup$ 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. $\endgroup$ Mar 2, 2011 at 1:45

2 Answers 2

19
$\begingroup$

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.$$

$\endgroup$
5
$\begingroup$

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$).

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 2, 2011 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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