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

Authors Noga Alon, Simi Haber, Michael Krivelevich

Publication date 17 February 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.5427, https://eudml.org/doc/227829, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p30.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Trees (05C05) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

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.

Review text

Summary: 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.

Recommendations

Cited in

(5)

This page was built for publication: The number of \(F\)-matchings in almost every tree is a zero residue

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q625397)