The number of \(F\)-matchings in almost every tree is a zero residue
The electronic journal of combinatorics, Tome 18 (2011) no. 1
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.
@article{10_37236_517,
author = {Noga Alon and Simi Haber and Michael Krivelevich},
title = {The number of {\(F\)-matchings} in almost every tree is a zero residue},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/517},
zbl = {1213.05130},
url = {http://geodesic.mathdoc.fr/articles/10.37236/517/}
}
TY - JOUR AU - Noga Alon AU - Simi Haber AU - Michael Krivelevich TI - The number of \(F\)-matchings in almost every tree is a zero residue JO - The electronic journal of combinatorics PY - 2011 VL - 18 IS - 1 UR - http://geodesic.mathdoc.fr/articles/10.37236/517/ DO - 10.37236/517 ID - 10_37236_517 ER -
Noga Alon; Simi Haber; Michael Krivelevich. The number of \(F\)-matchings in almost every tree is a zero residue. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/517
Cité par Sources :