Nie jesteś zalogowany |
Zero-one laws and planar graphs
- Prelegent(ci)
- Eryk Kopczyński
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 16 listopada 2011 14:15
- Pokój
- p. 5870
- Tytuł w języku angielskim
- joint work with Anuj Dawar
- Seminarium
- Seminarium „Teoria automatów”
It is well known that first order logic admits a zero one law: a probability that a random structure of size $n$ tends to a limit of either 0 or 1 as $n$ tends to infinity. The same property holds for other logics, like the infinitary logic $L_\infty$.
A similar result is also known for MSO logic on random free labelled trees (McColm). On the other hand, if we consider random rooted labelled trees, then the probability tends to a limit which need not be 0 or 1 \cite (Woods).
Similar limit laws hold for the class of $d$-regular graphs, or where degrees of vertices have a specific distribution (Lynch).
What happens for random planar graphs?
Technically, all the techniques we are using come from previous papers: we are just merging the logical techniques of McColm with the probabilistic and combinatorial results about random planar graphs of McDiarmid, Steger and Welsh.
