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.