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

Published electronically:
May 29, 2003

MathSciNet review:
1990173

Full-text PDF Free Access

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 (electronic). MR**1862560**, 10.1090/S0002-9947-01-02884-7**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), Research Paper 33, 22 pp. (electronic). MR**1763972****3.**Edward A. Bender,*Asymptotic methods in enumeration*, SIAM Rev.**16**(1974), 485–515. MR**0376369****4.**Stanley N. Burris,*Number theoretic density and logical limit laws*, Mathematical Surveys and Monographs, vol. 86, American Mathematical Society, Providence, RI, 2001. MR**1800435****5.**Stanley Burris,*Spectrally determined first-order limit laws*, Logic and random structures (New Brunswick, NJ, 1995) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 33, Amer. Math. Soc., Providence, RI, 1997, pp. 33–52. MR**1465467****6.**Stanley Burris and András Sárközy,*Fine spectra and limit laws. I. First-order laws*, Canad. J. Math.**49**(1997), no. 3, 468–498. MR**1451257**, 10.4153/CJM-1997-022-4**7.**Kevin J. Compton,*A logical approach to asymptotic combinatorics. I. First order properties*, Adv. in Math.**65**(1987), no. 1, 65–96. MR**893471**, 10.1016/0001-8708(87)90019-3**8.**Kevin J. Compton,*A logical approach to asymptotic combinatorics. II. Monadic second-order properties*, J. Combin. Theory Ser. A**50**(1989), no. 1, 110–131. MR**978070**, 10.1016/0097-3165(89)90009-5**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**0505710****10.**Richard Durrett, Boris L. Granovsky, and Shay Gueron,*The equilibrium behavior of reversible coagulation-fragmentation processes*, J. Theoret. Probab.**12**(1999), no. 2, 447–474. MR**1684753**, 10.1023/A:1021682212351**11.**Arnold Knopfmacher, John Knopfmacher, and Richard Warlimont,*“Factorisatio numerorum” in arithmetical semigroups*, Acta Arith.**61**(1992), no. 4, 327–336. MR**1168092**

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:
http://dx.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