Ernest Schimmerling

Mathematical logic seminar - April 13, 2004

Time: 12 - 1:15 p.m.

Room: Wean Hall 7220

Speaker: Oleg Pikhurko
Assistant Professor
Department of Mathematical Sciences (ACO)
Carnegie Mellon University

Title: The first order complexity of graphs

Abstract: It is not hard to write a first order formula which is true for a given graph $G$ but is false for any graph not isomorphic to $G$. The smallest number $D(G)$ of nested quantifiers in a such formula can serve as a measure for the `first order complexity' of $G$.

This graph parameter behaves somewhat strangely, not correlating very well with our everyday intuition of how complex a graph is.

For example, let $G=G(n,p)$ be a random graph. For constant $p$, $D(G)$ is of order $\log n$. For very sparse graphs its magnitude is $n$. On the other hand, for certain (carefully chosen) values of $p$ the parameter $D(G)$ can drop down to the very slow growing function $\log^* n$, the inverse of the TOWER-function. The general picture is still a mystery.

This is a joint work with Joeng-Han Kim, Joel Spencer, Helmut Veith, and Oleg Verbitsky.

Organizer's note:     Please bring your lunch.