Currently, I am trying to understand mathematical games and
I have some pages for logical and combinatorial games linked from this
page, and I will be putting up some stuff on random structures in the
The most of this page is devoted to past papers.
I am trying to understand mathematical games --- i.e., those things known
as "mathematical games" by logicians and combinatorists, and as "extended
games" by game theorists.
So what I am doing in this web-site is describing some important research
(including my own) with references for people who want to explore further.
Since I am trying to learn something about these subjects, I appreciate
questions, comments, and even (gentle) criticism.
I especially appreciate new kinds of games and new models of random
structures, and other areas of game theory that I have missed.
Perhaps I should explain where I am coming from.
I got a Ph.D. in mathematics from UCLA in 1986, where I had worked on
abstract recursion under Yiannis Moschovakis.
(The kind of abstract recursion I worked on was elementary induction, which
is now called Least Fixed Point logic, or just LFP to very theoretical
Most of my thesis was on recursion on infinite models, but I soon was
doing work on finite models.
I also spent some time working on ramsey theory, and also in analysis.
More recently, I became convinced that pebble games were the key to
I do not mean the pebble games developed by Ehrenfeucht, I mean the more
ancient game of the sort: you have a statement P and a structure M, and
there are two players, call them Eloise and Abelard (some people call them
I and II, or Angel and Demon, or Assertor and Denier).
They play a game on M in such a way that Eloise has a winning strategy iff
P is true on M.
For example, if M was a graph, and P was the statement "the graph is
connected", then the game would be as follows.
First, Abelard chooses two vertices, a and b.
Then Eloise must choose a sequence of vertices x(1), x(2), ..., x(n) so
1. a = x(1) and x(n) = b.
2. For each i, 0 < i < n, there is an edge from x(i) to x(i+1).
If Eloise succeeds, she wins.
If Eloise never succeeds, Abelard wins (so it could take an infinite amount
of time for Eloise to lose, if she simply wanders around forever.
In this game, if M is a connected graph, then Eloise has a winning
strategy: she can just select the vertices of some path from a to b in
On the other hand, if M is not connected, then Abelard could select a and
b on separate components, and then sit back and watch Eloise fail to
select a path connecting them.
So that is where I am at present.
To go to my first game page, click here.
The rest of this page consists of links and references to my papers.
Here are papers that have already appeared in journals.
1. Some restrictions on simple fixed points of the integers,
J. Sym. Logic 54:4 (1989), 1324-1345.
This is the first half of my Ph.D. thesis.
Its about abstract recursion on the natural numbers with successor,
predecessor, and 0.
We find some restrictions on simple (i.e., without parallelism) fixed
Out of this somewhat esoteric acorn, eventual periodicity (5. below) would
2. Parametrization over inductions with a bounded number of variables,
Ann. Pure & Appl. Logic 48 (1990), 103-134.
This is the third fourth of my Ph.D. thesis.
Here, we generalize the classical parametrization theorems to non-acceptable
structures (which include the finite structures).
The discerning reader will detect the blooper on p. 124.
3. When is Arithmetic Possible?,
Ann. Pure & Appl. Logic 50 (1990), 129-151.
The last fourth of my Ph.D. thesis.
Here I launch two conjectures on LFP logic: on a class of
(finite) structures, FO = LFP iff all LFP inductions are bounded, and
all LFP inductions are bounded iff the a popular infinitary logic
collapses to FO.
Kolaitis, Vardi and Dewar confirmed the latter conjecture, while
Immerman, Gurevich and Shelah found counterexamples to the former.
4. A Ramseyian Theorem for Products of Trees,
J. Comb. Th.-A 57:1 (1991), 68-75.
Suppose that P is a Cartesian product of posets.
Let X be a coloring of P: for each tuple p, X(p) is a color in I.
Under what conditions do we know that there must be a color i such
that there is an i-colored copy of one of the poset factors of P?
We explore the situation for I finite and each factor being a finitary
tree: such an i must exist.
There is a counterexample when non-finitary trees are allowed.
We conjecture that when I and all factors are finite, such i must exist.
5. Eventual Periodicity and One-Dimensional Queries,
Notre Dame J. Formal Logic 33:2 (1992), 273-290.
Out of the esoteric acorn (see , above) comes: on large, chain-like
graphs, one-dimensional and monadic second order-definable relations
are `eventually periodic' in the sense that they eventually cycle on
the chains in a predictable way.
We can take advantage of the monotonicity of LFP inductions to separate
some expressibility classes, in particular, separating 1-dimensional
LFP from Monadic Second Order (as described by Buchi & Ladner).
6. On the complexity of deadlock-free programs on a ring of processors
(with W. E. Clark &
W. R. Stark, both at USF),
J. Par. Dist. Comp. 16 (1992), 67-71.
This is a cute application of extremal graph theory to parallel computing.
We have a ring of processors, each communicating to its `predecessor'
each having an identical incomplete program.
We want to know how complete the programs must be to assure that the
system won't be unable to act.
7. Some Ramsey theory in boolean algebra for complexity classes,
Z. math. Logik Grund. Math. 38 (1992), 293-298.
We take a bit of lore, the fact that for any countable W, if A and B are
subsets of W, then there exists an infinite subset H of W such that
the intersections of A and H and of A and B are the same.
We see how far we can push this result, and look at applications in
8. Dimension Versus Number of Variables, and Connectivity, Too,
Math. Log. Quart. 41 (1995), 111-134.
Dimension and Number of variables are two complexity measures in LFP
We look at the game-theoretic version of LFP explored in paper 
below, and represent dimension and number of variables.
We use these characterizations to compute the dimension and number
of variables of nonconnectivity.
9. On the Power of Deterministic Transitive Closure
E. Graedel, at the Lehrgebiet Mathematische Grundlagen der
Informatik, in Aachen),
Inform. & Comp. 119:1 (1995), 129-135.
We prove that FO + pos DTC is closed under negation, and within
some highly uniform graphs collapses into FO, thus separating it
from FO + pos TC.
This paper follows a LICS abstract.
10. The Dimension of the Negation of Transitive Closure,
J. Sym. Logic 60:2 (1995), 392-413.
The long-awaited horrible proof (using eventual periodicity and
monotonicity) that non-reachability on finite
graphs is precisely 2-dimensional.
Remember, you heard it here first.
11. Pebble games and subroutines in least simple fixed point logic,
Inform. & Comp. 122:2 (1995), 201-220.
Here, I generalize LFP into a Datalog-like game structure, which allows
me to generate a nonlinear hierarchy in stratified least fixed point
logic, based on subroutines.
This is is continued in  above, and is the basis for much of my current
Incidentally, I have since discovered that a more general investigation
anticipating some of my approach was launched decades ago by J. Hintikka:
see my page on Game
Theoretic Semantics for details.
12. Hierarchies in Transitive Closure Logic, Stratified Datalog,
and Infinitary Logic,
E. Graedel, at the Lehrgebiet Mathematische Grundlagen der
Informatik, in Aachen),
Ann. Pure & Appl. Logic 77 (1996), 169-199.
We prove that non-reachability is not in FO + pos TC.
We cook up an alternate hierarchy to the one in , and present a proof
of (a a stronger version of) the Main Theorem of .
This paper follows a FOCS abstract.
13. An application of spanning trees to the separation of $k$ points
in Euclidean space,
B. Shekhtman and
W. E. Clark,
at USF), Proc. Lond Math. Soc. (2) 58 (1998), 297-130.
In n-space, say that a set F of functions from n-space to the reals is
k-separating if, for every k-subset S of n-space, there is a function f in
F that is 1-1 on S.
We prove that the minimum k-separating sets of differentiable functions
have n(k - 1) functions.
14. A Splitting Inequality,
Ramanujan 2 (1998), 511-519.
We present a new (and at last, completely elementary) proof of the
theorem that all monotone-increasing properties of graphs have
We explore the connection between this proof and the Bollobas-Thomason
proof, which uses the Kruskal-Katona theorem.
The relation to the S-shaped theorem of reliability theory is investigated
in the paper on weak thresholds above.
15. First Order Zero One Laws for Random Graphs on the Circle,
Random Struct. & Alg. 14 (1999) 239-266.
We look at the model of random graphs proposed by Gilbert: scatter
n vertices on a metric space and connect those which are within
distance d apart.
This model has been investigated, overtly or otherwise, in the theory
of coverage processes, percolation, cluster analysis, biological
models of computation, and elsewhere.
We have the metric space be the unit circle (the distance being measured
around the circle), and we look at what happens as d = d(n)
rises from 0 to pi.
(Some of these results were anticipated in a more precise paper by
E. Godehardt and J. Jaworsky, On the connectivity of a random interval
Random Structures & Algorithms 9:2, 1996, and apparently not reviewed
in the AMS Reviews, grump, grump, grump, so let's say that the AMS Review
should say that if you want to understand this model, start with this
Among other things, we find that for each fixed d, the set of
a.s. FO sentences in this model is a complete noncategorical theory.
This paper follows a LICS abstract.
16. MSO Zero One Laws on Random Labelled Acyclic Graphs,
Discrete Mathematics 254 (2002) 331-347.
We prove a result announced in the AMS abstracts.
We use elementary methods to prove that over free labelled trees, MSO
definable queries are almost surely true or almost surely false.
17. Introducting Random Trees, Research on
Language and Computation 1 (2003), 203-226.
This is an introduction to random trees intended for non-experts (i.e.,
researchers with no particular background in probabilistic methods or
We describe three useful techniques --- moment methods, generating functions,
and branching processes.
We also give some background and applications to computation.
18. An Anti-Ramsey Theorem on Posets,
Bulletin of the Institute of Combinatorics and its Applications 38
After my paper on A Ramseyian Theorem for Products of Trees, I
conjectured that any 2-coloring (i.e., red & blue) of a Cartesian product
of finite posets P x Q admits either a red copy of P or a blue copy of Q.
In this paper, I disprove this conjecture by proving that if n is sufficiently
larger than m, then there is a 2-coloring of the poset of the power set
of [m+n] that does not admit either a red copy of the poset of the power
set of [n], nor a blue copy of the poset of the power set of .
19. Guarded Quantification in Least Fixed Point Logic,
J. Logic, Language and Information, to appear.
This article introduces a (positive) least fixed point logic in which
quantification is restricted by guard relations.
This logic is more relaxed than previous guarded least fixed point logics,
which were motivated by modal logic type considerations: this one was
motivated by game logic and database considerations.
This logic turns out to have the same expressive power as the classical
positive least fixed point logic of Moschovakis.
20. On the Structure of Random Unlabelled Acyclic
Graphs, Discrete Mathematics 227 (2004), 147 - 170.
We use prove a variation of a result of
(that all MSO queries over random trees have asymptotic probabilities,
which he proved using hardcore generating function methods: see
RSA 10 (1997) Colouring rules for finite trees ...) that over free
unlabelled trees, MSO definable queries are almost surely true or
almost surely false.
The proof is an elementary version of Woods's approach, and this
scenic route gives us a lot of information about the anatomy of
(almost all) unlabelled trees.
21. Threshold Functions for Random Graphs on a Line
Segment, Combinatorics, Probability, Computing 13 (2004), 373 - 387.
This article presents a proof that in the 1-dimensional model of Gilbert
random graphs, all upwards closed properties have at least weak thresholds.
In addition, all upwards closed properties whose thresholds are sufficiently
higher than the threshold for connectivity have strong thresholds.
We also present some counterexamples.
I have just seen an interesting paper on a variant of these problems
for higher dimensions by
Ashish Goel, Bhaskar Krishnamacari, and Sanatan Rai; they use
matching methods which, alas, will suffice for the not-so-sparse
strong threshold results but not for the just-above-phase-transition
weak threshold results.
Other stuff: comments are appreciated.
Inductive Norms and Negation, in preparation.
This is the first of a series of articles on fragments of Least Fixed
Point logic, with restrictions imposed on quantifications.
This paper introduces generalizations of the Moschovakis Boundedness
Theorem and the Immerman Negation of LFP Theorem, and explores the
sharpness of the latter using the logic "positively stratified
Existential Fixed Point."
Game Representations of Complexity Classes,
presented to the European Summer School on Logic, Language and Information,
2001, at Helsinki.
This extends  above with game representations of NLOGSPACE (FO + pos TC),
PSPACE, and EXPTIME; these representations can be extended to higher types.