Combinatorics Seminar
When: Sunday, December 14, 10am
Where: Schreiber 309
Speaker: Simi Haber, Tel Aviv University
Title: Zero-one laws for random regular graphs
Abstract:
I will present several results regarding the limiting probability
of first order properties of graphs for random regular graphs.
A first order property of graphs is a property that can be written
as a logical formula where:
the variables stand for vertices;
there are two binary relations - equality and adjacency;
there are two quantifiers - the universal and the existential;
there are the usual boolean operations (negation, disjunction,
conjunction).
Note that we may quantify only over vertices.
Consider the set of all labeled d-regular graphs on n vertices. We
turn this set into a probability space by giving all elements the
same probability. This space is denoted by G_{n,d}, and an element
drawn from this space is called a random regular graph.
It is known that for several probability spaces of graphs, the
limiting probability of every first order property is either zero
or one. In such cases it is customary to say that the zero-one law
holds in that probability space. We show that for every d=d(n)
linear in n, and also for every d=d(n) in the form d=n^a, a is
irrational, the zero-one law holds for G_{n,d}. On the other hand,
for d=n^a, a is rational, there exists a first order property A
with no limiting probability in G_{n,d}. These results match the
corresponding results available for the random binomial graph
G(n,p), with p=d/n.
Joint work with Michael Krivelevich.