When structures are almost surely connected

Jason P. Bell

The electronic journal of combinatorics, Tome 7 (2000)

Résumé

Let $A_n$ denote the number of objects of some type of"size" $n$, and let $C_n$ denote the number of these objects which are connected. It is often the case that there is a relation between a generating function of the $C_n$'s and a generating function of the $A_n$'s. Wright showed that if $\lim_{n\rightarrow\infty} C_n/A_n =1$, then the radius of convergence of these generating functions must be zero. In this paper we prove that if the radius of convergence of the generating functions is zero, then $\limsup_{n\rightarrow \infty} C_n/A_n =1$, proving a conjecture of Compton; moreover, we show that $\liminf_{n\rightarrow\infty} C_n/A_n$ can assume any value between $0$ and $1$.

Détail

DOI : 10.37236/1514

Classification : 05A16
Mots-clés : generating function