A logical limit law for the sequential model of preferential attachment graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911988257390592 |
|---|---|
| author | Özdemir, Alperen |
| author_facet | Özdemir, Alperen |
| contents | 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ö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ólya urn representation. The two extreme cases of the parametric model, the uniform attachment graph and the sequential Barabási-Albert model, are covered separately as they exhibit qualitative differences regarding the distribution of cycles of bounded length in the graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07475 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A logical limit law for the sequential model of preferential attachment graphs Özdemir, Alperen Probability Combinatorics Logic 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ö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ólya urn representation. The two extreme cases of the parametric model, the uniform attachment graph and the sequential Barabási-Albert model, are covered separately as they exhibit qualitative differences regarding the distribution of cycles of bounded length in the graph. |
| title | A logical limit law for the sequential model of preferential attachment graphs |
| topic | Probability Combinatorics Logic |
| url | https://arxiv.org/abs/2408.07475 |