Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 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.


References [Enhancements On Off] (What's this?)

  • 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: 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

American Mathematical Society