Asymptotics for logical limit laws: When the growth of the components is in an RT class

Authors:
Jason P. Bell and Stanley N. Burris

Journal:
Trans. Amer. Math. Soc. **355** (2003), 3777-3794

MSC (2000):
Primary 03C13, 05A16, 11P99, 41A60; Secondary 11N45, 11N80, 11U99, 60J20

DOI:
https://doi.org/10.1090/S0002-9947-03-03299-9

Published electronically:
May 29, 2003

MathSciNet review:
1990173

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Compton's method of proving monadic second-order limit laws is based on analyzing the generating function of a class of finite structures. For applications of his deeper results we previously relied on asymptotics obtained using Cauchy's integral formula. In this paper we develop elementary techniques, based on a Tauberian theorem of Schur, that significantly extend the classes of structures for which we know that Compton's theory can be applied.

**1.**Jason P. Bell,*Sufficient conditions for zero-one laws.*Trans. Amer. Math. Soc.**354**(2002), no. 2, 613-630. MR**2002j:60057****2.**Jason P. Bell, Edward A. Bender, Peter J. Cameron, and L. Bruce Richmond,*Asymptotics for the probability of connectedness and the distribution of number of components.*Electron. J. Combin.**7**(2000), R33. MR**2001d:05009****3.**Edward A. Bender,*Asymptotic methods in enumeration.*SIAM Rev.**16**(1974), 485-515. MR**51:12545****4.**Stanley N. Burris,*Number Theoretic Density and Logical Limit Laws.*Mathematical Surveys and Monographs, Vol.**86**, Amer. Math. Soc., Providence, RI, 2001. MR**2002c:03060****5.**Stanley Burris,*Spectrally determined first-order limit laws.*Logic and Random Structures (New Brunswick, NJ, 1995), 33-52, ed. by Ravi Boppana and James Lynch. DIMACS Ser. Discrete Math. Theoret. Comput. Sci.**33**, Amer. Math. Soc., Providence, RI, 1997. MR**98j:03047****6.**Stanley Burris and András Sárközy,*Fine spectra and limit laws I. First-order laws.*Canad. J. Math.**49**(1997), 468-498. MR**98k:03076a****7.**Kevin J. Compton,*A logical approach to asymptotic combinatorics. I. First order properties.*Adv. in Math.**65**(1987), 65-96. MR**88k:03065****8.**Kevin J. Compton,*A logical approach to asymptotic combinatorics. II. Monadic second-order properties.*J. Combin. Theory, Ser. A**50**(1989), 110-131. MR**90c:03024****9.**N. G. de Bruijn, D. E. Knuth, and S. O. Rice,*The average height of planted plane trees.*Graph Theory and Computing, Academic Press, New York, 1972, pp. 15-22. MR**58:21737****10.**R. Durrett, B. Granovsky, and S. Gueron,*The equilibrium behavior of reversible coagulation-fragmentation processes.*J. Theoret. Probab.**12**(1999), 447-474. MR**2000g:82013****11.**Arnold Knopfmacher, John Knopfmacher, and Richard Warlimont,*``Factorisatio numerorum'' in arithmetical semigroups.*Acta Arith.**61**(1992), 327-336. MR**93f:11069**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
03C13,
05A16,
11P99,
41A60,
11N45,
11N80,
11U99,
60J20

Retrieve articles in all journals with MSC (2000): 03C13, 05A16, 11P99, 41A60, 11N45, 11N80, 11U99, 60J20

Additional Information

**Jason P. Bell**

Affiliation:
Mathematics Department, University of Michigan, East Hall, 525 East University, Ann Arbor, Michigan 48109-1109

Email:
belljp@umich.edu

**Stanley N. Burris**

Affiliation:
Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1 Canada

Email:
snburris@thoralf.uwaterloo.ca

DOI:
https://doi.org/10.1090/S0002-9947-03-03299-9

Keywords:
Ratio test,
Schur's Tauberian theorem,
asymptotic density,
monadic second-order logic,
zero-one law,
limit law

Received by editor(s):
June 26, 2002

Received by editor(s) in revised form:
January 10, 2003

Published electronically:
May 29, 2003

Additional Notes:
The second author would like to thank NSERC for support of this research

Article copyright:
© Copyright 2003
American Mathematical Society