Asymptotics for logical limit laws: When the growth of the components is in an RT class
HTML articles powered by AMS MathViewer
- by Jason P. Bell and Stanley N. Burris
- Trans. Amer. Math. Soc. 355 (2003), 3777-3794
- DOI: https://doi.org/10.1090/S0002-9947-03-03299-9
- Published electronically: May 29, 2003
- PDF | Request permission
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
- Jason P. Bell, Sufficient conditions for zero-one laws, Trans. Amer. Math. Soc. 354 (2002), no. 2, 613–630. MR 1862560, DOI 10.1090/S0002-9947-01-02884-7
- 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. MR 1763972, DOI 10.37236/1511
- Edward A. Bender, Asymptotic methods in enumeration, SIAM Rev. 16 (1974), 485–515. MR 376369, DOI 10.1137/1016082
- Stanley N. Burris, Number theoretic density and logical limit laws, Mathematical Surveys and Monographs, vol. 86, American Mathematical Society, Providence, RI, 2001. MR 1800435, DOI 10.1090/surv/086
- 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, DOI 10.1090/dimacs/033/03
- 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, DOI 10.4153/CJM-1997-022-4
- Kevin J. Compton, A logical approach to asymptotic combinatorics. I. First order properties, Adv. in Math. 65 (1987), no. 1, 65–96. MR 893471, DOI 10.1016/0001-8708(87)90019-3
- 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, DOI 10.1016/0097-3165(89)90009-5
- 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
- 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, DOI 10.1023/A:1021682212351
- Arnold Knopfmacher, John Knopfmacher, and Richard Warlimont, “Factorisatio numerorum” in arithmetical semigroups, Acta Arith. 61 (1992), no. 4, 327–336. MR 1168092, DOI 10.4064/aa-61-4-327-336
Bibliographic Information
- Jason P. Bell
- Affiliation: Mathematics Department, University of Michigan, East Hall, 525 East University, Ann Arbor, Michigan 48109-1109
- MR Author ID: 632303
- 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
- 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
- © Copyright 2003 American Mathematical Society
- 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
- MathSciNet review: 1990173