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), 37773794
MSC (2000):
Primary 03C13, 05A16, 11P99, 41A60; Secondary 11N45, 11N80, 11U99, 60J20
Published electronically:
May 29, 2003
MathSciNet review:
1990173
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Compton's method of proving monadic secondorder 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 zeroone
laws, Trans. Amer. Math. Soc.
354 (2002), no. 2,
613–630 (electronic). MR 1862560
(2002j:60057), http://dx.doi.org/10.1090/S0002994701028847
 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
(2001d:05009)
 3.
Edward
A. Bender, Asymptotic methods in enumeration, SIAM Rev.
16 (1974), 485–515. MR 0376369
(51 #12545)
 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
(2002c:03060)
 5.
Stanley
Burris, Spectrally determined firstorder 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
(98j:03047)
 6.
Stanley
Burris and András
Sárközy, Fine spectra and limit laws. I. Firstorder
laws, Canad. J. Math. 49 (1997), no. 3,
468–498. MR 1451257
(98k:03076a), http://dx.doi.org/10.4153/CJM19970224
 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
(88k:03065), http://dx.doi.org/10.1016/00018708(87)900193
 8.
Kevin
J. Compton, A logical approach to asymptotic combinatorics. II.
Monadic secondorder properties, J. Combin. Theory Ser. A
50 (1989), no. 1, 110–131. MR 978070
(90c:03024), http://dx.doi.org/10.1016/00973165(89)900095
 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
(58 #21737)
 10.
Richard
Durrett, Boris
L. Granovsky, and Shay
Gueron, The equilibrium behavior of reversible
coagulationfragmentation processes, J. Theoret. Probab.
12 (1999), no. 2, 447–474. MR 1684753
(2000g:82013), http://dx.doi.org/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
(93f:11069)
 1.
 Jason P. Bell, Sufficient conditions for zeroone laws. Trans. Amer. Math. Soc. 354 (2002), no. 2, 613630. 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), 485515. 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 firstorder limit laws. Logic and Random Structures (New Brunswick, NJ, 1995), 3352, 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. Firstorder laws. Canad. J. Math. 49 (1997), 468498. MR 98k:03076a
 7.
 Kevin J. Compton, A logical approach to asymptotic combinatorics. I. First order properties. Adv. in Math. 65 (1987), 6596. MR 88k:03065
 8.
 Kevin J. Compton, A logical approach to asymptotic combinatorics. II. Monadic secondorder properties. J. Combin. Theory, Ser. A 50 (1989), 110131. 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. 1522. MR 58:21737
 10.
 R. Durrett, B. Granovsky, and S. Gueron, The equilibrium behavior of reversible coagulationfragmentation processes. J. Theoret. Probab. 12 (1999), 447474. MR 2000g:82013
 11.
 Arnold Knopfmacher, John Knopfmacher, and Richard Warlimont, ``Factorisatio numerorum'' in arithmetical semigroups. Acta Arith. 61 (1992), 327336. MR 93f:11069
Similar Articles
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 481091109
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/S0002994703032999
PII:
S 00029947(03)032999
Keywords:
Ratio test,
Schur's Tauberian theorem,
asymptotic density,
monadic secondorder logic,
zeroone 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
