go-v.orgdoi

Almost All Trees have an Even Number of Independent Sets

Stephan G. Wagner · The Electronic Journal of Combinatorics · 2009

  • DOI 10.37236/182
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2009

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2009

Abstract

This paper is devoted to the proof of the surprising fact that almost all trees have an even number of independent vertex subsets (in the sense that the proportion of those trees with an odd number of independent sets tends to $0$ as the number of vertices approaches $\infty$) and to its generalisation to other moduli: for fixed $m$, the probability that a randomly chosen tree on $n$ vertices has a number of independent subsets that is divisible by $m$ tends to $1$ as $n \to \infty$.

Open the resolved locator · 10.37236/182

Metadata licence: OpenAlex metadata (CC0)