joint work with Anuj Dawar

Speaker(s)

Eryk Kopczyński

Affiliation

Uniwersytet Warszawski

Date

Nov. 16, 2011, 2:15 p.m.

Room

room 5870

Title in Polish

Zero-one laws and planar graphs

Seminar

Seminar Automata Theory

---

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.

---