Abstract
Let F(G) be the number of forests of a graph G. Similarly let C(G) be the number of connected spanning subgraphs of a connected graph G. We bound F(G) and C(G) for regular graphs and for graphs with a fixed average degree. Among many other things we study \(f_d=\sup _{G\in {\mathcal {G}}_d}F(G)^{1/v(G)}\), where \({\mathcal {G}}_d\) is the family of d-regular graphs, and v(G) denotes the number of vertices of a graph G. We show that \(f_3=2^{3/2}\), and if \((G_n)_n\) is a sequence of 3-regular graphs with the length of the shortest cycle tending to infinity, then \(\lim _{n\rightarrow \infty }F(G_n)^{1/v(G_n)}=2^{3/2}\). We also improve on the previous best bounds on \(f_d\) for \(4\le d\le 9\).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
For a graph \(G=(V,E)\) let \(T_G(x,y)\) denote its Tutte polynomial, that is,
where k(A) denotes the number of connected components of the graph (V, A), and v(G) denotes the number of vertices of the graph G. It is well-known that special evaluations of the Tutte polynomial have various combinatorial meaning. For instance, \(T_G(1,1)\) counts the number of spanning trees for a connected graph G. Similarly, \(T_G(2,1)\) enumerates the number of forests (acyclic edge subsets), and for a connected graph G the evaluation \(T_G(1,2)\) is equal to the number of connected spanning subgraphs, and \(T_G(2,0)\) is the number of acyclic orientations of G. In this paper, we use the notation \(F(G)=T_G(2,1)\) for the number of forests, \(C(G)=T_G(1,2)\) for the number of connected spanning subgraphs, and \(a(G)=T_G(2,0)\) for the number of acyclic orientations.
The scope of this paper is to give various upper bounds for F(G) and C(G) in terms of the average degree. A special emphasis is put on the case when G is a regular graph of degree d.
1.1 Number of Forests
First, we collect our results for the number of forests.
The following statement is well-known and serves as a motivation for many of our results. For the sake of completeness, we will give a proof of it.
Proposition 1.1
([23]) Let G be a graph, and let \(d_v\) be the degree of a vertex v. Then
When one applies Proposition 1.1 to regular graphs of degree 3 and 4, it turns out to be rather poor since the trivial inequality in terms of the number of edges e(G), that is, \(F(G)\le 2^{e(G)}\) gives stronger results. Indeed, for a 3-regular graph this trivial inequality gives \(F(G)^{1/v(G)}\le 2\sqrt{2}\), while for a 4-regular graph it gives \(F(G)^{1/v(G)}\le 4\). Surprisingly, this inequality cannot be improved for 3-regular graphs as the following result shows. Let g(G) be the length of the shortest cycle, which is called the girth of the graph G.
Theorem 1.2
Let \((G_n)_n\) be a sequence of 3-regular graphs with girth \(g(G_n)\rightarrow \infty \). Then
and
In particular, \(f_3=2\sqrt{2}\).
Note that the large girth requirement is necessary in the following sense. Suppose that for a fixed k and \(\varepsilon \) the graph G contains at least \(\varepsilon v(G)\) edge-disjoint cycles of length at most k. Then
where \(c(k,\varepsilon )<1\). Indeed, if \(C_1,C_2,\dots ,C_r\) are edge-disjoint cycles of length at most k, then
Hence
We remark that the ratio \(\frac{F(G)}{2^{e(G)}}\) can be rather large for a 3-regular graph. For instance, for the Tutte–Coxeter graph this ratio is roughly 0.728. Note that this is a 3-regular graph on 30 vertices with girth 8. It seems that for cages, that is, for regular graphs that have minimal size for a given degree and girth, this ratio can be quite large. This motivates the following question.
Problem 1.3
Let \({\mathcal {G}}_3\) be the family of 3-regular graphs. Is it true that
Before we turn our attention to 4-regular graphs, let us give one more general upper bound for the number of forests. Let us introduce the entropy function
with the usual convention \(H(0)=H(1)=0\). In the proofs, we will often use the following inequality. If \(n\le m/2\), then
The proof of this inequality can be found in [1].
Proposition 1.4
Let G be a graph with average degree \({\overline{d}}\). If \({\overline{d}}\ge 4\), then
This simple inequality is based on the rather trivial observation that a forest can have at most \(v(G)-1\) edges, and so
The problem with this bound is that if the average degree is exactly 4, this is not much different from the trivial upper bound \(2^{e(G)}=4^{v(G)}\). Already Merino and Welsh [19] noted that they found rather challenging to improve on this trivial bound even for grids. Nevertheless, \(4^{v(G)}\) is definitely not the best answer for 4-regular graphs as the following theorem shows.
Theorem 1.5
Let \({\mathcal {G}}_4\) be the family of 4-regular graphs. Then
We have seen that for 3-regular graphs the quantity \(F(G)^{1/v(G)}\) is asymptotically maximized by large girth graphs. A similar theorem was proved for the number of spanning trees by McKay [16] for regular graphs of degree d for arbitrary d. Here we show that the same holds for F(G) for any d assuming a well-known conjecture about a certain negative correlation.
Conjecture 1.6
([9, 20]) Let G be a graph and let \(\mathbf{F }\) be a random forest chosen uniformly from all the forests of G. Let \(e,f\in E(G)\), then
Assuming Conjecture 1.6 we can prove a result on forests of 2-covers which then implies our claim about the large girth graphs.
Recall that a k-cover (or k-lift) H of a graph G is defined as follows. The vertex set of H is \(V(H)=V(G)\times \{0,1,\dots , k-1\}\), and if \((u,v)\in E(G)\), then we choose a perfect matching between the vertex set \(L_u=\{(u,i)\ |\ 0\le i\le k-1\}\) and \(L_v=\{(v,i)\ |\ 0\le i\le k-1\}\). If \((u,v)\notin E(G)\), then there are no edges between \(L_u\) and \(L_v\). Fig. 1 depicts a 2-lift.
When \(k=2\) one can encode the 2-lift H by putting signs on the edges of the graph G: the \(+\) sign means that we use the matching ((u, 0), (v, 0)), ((u, 1), (v, 1)) at the edge (u, v), the − sign means that we use the matching ((u, 0), (v, 1)), ((u, 1), (v, 0)) at the edge (u, v). For instance, if we put \(+\) signs to every edge, then we simply get the disjoint union \(G\cup G\), and if we put − signs everywhere, then the obtained 2-cover H is simply the tensor product \(G\times K_2\). Observe that if G is bipartite, then \(G\cup G=G\times K_2\), but other 2-covers might differ from \(G\cup G\).
Theorem 1.7
Let G be a graph, and let H be a 2-cover of G. If Conjecture 1.6is true, then we have
In other words, \(F(G)^{1/v(G)}\le F(H)^{1/v(H)}\).
There is a nice property of covers that is related to the girth. For every graph G, there is a sequence of graphs \((G_n)_n\) such that \(G_0=G\), \(G_k\) is a 2-cover of \(G_{k-1}\), and \(g(G_k)\rightarrow \infty \). This is an observation due to Linial [15], his proof is also given in [6]. This observation and Theorem 1.7 (assuming Conjecture 1.6) together imply the following statement. If one can prove that for any sequence of d-regular graphs \((G_n)_n\) with \(g(G_n)\rightarrow \infty \), the limit \(\lim _{n\rightarrow \infty }F(G_n)^{1/v(G_n)}\) always exists, and its value is (always) \(s_d\), then \(\sup _{G\in {\mathcal {G}}_d}F(G)^{1/v(G)}=s_d\).
Large girth d-regular graphs locally look like the infinite d-regular tree. So the above discussion suggests that it is natural to compare finite graphs with the infinite d-regular tree. At first sight, it might not be clear how to do it. Nevertheless, there is already such an argument in the literature. Kahale and Schulman [11] gave an upper bound on the number of acyclic orientations a(G) in this spirit. Note that \(a(G)=T_G(2,0)\le T_G(2,1)=F(G)\). Their proof actually works for F(G) too, and for \(d\ge 6\) this upper bound is better than any of these three bounds: the trivial bound \(2^{d/2}\) provided by \(F(G)\le 2^{e(G)}\), the bound \(d+1\) provided by Proposition 1.1, and the bound \(\exp \left( \frac{d}{2}H\left( \frac{2}{d}\right) \right) \) provided by Proposition 1.4.
Theorem 1.8
(Kahale and Schulman [11]) Let G be a d-regular graph. Then
where
Theorem 1.8 gives the bound
In this paper, we will review the proof of Theorem 1.8 and show how to improve on it for certain d. The proof is actually a combination of the proof of Theorem 1.8 and Proposition 1.4. In particular, we will prove the following statement.
Theorem 1.9
Let G be a d-regular graph, where \(d\!\in \! \{5,6,7,8,9\}\). Then \(F(G)^{1/v(G)}\!\le C_d\), where \(C_d\) is a constant strictly better than the one given in Theorem 1.8and is given in Table 1.
Remark 1.10
One might wish to compare these results with existing bounds on finite and infinite sections of Archimedean lattices, cf. [3,4,5, 18, 19]. For these specific graphs one may give more accurate bounds.
1.2 Number of Connected Spanning Subgraphs
In this section, we collect the results on the number of connected spanning subgraphs. Again the trivial upper bound is \(C(G)\le 2^{e(G)}\) which gives \(C(G)^{1/v(G)}\le 2^{d/2}\) for a graph with average degree d. This time this inequality can never be tight, not even for 3-regular graphs.
Theorem 1.11
Let \({\mathcal {G}}_d\) be the set of d-regular graphs. Then
We will again prove another upper bound for graphs with small average degree.
Theorem 1.12
Let G be a graph with average degree \({\overline{d}}\). If \(2< {\overline{d}}\le 4\), then
1.3 This Paper is Organized as Follows
Each section of the paper contains a proof of a theorem or proposition that is stated in the introduction. The proofs are in the same order as the results appear in the introduction.
2 Proof of Proposition 1.1
In this section, we give two proofs of Proposition 1.1.
In the first proof we will use the recursion
where \(G-e\) is the graph obtained from G by deleting the edge e, and G/e is the graph obtained from G by contracting the edge e. This latter operation means that we replace the end vertices u, v of e by a new vertex w, and for a vertex \(s\ne u,v\) we add as many edges between s and w as it goes between s and the set \(\{u,v\}\) in the graph G, and if there were k edges going between u and v in G, then we add \(k-1\) loops to the vertex w in G/e. The above recursion simply counts the number of forests based on the property that a forest contains the edge e or not. Note that the contraction may produce multiple edges so we necessarily work in the class of graphs with multiple edges. A forest cannot contain a loop so we can even delete them from the contraction.
Proof of Proposition 1.1
This can easily be proved by induction using the identity \(F(G)=F(G-e)+F(G/e)\). If \(e=(u,v)\), then
\(\square \)
Proof
(Second proof) For a graph G and an orientation \({\mathcal {O}}\) of the edges, the score vector of \({\mathcal {O}}\) is simply the out-degree sequence of this orientation. It is known that the number of different score vectors is exactly the number of forests of G. This is an unpublished result of R. Stanley, a bijective proof can be found in [13]. Since the out-degree of a vertex u is between 0 and \(d_u\), the number of different score vectors is at most \(\prod _{u\in V(G)}(d_u+1)\). \(\square \)
3 Proof of Theorem 1.2
In this section, we prove Theorem 1.2. Since \(a(G)\le F(G)\le 2^{e(G)}\) it is enough to prove that \(\lim _{n\rightarrow \infty }a(G_n)^{1/v(G_n)}=2\sqrt{2}\). In fact, we will prove a slightly stronger theorem. For this, we need the concepts of weakly induced forest and broken cycle. Figure 2 may help to understand these concepts.
Definition 3.1
Let us label the edges of the graph G with numbers from 1 to |E(G)|. A broken cycle is an edge set that we obtain from a cycle by deleting the edge with the largest label. Let \(c_k(G)\) be the number of edge sets with exactly k edges that do not contain any broken cycle. (Note that these edge sets must be forests, since they cannot contain cycles.)
Definition 3.2
A set \(S\subseteq E(G)\) is called a weakly induced forest if it contains no cycle, and the connected components determined by S induces exactly the edges of S, all other edges are going between the connected components. Note that the vertex set of a weakly induced forest is the vertex set of the original graph G, that is, V(G). Let \(F_{wi}(G)\) be the number of weakly induced forests.
Lemma 3.3
For any graph G, we have
Proof
The proof is based on the fact that a(G) is the number of edge subsets of E(G) without a broken cycle. This follows from the following well-known facts. Let \(\mathrm {ch}(G,q)\) be the chromatic polynomial of the graph G, this polynomial counts the number of proper colorings of the graph G when we color the vertices of the graph with q colors (it is allowed that some colors are not used), see for instance [21]. It is also known [22] that \(|\mathrm {ch}(G,-1)|=a(G)\). Furthermore, \(\mathrm {ch}(G,q)=\sum _{k=0}^{n-1}(-1)^kc_k(G)q^{n-k}\), see [24]. So \(a(G)=\sum _{k=0}^{n-1}c_k(G)\) is the number of edge subsets of E(G) without a broken cycle. From this it is immediately clear that \(a(G)\le F(G)\). It is also clear that a weakly induced forest does not contain any broken cycle no matter what the labeling is since it does not contain a path that can be obtained by deleting an edge from a cycle. Hence \(F_{wi}(G)\le a(G)\le F(G)\). \(\square \)
Remark 3.4
This remark outlines another proof of Lemma 3.3 via shattering sets. Its sole purpose is to share this unusual proof, the reader should feel free to skip this remark.
The following proof of Lemma 3.3 is based on an observation of Kozma and Moran [14]. For a set X and a set system \({\mathcal {S}}\subseteq 2^{X}\) let
and
The elements of the set system \(\mathrm {str}({\mathcal {S}})\) are the shattered sets of \({\mathcal {S}}\), and elements of the set system \(\mathrm {sstr}({\mathcal {S}})\) are the strongly shattered sets of \({\mathcal {S}}\). It is known that
Now let \(X=E(G)\) and let us fix an orientation of the edges. Then every orientation corresponds to a subset of E(G), namely to the edge set where the orientation differs from the fixed orientation. Now following Kozma and Moran let \({\mathcal {S}}\) be the family of acyclic orientations. Then \(Y\subset E(G)\) is shattered if no matter how we orient the edges of Y we can extend it to an acyclic orientation of G. It is easy to see that these are exactly the forests of G: first of all, it cannot contain a cycle, because then by orienting the cycle we cannot extend it to an acyclic orientation. Secondly, if we orient a forest somehow, then we can orient the rest of the edges according to some topological order that is compatible with the orientation of the forest. A set \(Z\subset E(G)\) is strongly shattered if we can orient the rest of the edges in a way that no matter how the edges of Z are oriented it will be an acyclic orientation. Again it is easy to see that these edge sets are exactly the weakly induced forests of G: such an edge set cannot contain a cycle or a cycle minus an edge, because otherwise no matter how we orient the rest of the edges we would be able to achieve a cycle by orienting the elements of Z. On the other hand, if Z determines a weakly induced forest, then by numbering the connected components of Z, and orienting the rest of the edges towards the largest numbers we get an orientation of \(E(G)\setminus Z\) that satisfies that no matter how we orient the edges of Z it will yield an acyclic orientation.
As a preparation for the proof of Theorem 1.2 we add some remarks. The proof uses probabilistic ideas, in particular, the so-called FKG-inequality [1, 7]. For each subset \(S\subseteq E(G)\) we can associate the indicator vector \(\omega _S\in \{0,1\}^{E(G)}\):
There is a natural partial ordering on the vectors of \(\{0,1\}^{E(G)}\): \(\omega \le \omega '\) if for all e we have \(\omega (e)\le \omega '(e)\). On the level of sets this simply means that \(\omega _S\le \omega _{S'}\) if and only if \(S\subseteq S'\). A function \(f:\{0,1\}^{E(G)}\rightarrow {\mathbb {R}}\) is monotone increasing if \(f(\omega )\le f(\omega ')\) whenever \(\omega \le \omega '\). A function \(g:\{0,1\}^{E(G)}\rightarrow {\mathbb {R}}\) is monotone decreasing if \(g(\omega )\ge g(\omega ')\) whenever \(\omega \le \omega '\).
Next let us consider the uniform measure \(\mu \) on \(\{0,1\}^{E(G)}\), that is, \(\mu (\omega _S)=\frac{1}{2^{e(G)}}\) for all \(S\subseteq E(G)\). Then \(\mu \) trivially satisfies (with equality) the so-called log-supermodularity inequality:
where \(\omega \vee \omega '\) is the vector such that \((\omega \vee \omega ')(e)=\max (\omega (e),\omega '(e))\), and \(\omega \wedge \omega '\) is the vector such that \((\omega \wedge \omega ')(e)=\min (\omega (e),\omega '(e))\). The so-called FKG-inequality [7] asserts that if the random variables \(X,Y:\{0,1\}^{E(G)}\rightarrow {\mathbb {R}}_{\ge 0}\) are both monotone increasing or both monotone decreasing and \(\mu \) is log-supermodular, then
Since the product of non-negative monotone decreasing random variables is also monotone decreasing, we get that
if every \(X_i\) is non-negative monotone decreasing random variable. With this preparation, we can prove Theorem 1.2.
Proof of Theorem 1.2
We will actually prove that \(\lim _{n\rightarrow \infty }F_{wi}(G_n)^{1/v(G_n)}=2\sqrt{2}\). By the above lemma it implies that \(\lim _{n\rightarrow \infty }a(G_n)^{1/v(G_n)}=2\sqrt{2},\) and \(\lim _{n\rightarrow \infty }F(G_n)^{1/v(G_n)}=2\sqrt{2}\).
Let us consider a subset \(A\subseteq E\) chosen uniformly at random from all possible \(2^{e(G)}\) subsets. Then
Let \(C_1,C_2,\dots ,C_k\) be the connected components of A. Note that \(C_j\) might be a single vertex, or it might contain a cycle. For a fixed vertex v let \(X_v:\{0,1\}^{E(G)}\rightarrow {\mathbb {R}}\) be the indicator variable that the vertex v is in a weakly induced tree, that is, it is a tree whose connected component contains only the edges of the tree. In other words, if \(v\in C_j\) for some j, then \(X_v(\omega _A)=1\) if \(C_j\) is a tree that only contains the edges of \(G[V(C_j)]\), otherwise it is 0. In particular, it is 0 if it contains a cycle, or \(G[V(C_j)]\) contains an edge that is not in A.
The set A is weakly induced forest if and only if \(X_v(\omega _A)=1\) for all \(v\in V(G)\). Hence
Observe that \(X_v\) are all monotone decreasing functions (a subset of a weakly induced tree is also weakly induced), and so by the FKG-inequality we get that
Here \({\mathbb {E}}[X_v]\) is the probability that v is in a weakly induced tree. Suppose that \(g(G)\ge 2k+1\), and let us choose \(R=k-1\), then the R-neighborhood of any vertex in G is an induced tree. The probability that v is in a weakly induced tree is clearly bigger than the probability that in A there is no path between v and a vertex at distance R. Next we examine this probability.
Before estimating the above probability, let us consider the case when we have a 2-ary tree of depth t, that is the root vertex has degree 2 and all other non-leaf vertices have degree 3, and all leaves are of distance t from the root vertex.
For a 2-ary tree of depth t let us consider a random subset of edges. The probability \(p_t\) that the root vertex is connected to some leaf vertex in this random subset satisfies the recursion \(p_t=p_{t-1}-\frac{1}{4}p_{t-1}^2\). Clearly, \(p_t\) is a monotone decreasing sequence and the limit q must satisfy \(q=q-\frac{1}{4}q^2\), so \(q=0\).
The R-neighborhood of a vertex v in the graph G is not exactly a 2-ary tree, because v has degree 3 unlike the root vertex of a 2-ary tree which has degree 2. Still, we can upper bound the probability that in A there is a path between v and a vertex at distance R by \(3p_{R-1}\). Hence \({\mathbb {E}}[X_v]\ge 1-3p_{R-1}\). So we have
Then using the trivial upper bound and the lower bound obtained now we get that
Since \(p_{R}\rightarrow 0\) as \(n\rightarrow \infty \) we get that
Remark 3.5
Since subgraphs free of broken cycles are already decreasing it would have been enough to consider a(G), but from the point of view of the theorem, it was a bit more convenient and natural to use weakly induced forests.
4 Proof of Proposition 1.4
In this section we prove Proposition 1.4.
Proof of Proposition 1.4
Let n be the number of vertices and let \(m={\overline{d}}n/2\) be the number of edges. Since a forest has at most \(n-1\) edges we have
where we used the fact that H(x) is monotone increasing for \(0<x<1/2\). Hence
\(\square \)
5 Proof of Theorem 1.5
In this section we prove Theorem 1.5. The following lemma is not crucial, but will turn out to be useful at some point to avoid certain technical difficulties.
Lemma 5.1
Let G be a graph and \(e=(u,v)\in E(G)\). Let us consider the graph H obtained from \(G\cup G\) in such a way that we delete the two copies \((u_1,v_1)\) and \((u_2,v_2)\) of the edge e and add the edges \((u_1,v_2)\) and \((u_2,v_1)\). Then
Remark 5.2
If G is connected and \(e=(u,v)\in E(G)\) is not a cut edge, then H is connected too. Note that H is a very special 2-cover of G.
Proof
Let
Then \(|F_1|\ge |F_2|\) and \(F(G)=|F_1|+|F_2|\). Set \(|F_1|=f_1\) and \(|F_2|=f_2\). Note that \(F(H)=3f_1^2+(f_1^2-(f_1-f_2)^2)=3f_1^2+2f_1f_2-f_2^2\) since if we add at most one of the edges of \((u_1,v_2)\) and \((u_2,v_1)\), then there are \(f_1^2\) ways to add a subset of the edges such that it will be a forest, and if we add both edges, then the only bad case that we add sets \(S_1,S_2\in F_1\setminus F_2\) in the two copies of G. Since \(3f_1^2+2f_1f_2-f_2^2\ge (f_1+f_2)^2\) we are done. \(\square \)
Now we are ready to prove Theorem 1.5.
Proof of Theorem 1.5
First, let us assume that G is connected. The idea is to bound the number of forests according to the number of edges. If the number of edges of the forest is at most \((1-\varepsilon )n\), then the number of forests is at most
If the number of edges is at least \((1-\varepsilon )n\), then we can get it from a spanning tree by deleting at most \(\varepsilon n\) edges. Hence the number of such forests is at most
where \(\tau (G)\) is the number of spanning trees.
We will use the theorem of McKay [16] claiming that the number of spanning trees of a d-regular graph is at most
For us \(d=4\), so
Hence
By choosing \(\varepsilon =0.04\) we get that \(F(G)\le C\cdot 3.994^n\), where C is some absolute constant. Next, we show that this statement is true for all 4-regular connected graphs without C, that is, \(F(G)\le 3.994^n\). Let
where the supremum is taken over all 4-regular connected graphs. We know that \(M\le C\). Let G be an arbitrary 4-regular connected graph. Now let H be the special 2-cover described in Lemma 5.1 such that H is connected too. Then
whence \(F(G)\le \sqrt{M}\cdot 3.994^{v(G)}\). Since G was arbitrary we get that \(M\le \sqrt{M}\), hence \(M\le 1\). Hence \(F(G)^{1/v(G)}\le 3.994\) for all 4-regular connected graphs. Since \(F(\bigcup G_i)=\prod F(G_i)\), the same inequality is true for disconnected graphs. \(\square \)
6 Proof of Theorem 1.7
In this section we prove Theorem 1.7. We first need a lemma.
Lemma 6.1
Let S be a finite set, and let \(\mu \) be a probability distribution on the subsets of S. Let x, y be fixed elements of S. Let \(\mathbf{S }\) be a random subset of S according to the distribution \(\mu \). Then the following inequalities are equivalent
Proof
We prove the equivalence of the first and third inequalities, the rest is similar.
and
Furthermore,
Now writing the above identities into \({\mathbb {P}}_{\mu }(x,y\in \mathbf{S })\le {\mathbb {P}}_{\mu }(x\in \mathbf{S }){\mathbb {P}}_{\mu }(y\in \mathbf{S }),\) and subtracting the identical terms we get the third inequality. \(\square \)
In the forthcoming proof, we will apply Lemma 6.1 and Conjecture 1.6 to the set \(S=E(H)\) and probability distribution \(\mu \) which takes value 0 on the non-forest subsets, and uniform on the forests.
The other tool that we need is the recursion
that we already used in the proof of Proposition 1.1. As we already noted the contraction may produce multiple edges so we necessarily work in the class of graphs with multiple edges. Conjecture 1.6 is expected to be true for graphs with multiple edges, in fact, it is expected to be true even for weighted graphs.
Now we are ready to prove Theorem 1.7.
Proof of Theorem 1.7
We prove the statement by induction on the number of edges. When G is the empty graph on n vertices, the claim is trivial. Let \(e=(u,v)\in E(G)\), and let \(e_1\) and \(e_2\) be the 2-lifts of e in a 2-cover H. For the sake of simplicity we also denote by \(e_1\) and \(e_2\) the 2-lifts of e in \(G\cup G\). We decompose F(H) according to the cases whether a forest contains \(e_1\) and/or \(e_2\):
where the first term means that we count the number of forests containing both \(e_1,e_2\), the second term counts the number of forests containing \(e_2\), but not \(e_1\), etc. Similarly, we have
Now observe that the terms \(F_{{\overline{e}}_1,{\overline{e}}_2}(H)\) and \(F_{{\overline{e}}_1,{\overline{e}}_2}(G\cup G)\) count the number of forests in 2-covers of \(G-e\), and by induction
Similarly, \(F_{e_1,e_2}(H)=F(H/\{e_1,e_2\})\) and \(H/\{e_1,e_2\}\) is isomorphic to a 2-cover of G/e. Hence
Observe that by symmetry we have \(F_{{\overline{e}}_1,e_2}(H)=F_{e_1,{\overline{e}}_2}(H)\). Let \({\mathbf {F}}\) be a random forest of H chosen uniformly, and \({\mathbb {P}}_H\) be the corresponding probability distribution. Note that with our previous notation we have
Lemma 6.1 shows that the negative correlation inequality of Conjecture 1.6, namely,
is equivalent to
In the following computation, we will apply this inequality to \(e=e_1\) and \(f=e_2\). Then
Hence \(F_{{\overline{e}}_1,e_2}(H)\ge F_{{\overline{e}}_1,e_2}(G\cup G)\). Putting together the 4 inequalities we get that \(F(H)\ge F(G\cup G)\). \(\square \)
7 Proof of Theorem 1.9
In this section, we give a new upper bound on the number of forests in regular graphs. We use some basic results from spectral graph theory such as the matrix-tree theorem and the expression of the number of closed walks as a power sum of the eigenvalues of the adjacency matrix. All these results can be found in the books of Brouwer and Haemers [2] and Godsil and Royle [8].
Definition 7.1
Let G be a graph with edge weights \(w:E(G)\rightarrow {\mathbb {R}}\). Let L(G, w) be the \(|V|\times |V|\) matrix defined as follows:
The matrix L(G, w) is the weighted Laplacian matrix of the graph G.
Lemma 7.2
(Kirchhoff’s matrix-tree theorem [2, 8, 12]) Let G be a graph with edge weights \(w:E(G)\rightarrow {\mathbb {R}}\). Let L(G, w) be its weighted Laplacian matrix. Let \(L_0(G,w)\) be the matrix obtained from L(G, w) by deleting the first row and column. Then
where \({\mathcal {T}}(G)\) is the set of spanning trees of G.
Let G be a d-regular graph with Laplacian matrix \(L(G,{\underline{1}})\). Let us add one more vertex to G, and connect it to all vertices with an edge of weight \(\alpha \). Let \(G_{\alpha }\) be the new graph. The original edges have weight 1, and a weight of a spanning tree of the graph \(G_{\alpha }\) is the product of the weights of the edges in the spanning tree. Then the weighted sum of the spanning trees of \(G_{\alpha }\) can be computed as a weighted sum of the forests of the original graph G as follows. The total weight of spanning trees in \(G_{\alpha }\), which correspond to a forest F in G with connected components \(F_1,F_2,\dots ,F_k\), is
Indeed, once we have a forest of G we can create \(\prod _{i=1}^k|F_i|\) spanning trees of \(G_{\alpha }\) by connecting one of the vertices of each component to the new vertex. Each such spanning tree has a weight \(\alpha ^k\).
Let k(F) denote the number of connected components of a forest F. By the above discussion we get that for each \(\alpha >0\) we have \(w_{\alpha }(F)(1/\alpha )^{k(F)}\ge 1\). Let us use the matrix-tree theorem (Lemma 7.2): we have \(L_0(G_{\alpha },w)=L(G,{\underline{1}})+\alpha I\), where I is the identity matrix. Then
where \(\lambda _i\) are the eigenvalues of the matrix \(L(G,{\underline{1}})\). If \(d=\mu _1\ge \mu _2\ge \dots \ge \mu _n\) are the eigenvalues of the adjacency matrix of the graph G, then \(\lambda _i=d-\mu _i\). Hence
Now we can estimate this sum as follows. In the following computation \(\mu _{KM}\) is the Kesten-McKay measure [16, 17]. Its explicit form is given by the density function
Its speciality is that
is equal to the number of closed walks of length k in the infinite d-regular tree from a fixed root vertex o. The quantity \(W_k(G)=\sum _{i=1}^n\mu _i^k\) counts the number of closed walks of length k in the graph G. The following standard argument shows that \(W_k(G)\ge nW_k({\mathbb {T}}_d,o)\) since \({\mathbb {T}}_d\) is the universal cover of any d-regular graph G. We show that for any vertex v, the number of closed walks \(W_{k}(G,v)\) of length k starting and ending at vertex v is at least as large as the number of closed walks starting and ending at some root vertex of the infinite d-regular tree \({\mathbb {T}}_d\). Let us consider the following infinite d-regular tree, its vertices are labeled by the walks starting at the vertex v which never steps immediately back to a vertex, where it came from. Such walks are called non-backtracking walks. For instance, in the depicted graph below 149831 is such a walk, but 1494 is not a backtracking walk since after 9 we immediately stepped back to 4. We connect two non-backtracking walks in the tree if one of them is a one-step extension of the other (see Fig. 3).
Note that every closed walk in the tree corresponds to a closed walk in the graph G: for instance, for the depicted graph the walk 1, 14, 149, 14, 1 in the tree corresponds to the walk 1, 4, 9, 4, 1 in the graph. On the other hand, there are closed walks in the graph G, like 149831, which are not closed anymore in the tree. This argument shows that \(W_k(G,v)\ge W_k({\mathbb {T}}_d,o)\) for all \(v\in V(G)\). Consequently, \(W_k(G)\ge nW_k({\mathbb {T}}_d,o)\).
Then
Hence
When \(\alpha =1\), then \(w_1(F)\ge 1\), and we get back the result of Kahale and Schulman (actually they used almost the same argument for acyclic orientations instead of forests). When \(\alpha =1/2\), then we get that the number of forests without isolated vertices, denoted by \(F_1(G)\), satisfies
since \(w_{1/2}(F)\ge 1\) for forests without isolated vertices.
Remark 7.3
One can explicitly compute the above integrals using a theorem of McKay [16]. For \(|\gamma |<\frac{1}{2\sqrt{d-1}}\) let
Let
Then
Clearly, one needs to use that
This is how we got the explicit bound in Theorem 1.8 that does not appear in the original paper of Kahale and Schulman [11].
Now we are ready to improve the result of Kahale and Schulman [11].
Proof
Let G be a d-regular graph on n vertices. Then the number of edges is \(m=dn/2\). Let \(F_1\) be the number of forests of G with at most cn connected components, where c is some constant that we will choose later. Let \(F_2\) be the number of forests of G with more than cn connected components. In this latter case the number of edges of the forest is at most \(e(F)=n-k(F)\le (1-c)n\). Then
since \(F_1\le \sum _{F}w_{\alpha }(F)\left( \frac{1}{\alpha }\right) ^{k(F)}\le \sum _{F}w_{\alpha }(F)\left( \frac{1}{\alpha }\right) ^{cn}\). For \(F_2\) we use the trivial bound based on the fact that such a forest has at most \((1-c)n\) edges.
Hence
Next, we choose \(\alpha \) and c to make the two terms (approximately) the same, then we arrive at the bound \(F(G)\le 2C_d^n\). If we cannot find such c, then we can still use \(c=1\) to recover the bound of Kahale and Schulman (KS-bound in the table below) that corresponds to the choice \(\alpha =1, c=1\). Besides, one can get rid of the constant 2 by the trick used in the proof of Theorem 1.5. The value of \(C_d\) is given in the table below. As we see we get a much better bound for \(d=5,6,7,8\), and a slightly better bound for \(d=9\). \(\square \)
8 Proof of Theorem 1.11
In this section we prove Theorem 1.11. Note that for a bipartite graph \(G=(A,B,E)\) there is a strikingly simple argument giving
Indeed, if we consider the probability that a random edge subset spans a connected graph, then this probability is clearly smaller than the probability that on one side of bipartition none of the vertices are isolated. Let S be a random subset of the edge set. If \(B_v\) is the bad event that the vertex \(v\in A\) is isolated, then
We used the fact that the events \(B_v\) for \(v\in A\) are independent. This gives the above inequality.
In the general case, there is no independence for all vertices. (Though we can take a large independent set of the vertex set instead of the set A.) Nevertheless, we can easily overcome it by using one of Janson’s inequalities. This needs some preparation.
Setup of Janson’s inequalities Let \(\Omega \) be a fixed set and let R be a random subset of \(\Omega \) by choosing \(r\in R\) with probability \(p_r\) mutually independently of each other. Let \((A_i)_{i\in I}\) be subsets of \(\Omega \) for some index set I. Let \(B_i\) be the event that \(A_i\subseteq R\). Let \(X_i\) be the indicator random variable for the event \(B_i\). Let
It is, of course, the number of \(A_i\subseteq R\). So the events \(\bigcap _{i\in I}\overline{B_i}\) and \(X=0\) are identical. For \(i,j\in I\) we say that \(i\sim j\) if \(A_i\cap A_j\ne \emptyset \). Note that if \(i\not \sim j\) then this is consistent with our previous notation that \(B_i\) and \(B_j\) are independent. Let
where the sum is over all ordered pairs, so \(\Delta /2\) is the same sum for unordered pairs. Set
This would be the probability of \(\bigcap _{i\in I}\overline{B_i}\) if the events \(B_i\) were independent. Finally, set
Now we are ready to state Janson’s inequalities.
Theorem 8.1
(Janson inequality [1, 10]) Let \((B_i)_{i\in I},M,\Delta ,\mu \) be as above, and assume that \({\mathbb {P}}(B_i)\le \varepsilon \) for all \(i\in I\). Then
Proof of Theorem 1.11
Now let \(R\subseteq E(G)\) be a set chosen uniformly at random. For a vertex v let \(A_v\) be the set of edges incident to the vertex v. Let \(B_v\) be the bad event that \(A_v\subseteq R\). If one of \(B_v\) occurs, then \(E(G)\setminus R\) cannot be connected since the vertex v would be an isolated vertex. We have
and
Then using Janson’s inequality with \(\varepsilon =\frac{1}{2^d}\) we get that
Hence
\(\square \)
9 Proof of Theorem 1.12
In this section we prove Theorem 1.12.
Proof of Theorem 1.12
Let us consider
We show that if \(0<q\le 1\) and \(w\ge 0\), then
Indeed,
So it is enough to show that
equivalently \(1\le q^{v(G)-k(A)-|A|}\) which is indeed true since \(|A|+k(A)\ge v(G)\) and \(0<q\le 1\). Let us apply this inequality to \(q=\frac{{\overline{d}}-2}{2}\) and \(w=1\). Note that \(0<q\le 1\) since \(2<{\overline{d}}\le 4\). Observe also that just by keeping the connected spanning subgraphs A we have
By substituting \(q=\frac{{\overline{d}}-2}{2}\) and evaluating the right-hand side we get that
\(\square \)
References
Alon, N., Spencer, J.: The Probabilistic Methods. Wiley, Hoboken (2016)
Brouwer, A.E., Haemars, W.: Spectra of Graphs. Springer, Berlin (2011)
Calkin, N., Merino, C., Noble, S., Noy, M.: Improved bounds for the number of forests and acyclic orientations in the square lattice. Electron. J. Combin. 10(1), R4 (2003)
Chang, C., Shrock, R.: Asymptotic behavior of spanning forests and connected spanning subgraphs on two-dimensional lattices. Int. J. Mod. Phys. B 34, 2050249 (2020)
Chang, C., Shrock, R.: Exponential growth constants for spanning forests on Archimedean lattices: values and comparisons of upper bounds. arXiv:2012.13468
Csikvári, P.: Lower matching conjecture, and a new proof of Schrijvers and Gurvitss theorems. J. Eur. Math. Soc. 19(6), 1811–1844 (2017)
Fortuin, C.M., Kasteleyn, R.W., Ginibre, J.: Correlation inequalities on some partially ordered sets. Commun. Math. Phys. 22, 89–103 (1971)
Godsil, C., Royle, G.F.: Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207. Springer Science and Business Media, Berlin (2001)
Grimmett, G.R., Winkler, S.N.: Negative association in uniform forests and connected graphs. Random Struct. Algorithms 24, 444–460 (2004)
Janson, S., Luczak, T., Rucinski, A.: An Exponential Bound for the Probability of Nonexistence of a Specified Subgraph in a Random Graph. Institute for Mathematics and its Applications, Berlin (1988)
Kahale, N., Schulman, L.J.: Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph. Combinatorica 16(3), 383–397 (1996)
Kirchhoff, G.: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme gefuhrt wird. Ann. Phys. Chem. 72, 497–508 (1847). (English transl. IRE Trans. Circuit Theory CT-5 (1958), 4-7)
Kleitman, D.J., Winston, K.J.: Forests and score vectors. Combinatorica 1(1), 49–54 (1981)
Kozma, L., Moran, S.: Shattering, graph orientations, and connectivity. Electron. J. Combin. 20(3), P44 (2013)
Linial, N.: Lifts of graphs, (talk slides), http://www.cs.huji.ac.il/~nati/PAPERS/lifts_ talk.pdf
McKay, B.D.: Spanning trees in regular graphs. Eur. J. Combin. 4(2), 149–160 (1983)
McKay, B.D.: The expected eigenvalue distribution of a large regular graph. Linear Algebra Appl. 40, 203–216 (1981)
Mani, A.P.: On some Tutte polynomial sequences in the square lattice. J. Combin. Theory Ser. B 102(2), 436–453 (2012)
Merino, C., Welsh, D.J.A.: Forests, colorings and acyclic orientations of the square lattice. Ann. Combin. 3, 417–429 (1999)
Pemantle, R.: Towards a theory of negative independence. J. Math. Phys. 41, 1371–1390 (2000)
Read, R.C.: An introduction to chromatic polynomials. J. Combin. Theory 4, 52–71 (1968)
Stanley, R.P.: Acyclic orientations of graphs. Discrete Math. 5(2), 171–178 (1973)
Thomassen, C.: Spanning trees and orientations of graphs. J. Combin. 1(2), 101–111 (2010)
Whitney, H.: A logical expansion in mathematics. Bull. Am. Math. Soc. 38, 572–579 (1932)
Acknowledgements
The second author thanks Ferenc Bencs for the useful discussions. The authors are very grateful to the referees for their comments and suggestions.
Funding
Open access funding provided by ELKH Alfréd Rényi Institute of Mathematics.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The first author was partially supported by the EFOP program (EFOP-3.6.3-VEKOP-16-2017-00002) and the New National Excellence Program (ÚNKP) when the project started. The second author is supported by the Counting in Sparse Graphs Lendület Research Group. When the project started he was also supported by the Marie Skłodowska-Curie Individual Fellowship grant no. 747430.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Borbényi, M., Csikvári, P. & Luo, H. On the Number of Forests and Connected Spanning Subgraphs. Graphs and Combinatorics 37, 2655–2678 (2021). https://doi.org/10.1007/s00373-021-02382-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-021-02382-x