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

Noga Alon, Simi Haber, Michael Krivelevich

Research output: Contribution to journalArticle

3 Scopus citations

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, Tn) ≡ 0 (mod m), where Tn 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.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
Volume18
Issue number1
DOIs
StatePublished - Jan 1 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The number of F-matchings in almost every tree is a zero residue'. Together they form a unique fingerprint.

  • Cite this