From jcumming@legba.math.cmu.edu Mon Feb 16 04:10:44 2004
Date: Thu, 12 Feb 2004 17:31:20 -0500 (EST)
From: James W Cummings
To: Oleg Pikhurko
Cc: Ernest Schimmerling
Subject: Re: logic seminar
On Thu, 12 Feb 2004, Oleg Pikhurko wrote:
> Dear James,
>
> If you think that the people here will be interested and there is a slot
> at the logic seminar sometime, I can give the following talk:
>
>
> 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.
>
>
> Thanks.
>
> With best wishes,
> Oleg
>
Oleg ----- We would certainly like to hear about your work at some
point! I don't know if there is a slot free this term. Ernest Schimmerling
is running the show right now, I will forward your message ....
Warmest regards J
PS I would be interested to hear more about this work, is there
something written down that I can look at??