The number of \(F\)-matchings in almost every tree is a zero residue (Q625397)

Summary: For graphs \(F\) and \(G\) an \(F\)-matching in \(G\) is a subgraph of \(G\) consisting of pairwise vertex disjoint copies of \(F\). The number of \(F\)-matchings in \(G\) is denoted by \(s(F, G)\). We show that for every fixed positive integer \(m\) and every fixed tree \(F\), the probability that \(s(F,{\mathcal T}_n)\equiv 0 \pmod m\), where \({\mathcal T}_n\) is a random labeled tree with n vertices, tends to one exponentially fast as \(n\) grows to infinity. A similar result is proven for induced \(F\)-matchings. As a very special special case this implies that the number of independent sets in a random labeled tree is almost surely a zero residue. A recent result of Wagner shows that this is the case for random unlabeled trees as well.