✦ LIBER ✦

Random graphs in the monadic theory of order

✍ Scribed by Shmuel Lifsches; Saharon Shelah

Publisher: Springer
Year: 1999
Tongue: English
Weight: 278 KB
Volume: 38
Category: Article
ISSN: 0933-5846
DOI: 10.1007/s001530050129

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Theory of random graphs

✍ I. N. Kovalenko 📂 Article 📅 1974 🏛 Springer US 🌐 English ⚖ 214 KB

The monadic second-order logic of graphs

The monadic second-order logic of graphs XIV: uniformly sparse graphs and edge set quantifications

✍ Bruno Courcelle 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 342 KB

We consider the class US k of uniformly k-sparse simple graphs, i.e., the class of ÿnite or countable simple graphs, every ÿnite subgraph of which has a number of edges bounded by k times the number of vertices. We prove that for each k, every monadic second-order formula (intended to express a grap

Algorithmic theory of random graphs

✍ Alan Frieze; Colin McDiarmid 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 2 views

The theory of random graphs has been mainly concerned with structural w x properties, in particular the most likely values of various graph invariantsᎏsee Bollobas 21 . There has been increasing interest in using random graphs as models for the average case analysis of graph algorithms. In this pap

A regular characterization of graph lang

A regular characterization of graph languages definable in monadic second-order logic

✍ Joost Engelfriet 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 867 KB

Convergence of probabilities for the sec

Convergence of probabilities for the second order monadic properties of a random mapping

✍ Tomasz Łuczak; Luboš Thoma 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

We prove that the probability of each second order monadic property of a random mapping u converges as n ª ϱ.

The monadic theory of (ω2,

✍ Shmuel Lifsches; Saharon Shelah 📂 Article 📅 1992 🏛 Springer 🌐 English ⚖ 325 KB