94 problems

Asymptotic ratio conjecture. The limit exists:

Let $\hat{\mathcal{G}}_{2n+1}$ be the graph whose components $A$ have labeled edges, and let $\eta$ be a label of a component $A$. A component spanning tree of $A$ is a spanning tr…

For $3\leq k\leq 6$, let $\mathcal{X}_{n,k,g}$ be the class of graphs considered in the source and define … where $g$ is fixed sufficiently large and $\tau(G)$ is the number of spa…

Let $G$ be a simple graph, and let $\tau(G)$ denote its number of spanning trees. A $k$-regular graph of girth $g$ with the minimum possible number of vertices is called a $(k,g)$-…

Let $G$ be the infinite nearest-neighbor graph on the integer lattice in $d$ dimensions, and let ${\bf T}$ be the uniform spanning forest obtained as a distributional limit of unif…

Let $G$ be a finite connected graph, let ${\bf T}$ be a uniform spanning tree, let $e$ be an edge, and let $A$ be an up-event, meaning an upwardly closed event in the space of subg…

Asymptotic growth constant conjecture. The asymptotic growth constant is

Spanning-tree factorization conjecture. The number of spanning trees is

Let $Q_n$ be the $n$-dimensional hypercube and let $F_{n+1}$ be the dual-cube of dimension $n+1$. Let $k$ be a positive integer. Dual-cube lifting conjecture. If $Q_n$ has $k$ comp…

Periodic perfect-power maximality conjecture. Its spanning-tree count is at most

Perfect-power square-maximality conjecture. Equality should occur only for the $d$-dimensional box $P_n^{\square d}$, up to lattice translation and coordinate permutation.

Higher-outerplanarity obstruction conjecture. For any $k\geq 4$, there exists a 3-connected $k$-outerplanar triangulated disc with no completely independent spanning trees.

Let $k$ and $c$ be integers with $0\le c\le k-1$. For $0\le c\le k-2$, let $\mathcal{H}_1(n,k,c)$ be the class of all $(k+c)$-edge-connected graphs $H$ of order $n$ for which there…

Non-isomorphic spanning-tree lower-bound conjecture. The number of non-isomorphic spanning trees of $G$ is at least

Sharp anticoncentration conjecture. For every tree $T$,

Lee's conjecture. For every tree $T$,

Let $\mathcal{RS}_n$ be the rainbow-spanning-tree game played on $n-1$ copies of $K_n$, where Maker wins by claiming a rainbow spanning tree, and let $b_{\mathcal{RS}_n}$ denote it…

Let $q$ be a prime power and let $n=q^2+q+1$. For an $n$-vertex $C_4$-free graph $G$, write $\tau(G)$ for its number of spanning trees, and let $\mathrm{st}(n,C_4)$ denote the maxi…

Perturbation conjecture. For every $\epsilon>0$, there is a set $S'=\{p'_1,p'_2,\ldots,p'_n\}$ in bijective correspondence with $S$ such that each corresponding pair satisfies…

Let $n,d\geq 3$ be integers, and let $G$ be a connected $n$-vertex $d$-regular graph. Write $T_{\mathrm{unlabeled}}(G)$ for the set of isomorphism classes of spanning trees of $G$.…

Let $\mathcal{T}(n)$ denote the set of values of the spanning-tree count $\tau(G)$ over unrestricted graphs on $n$ vertices. Cayley's theorem gives $\tau(K_n)=n^{n-2}$, so the poss…

Spanning-subtree probability conjecture. For every graph $G$ with $n$ vertices,

Almost-spanning subtree ratio conjecture. For every graph $G$ of order $n$,

Let $T$ be a tree of order $m$, and let $G$ be a $k$-connected graph. Write $\delta(G)$ for the minimum degree of $G$. A tree subgraph is $k$-redundant if it has the redundancy pro…

Let $G$ be any graph and $0\leq q\leq1$. Let $\mathcal{M}_{ef}(q)$ be the random-cluster polynomial associated with distinct edges $e,f$, and let $A_{\beta,\gamma}$ be the set of…