Asymptotics for logical limit laws: When the growth of the components is in an RT class

Bell, Jason; Burris, Stanley

doi:10.1090/S0002-9947-03-03299-9

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 PDF

Trans. Amer. Math. Soc. 355 (2003), 3777-3794 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
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