Combinatorics Seminar

When: Sunday, May 2, 10am Where: Schreiber 309 Speaker: Simi Haber, Tel Aviv U. Title: The number of F-matchings in a random tree is almost always a zero residue

Abstract:

Let F and T be trees. An F-matching of T is a set of vertex disjoint copies of F in T. The F-matching is said to be induced if no additional edge of T is spanned by the vertices of the matching. In the talk we shall show that for a fixed integer m and a fixed tree F, the number of F-matchings in a random tree is congruent to zero modulo m with probability tending exponentially fast to one as the number of vertices tends to infinity. The same holds also in the induced case. Our result generalizes a recent result of Wagner showing that the number of independent sets in a random tree is almost always congruent to zero modulo m.