The number of F-matchings in almost every tree is a zero residue

2010/06/28 by Noga Alon, Alon, Noga, Simi Haber +3 · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1006.5427

Abstract

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,T_n) = 0 mod m, where 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. This generalizes a recent result of Wagner who showed that the number of independent sets in a random labeled tree is almost surely a zero residue.

Citations

• Fibonacci Numbers of Graphs

Cited by

• Fixed Point Explainability

Related

• On the number of r-matchings in a Tree
• Counting matchings in irregular bipartite graphs and random lifts
• Probabilistic enumeration and equivalence of nonisomorphic trees
• On the maximal matchings of trees
• The number of perfect matchings, and the nesting properties, of random regular graphs