
Mathematical Research
Currently, I am trying to understand mathematical games and
random structures.
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
foreseeable future.
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 website 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
computer scientists.)
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
understanding LFP.
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
that:
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
sequence.
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.
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), 13241345.
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
points.
Out of this somewhat esoteric acorn, eventual periodicity (5. below) would
grow.
2. Parametrization over inductions with a bounded number of variables,
Ann. Pure & Appl. Logic 48 (1990), 103134.
This is the third fourth of my Ph.D. thesis.
Here, we generalize the classical parametrization theorems to nonacceptable
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), 129151.
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), 6875.
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 icolored 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 nonfinitary trees are allowed.
We conjecture that when I and all factors are finite, such i must exist.
5. Eventual Periodicity and OneDimensional Queries,
Notre Dame J. Formal Logic 33:2 (1992), 273290.
Out of the esoteric acorn (see [1], above) comes: on large, chainlike
graphs, onedimensional and monadic second orderdefinable 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 1dimensional
LFP from Monadic Second Order (as described by Buchi & Ladner).
6. On the complexity of deadlockfree programs on a ring of processors
(with W. E. Clark &
W. R. Stark, both at USF),
J. Par. Dist. Comp. 16 (1992), 6771.
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), 293298.
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
expressibility theory.
8. Dimension Versus Number of Variables, and Connectivity, Too,
Math. Log. Quart. 41 (1995), 111134.
Dimension and Number of variables are two complexity measures in LFP
logic.
We look at the gametheoretic version of LFP explored in paper [11]
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
(with
E. Graedel, at the Lehrgebiet Mathematische Grundlagen der
Informatik, in Aachen),
Inform. & Comp. 119:1 (1995), 129135.
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), 392413.
The longawaited horrible proof (using eventual periodicity and
monotonicity) that nonreachability on finite
graphs is precisely 2dimensional.
Remember, you heard it here first.
11. Pebble games and subroutines in least simple fixed point logic,
Inform. & Comp. 122:2 (1995), 201220.
Here, I generalize LFP into a Dataloglike game structure, which allows
me to generate a nonlinear hierarchy in stratified least fixed point
logic, based on subroutines.
This is is continued in [8] above, and is the basis for much of my current
research.
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,
(with
E. Graedel, at the Lehrgebiet Mathematische Grundlagen der
Informatik, in Aachen),
Ann. Pure & Appl. Logic 77 (1996), 169199.
We prove that nonreachability is not in FO + pos TC.
We cook up an alternate hierarchy to the one in [11], and present a proof
of (a a stronger version of) the Main Theorem of [11].
This paper follows a FOCS abstract.
13. An application of spanning trees to the separation of $k$ points
in Euclidean space,
(with
B. Shekhtman and
W. E. Clark,
at USF), Proc. Lond Math. Soc. (2) 58 (1998), 297130.
In nspace, say that a set F of functions from nspace to the reals is
kseparating if, for every ksubset S of nspace, there is a function f in
F that is 11 on S.
We prove that the minimum kseparating sets of differentiable functions
have n(k  1) functions.
14. A Splitting Inequality,
Ramanujan 2 (1998), 511519.
We present a new (and at last, completely elementary) proof of the
theorem that all monotoneincreasing properties of graphs have
weak thresholds.
We explore the connection between this proof and the BollobasThomason
proof, which uses the KruskalKatona theorem.
The relation to the Sshaped 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) 239266.
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
graph, in
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
paper.)
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) 331347.
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), 203226.
This is an introduction to random trees intended for nonexperts (i.e.,
researchers with no particular background in probabilistic methods or
in combinatorics).
We describe three useful techniques  moment methods, generating functions,
and branching processes.
We also give some background and applications to computation.
18. An AntiRamsey Theorem on Posets,
Bulletin of the Institute of Combinatorics and its Applications 38
(2003) 84100.
After my paper on A Ramseyian Theorem for Products of Trees, I
conjectured that any 2coloring (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 2coloring 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 [2].
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
Alan Woods
(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 1dimensional 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 notsosparse
strong threshold results but not for the justabovephasetransition
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 [11] above with game representations of NLOGSPACE (FO + pos TC),
PSPACE, and EXPTIME; these representations can be extended to higher types.

