Combinatorics Seminar
When: Sunday, May 8, 10am
Where: Schreiber 309
Speaker: Simi Haber, Tel Aviv U.
Title: Extending the first order language by graph
properties (PhD defense talk)
Abstract:
In this talk I will present results regarding zero-one laws for extensions
of the first order language of graphs. The first order language of
graphs is a formal language in which one may express some properties
of graphs. Let p be a constant between zero and one. We say that a
logic L has a limit law if every graph property expressible in L has a
limiting probability in G(n,p). We say that L obeys a zero-one law if
this limit is always either zero or one. Glebskii et al and independently
Fagin showed that the zero-one law holds for the first order language of
graphs. There are numerous results dealing with zero-one laws and limit
laws for extensions of the first order language, but to the best of our
knowledge all of these extensions are logical in nature.
A related question asked many times is the following: Given a graph
property P, is there a language able to express P but still obeying the
zero-one law (or a limit law)? Natural candidates for P are connectivity,
k-colorability and hamiltonicity. We provide the following answers.
There is a language able to express first order properties, connectivity
and k-colorability for any finite k, while still obeying the zero-one
law. On the other hand, for any language stronger than the first order
language that is able to express hamiltonicity the limit law fails.
No prior knowledge in logic is assumed.
This is the public presentation of (part of) the PhD thesis of the
speaker conducted under the supervision of Prof. Michael Krivelevich. The
results described are based on joint work with Saharon Shelah.