Covering a random graph with spanning trees.

Question

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.

Answer 1

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.

Answer 2

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.