Back to Search
Start Over
A logical limit law for the sequential model of preferential attachment graphs
- Publication Year :
- 2024
-
Abstract
- For a sequence of random graphs, the limit law we refer to is the existence of a limiting probability of any graph property that can be expressed in terms of predicate logic. A zero-one limit law is shown by Shelah and Spencer for Erd\"{o}s-Renyi graphs given that the connection rate has an irrational exponent. We show a limit law for preferential attachment graphs which admit a P\'{o}lya urn representation. The two extreme cases of the parametric model, the uniform attachment graph and the sequential Barab\'{a}si-Albert model, are covered separately as they exhibit qualitative differences regarding the distribution of cycles of bounded length in the graph.<br />Comment: 42 pages
- Subjects :
- Mathematics - Probability
Mathematics - Combinatorics
Mathematics - Logic
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2408.07475
- Document Type :
- Working Paper