First Order Logic of Sparse Graphs with Given Degree Sequences
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909209496387584 |
|---|---|
| author | Larrauri, Alberto Perarnau, Guillem |
| author_facet | Larrauri, Alberto Perarnau, Guillem |
| contents | We consider limit probabilities of first order properties in random graphs with a given degree sequence. Under mild conditions on the degree sequence, we show that the closure set of limit probabilities is a finite union of closed intervals. Moreover, we characterize the degree sequences for which this closure set is the interval $[0,1]$, a property that is intimately related with the probability that the random graph is acyclic. As a side result, we compile a full description of the cycle distribution of random graphs and study their fragment (disjoint union of unicyclic components) in the subcritical regime. Finally, we amend the proof of the existence of limit probabilities for first order properties in random graphs with a given degree sequence; this result was already claimed by Lynch~[IEEE LICS 2003] but his proof contained some inaccuracies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_14836 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | First Order Logic of Sparse Graphs with Given Degree Sequences Larrauri, Alberto Perarnau, Guillem Combinatorics Discrete Mathematics Logic Probability cc:05C80 (Primary), cc:03C13 (Secondary) We consider limit probabilities of first order properties in random graphs with a given degree sequence. Under mild conditions on the degree sequence, we show that the closure set of limit probabilities is a finite union of closed intervals. Moreover, we characterize the degree sequences for which this closure set is the interval $[0,1]$, a property that is intimately related with the probability that the random graph is acyclic. As a side result, we compile a full description of the cycle distribution of random graphs and study their fragment (disjoint union of unicyclic components) in the subcritical regime. Finally, we amend the proof of the existence of limit probabilities for first order properties in random graphs with a given degree sequence; this result was already claimed by Lynch~[IEEE LICS 2003] but his proof contained some inaccuracies. |
| title | First Order Logic of Sparse Graphs with Given Degree Sequences |
| topic | Combinatorics Discrete Mathematics Logic Probability cc:05C80 (Primary), cc:03C13 (Secondary) |
| url | https://arxiv.org/abs/2405.14836 |