Logical properties of random graphs from small addable classes
We establish zero-one laws and convergence laws for monadic second-order logic (MSO) (and, a fortiori, first-order logic) on a number of interesting graph classes. In particular, we show that MSO obeys a zero-one law on the class of connected planar graphs, the class of connected graphs of tree-widt...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2019-07-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/3780/pdf |
| _version_ | 1797268585868951552 |
|---|---|
| author | Anuj Dawar Eryk Kopczyński |
| author_facet | Anuj Dawar Eryk Kopczyński |
| author_sort | Anuj Dawar |
| collection | DOAJ |
| description | We establish zero-one laws and convergence laws for monadic second-order
logic (MSO) (and, a fortiori, first-order logic) on a number of interesting
graph classes. In particular, we show that MSO obeys a zero-one law on the
class of connected planar graphs, the class of connected graphs of tree-width
at most $k$ and the class of connected graphs excluding the $k$-clique as a
minor. In each of these cases, dropping the connectivity requirement leads to a
class where the zero-one law fails but a convergence law for MSO still holds. |
| first_indexed | 2024-04-25T01:34:50Z |
| format | Article |
| id | doaj.art-bdc5c8ec402443e98ce7b512237a93a8 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:34:50Z |
| publishDate | 2019-07-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-bdc5c8ec402443e98ce7b512237a93a82024-03-08T10:28:03ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742019-07-01Volume 15, Issue 310.23638/LMCS-15(3:4)20193780Logical properties of random graphs from small addable classesAnuj DawarEryk KopczyńskiWe establish zero-one laws and convergence laws for monadic second-order logic (MSO) (and, a fortiori, first-order logic) on a number of interesting graph classes. In particular, we show that MSO obeys a zero-one law on the class of connected planar graphs, the class of connected graphs of tree-width at most $k$ and the class of connected graphs excluding the $k$-clique as a minor. In each of these cases, dropping the connectivity requirement leads to a class where the zero-one law fails but a convergence law for MSO still holds.https://lmcs.episciences.org/3780/pdfcomputer science - logic in computer sciencemathematics - logic03c13f.4.1 |
| spellingShingle | Anuj Dawar Eryk Kopczyński Logical properties of random graphs from small addable classes Logical Methods in Computer Science computer science - logic in computer science mathematics - logic 03c13 f.4.1 |
| title | Logical properties of random graphs from small addable classes |
| title_full | Logical properties of random graphs from small addable classes |
| title_fullStr | Logical properties of random graphs from small addable classes |
| title_full_unstemmed | Logical properties of random graphs from small addable classes |
| title_short | Logical properties of random graphs from small addable classes |
| title_sort | logical properties of random graphs from small addable classes |
| topic | computer science - logic in computer science mathematics - logic 03c13 f.4.1 |
| url | https://lmcs.episciences.org/3780/pdf |
| work_keys_str_mv | AT anujdawar logicalpropertiesofrandomgraphsfromsmalladdableclasses AT erykkopczynski logicalpropertiesofrandomgraphsfromsmalladdableclasses |