COUNTING ROOTED FORESTS IN A NETWORK

Abstract. If F,G are two n×m matrices, then det(1+xFTG) =∑ P x |P |det(FP)det(GP) where the sum is over all minors [19]. An application is a new proof of the Chebotarev-Shamis forest theorem telling that det(1 +L) is the number of rooted spanning forests in a finite simple graph G with Laplacian L. We can generalize this and show that det(1 + kL) is the number of rooted edge-k-colored spanning forests. If a forest with an even number of edges is called even, then det(1−L) is the difference between even and odd rooted spanning forests in G. 1. The forest theorem A social network describing friendship relations is mathematically de-scribed by a finite simple graph. Assume that everybody can chose among their friends a candidate for “president ” or decide not to vote. How many possibilities are there to do so, if cyclic nominations are discarded? The answer is given explicitly as the product of 1 + λj, where λj are the eigenvalues of the combinatorial Laplacian L of G. More generally, if votes can come in k categories, then the number voting situation is the product of 1 + kλj. We can interpret the result as counting rooted spanning forests in finite simple graphs, which is a theorem of Chebotarev-Shamis. In a generalized setup, the edges can have k colors and get a formula for these rooted spanning forests. While counting subtrees in a graph is difficult [15, 12] in Valiants complexity class #P, Chebotarev-Shamis show that this is different if the trees are rooted. The forest counting result belongs to spectral graph theory [2, 5, 7, 22, 18] or enumerative combinatorics [10, 11]. Other results relating the spectrum of L with combinatorial properties is Kirchhoff’s matrix tree theorem which expresses the number of spanning trees in a connected graph of n nodes as the pseudo determinant Det(L)/n or the Google determinant det(E+L) with Eij = 1/n 2. counting the numbe