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

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 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), 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 [1], 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 expressibility theory.

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 logic. We look at the game-theoretic 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), 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 [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), 169-199. We prove that non-reachability 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), 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 weak thresholds. 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 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) 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 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 Anti-Ramsey Theorem on Posets, Bulletin of the Institute of Combinatorics and its Applications 38 (2003) 84-100. 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 [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 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.

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.