|Time:|| 12 - 1:15 p.m.
Wean Hall 7220
|Speaker:|| Oleg Pikhurko
Department of Mathematical Sciences (ACO)
Carnegie Mellon University
The first order complexity of graphs
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
|Organizer's note:|| Please bring your lunch.