MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is uniformly chosen over all such sets.)

Associated to the random forest $F$ are marginals $\{p_e:e \in E\}$, where $p_e = \mathbb{P}(e \in E')$. Now let $E^*$ be a random subset of $E$, chosen by independently including each edge $e \in E$ with probability $p_e$.

Finally, let $N$ be the (random) smallest number of spanning trees of $G$ whose union contains $E^*$.

What is known about the distribution of $N$? How does $\sup_{G} \mathbb{E}(N)$, the largest expected value of $N$ over all $n$-vertex graphs, grow? Is it $O(\log n)$? Is it $O(1)$?

Edit: is it $O(\sqrt{\log n})$? Fedor has a nice example showing that it is not $O(1)$. I believe optimizing Fedor's example yields a lower bound of order $(\log n/\log\log n)^{1/2}$.

Note: the question also makes sense if $E'$ is the edge set of a uniformly random spanning tree, and Fedor's example applies in either case.

share|cite|improve this question

It is not $O(1)$ for sure. Take isomorphic (say, to $K_m$) disjoint graphs $G_1$, $G_2$, $\dots$, $G_N$ and draw one edge between $G_i$ and $G_{i+1}$, $i=1,2,\dots,N$. Then frequencies of edges of $G_i$ are the same and depend only on $m$, so each $G_i$ is chosen as whole with some probability depending only in $m$, These events are independent, so for large $N$ with high probability at least one of them holds. But for covering $K_m$ by trees you need at least $m/2$ trees.

And it looks probbale that it is $O(\log n)$ or even $O(\sqrt{\log n})$ or smth like this. Indeed, what does it mean that we can not cover graph by $K$ trees? That for some set $A$ of some $m$ vertices the graph has at least $K(m-1)$ edges between vertices of $A$. Fix $A$ and estimate the probability of this unlucky event. We have sum of independent variavles, and some of their expectations is nothing but the average number of edges covered by random spanning tree in $A$. So, at most $m-1$ for sure. Even if it we increase some probabilities so that it becomes $m-1$, dispersion is about $m$ too, so the probability of our event is estimated by some $\exp(-cK^2m)$ for some $c>0$ (I am not sure in this point, but this must be very standard weak version of CLT). If $e^{K^2}\gg n$, then even if multiply this by number of $m$-subsets of $V$, and then sum up by $n$, we get some infinitesimal.

share|cite|improve this answer
Fedor, thanks for this answer! I believe that the argument in your second paragraph is close to correct, except that your probability estimate is a little too strong. A binomial event of this form will have Poisson rather than Gaussian tails (so tails of the form $exp(−c(K\log K)m) when K is somewhat large). So I think this argument can show an upper bound of $O(logn/loglogn)$. – Louigi Addario-Berry Nov 11 '10 at 21:01

Consider the path P of length n. Now replace every edge by n parallel edges. A random tree has $p_e=1/n$ and $p_e=1/(n+1)$ in a random forest for each edge $e$. Now, consider the set E^*. There is a constant probability that $\Omega(\frac{\log n}{\log \log n})$ copies of some parallel edge will show up. Therefore, the expectation of $N$ will be $\Omega(\frac{\log n}{\log \log n})$. Am I missing anything here?

I believe the upperbound will be the same as well.

share|cite|improve this answer

Your Answer


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.