Return to Question

2 Added to the question in light of a first response.

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 Is it $O(1)$?

Edit: is it $O(\sqrt{\log n})$? Fedor has a nice example showing that it is not $O(1)$. I expect this may be well-understoodbelieve 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, but not by meand Fedor's example applies in either case.

1

Covering a random graph with spanning trees.

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

I expect this may be well-understood, but not by me.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 44, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9270102381706238, "perplexity_flag": "head"}