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 TOWERfunction. The general picture is still a mystery.
This is a joint work with JoengHan Kim, Joel Spencer, Helmut Veith, and
Oleg Verbitsky.

Organizer's note:  Please bring your lunch.
