|
Asymptotics for logical limit laws: When the growth of the components is in an RT class
Author(s):
Jason
P.
Bell;
Stanley
N.
Burris
Journal:
Trans. Amer. Math. Soc.
355
(2003),
3777-3794.
MSC (2000):
Primary 03C13, 05A16, 11P99, 41A60;
Secondary 11N45, 11N80, 11U99, 60J20
Posted:
May 29, 2003
Retrieve article in:
PDF DVI PostScript
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.
References:
-
- 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
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 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:
10.1090/S0002-9947-03-03299-9
PII:
S 0002-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
Posted:
May 29, 2003
Additional Notes:
The second author would like to thank NSERC for support of this research
Copyright of article:
Copyright
2003,
American Mathematical Society
|
Comments: webmaster@ams.org