| 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.
|