Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 13, 2010, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Simi Haber (Tel Aviv University)
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.
Joint work with Noga Alon and Michael Krivelevich.
Automatic MiSe System Software Version 1.4803M | admin login