Nie jesteś zalogowany | Zaloguj się

Zero-one laws and planar graphs

Prelegent(ci)
Eryk Kopczyński
Afiliacja
Uniwersytet Warszawski
Termin
16 listopada 2011 14:15
Pokój
p. 5870
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.