Logical properties of random graphs from small addable classes
Published version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Dawar, Anuj https://orcid.org/0000-0003-4014-8248
Kopczyński, E
Abstract
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
Description
Keywords
zero-one laws, limit law, first-order logic, random planar graphs, smooth addable classes
Journal Title
Logical Methods in Computer Science
Conference Name
Journal ISSN
1860-5974
1860-5974
1860-5974
Volume Title
15
Publisher
Publisher DOI
Sponsorship
Leverhulme Trust (RPG-2018-077)