Tue 27 Feb, 2007


Thomas:
new: accepted for publication in J. Math. Logic
new: as of 2/23/07.
---
deleted: submitted September 2004. Popa superrigidity and countable Borel
new: equivalence relations submitted December 2006.
--- Popa Superrigidity and Countable Borel
deleted: Equivalence Relations submitted December 2006.


Mon 26 Feb, 2007


Jin:
new: 40
new: 104
---
deleted: 30
deleted: 71
new: 2007-02-19T16:50:00Z
---
deleted: 2006-04-17T17:39:00Z
new: 1102
new: 6286
---
deleted: 1048
deleted: 5977
new: 52
new: 12
new: 7719
---
deleted: 49
deleted: 11
deleted: 7340
new: mso-font-signature:-1 -369098753 63 0 4129279 0;}
---
deleted: mso-font-signature:-1 -369098753 63 0 4129023 0;}
new: mso-list:l0 level1 lfo3;tab-stops:list .5in'>Inverse Problems For
new: Cuts, pdf-file, dvi-file, ps-file. new: 10.0pt'>vol 18, no 2
new: (2006) of Journal de theorie des nombres de Bordeaux.
--- href="http://math.cofc.edu/faculty/jin/research/publication.html/knese r-banach.pdf">pdf-file, dvi-file, ps-file, accepted by Journal de theorie des
deleted: nombres de Bordeaux.
new: Journal für die reine und angewandte Mathematik
new: (Crelle's Journal), 595
new: (2006), pp.121 --- 166.
--- dvi-file, ps-file,
deleted: accepted by Journal für die reine und angewandte
deleted: Mathematik (Crelle's Journal). href="http://math.cofc.edu/faculty/jin/research/upden2.pdf">pdf-file%e ndtag%,
new: in Nonstandard Methods and Applications in Mathematics, edited by N. J.
--- href="http://math.cofc.edu/faculty/jin/research/upden2.pdf">pdf-file%e ndtag%, in
deleted: Nonstandard Methods and Applications in Mathematics, edited by N. J.
new: text-indent:.5in'>
new: mso-list:l0 level1 lfo3;tab-stops:list .5in'>Introduction of
new: Nonstandard Methods for Number Theorists, pdf-file, dvi-file, ps-file,
new: submitted.
--- href="http://math.cofc.edu/faculty/jin/research/publication.html/s urvey.pdf">pdf-file, in The Strength new: of Nonstandard Analysis, ed. by Imme van den Berg and Vitor Neves, new: Springer Publisher, January 2007 href="http://math.cofc.edu/faculty/jin/research/publication.html/s urvey.pdf">pdf-file, ps-file, accepted, the Proceedings of Conference on deleted: Non Standard Mathematics, Aviero, Portugal, July 2004


Fri 23 Feb, 2007


Friedman_S: (with Katherine Thompson) Internal consistency for embedding complexity (Postscript file)
--- (with Katherine Thompson) Generics for global complexity (Postscript file)


Thu 22 Feb, 2007


Truss:


Wed 21 Feb, 2007


Friedman_S: Answer to a question of Wayne Richter (Postscr ipt file) (with Zoran Spasojevic) Mutual Diamond (Postscri pt file)
--- Answer to a question of Wayne Richter. (Postscr ipt file) (with Zoran Spasojevic) Mutual Diamond. (Postscri pt file) (with Boris Piwinger) Hyperfine structure theory and gap 2
new: morasses (Postscrip t file) (with John Krueger) Thin stationary sets and disjoint club sequences, Transactions of the American Mathematical Society 359, no. 5, 2007, pp. 2407--2420.. (Postscript file)
--- (with Boris Piwinger) Hyperfine structure theory and gap 2 morasses.(Postscript file) (with John Krueger) Thin stationary sets and disjoint club sequences, Transactions AMS. (Postscript file) (with Natasha Dobrinen) Co-stationarity of the ground model, Journal of Symbolic Logic, Vol.71, No.3, pp. 1029-1043, 2006. (Post script file) (with Philip Welch and Hugh Woodin) On the consistency strength of the inner model hypothesis (Postscript file)
--- (with Natasha Dobrinen) Co-stationarity of the ground model, Journal of Symbolic Logic, Journal of Symbolic Logic, Vol.71, No.3, pp. 1029-1043, 2006. (Post script file) (with Philip Welch and Hugh Woodin) On the consistency strength of the inner model hypothesis . (Postscript file) (with James Cummings) Square on the singular cardinals (Pos tscript file)
--- (with James Cummings) Square on the singular cardinals . (Pos tscript file) Generalisations of Gödel's universe of constructible sets (Pos tscript file)
--- Generalisations of Gödel's universe of constructible sets(Postscript file) Parameter-free uniformisation (P ostscript file)


Tue 20 Feb, 2007


Friedman_S: Higher Recursion Theory Admissible Sets Fine Structure Theory Class Forcing and Other * (with James Cummings) Square on the singular cardinals (Postscript file) * (with James Cummings) Square on the singular cardinals (Postscript file) * (with Natasha Dobrinen) Homogeneous iteration and measure one covering relative to HOD ( Postscript file) * Generalisations of Gödel's universe of constructible sets(Postscript file) * (with Philip Welch) Two observations regarding infinite time Turing machines (Postscript file)
--- (with Natasha Dobrinen) Homogeneous iteration and measure one covering relative to HOD (Post script file)

Truss:
new: [48]-[51], [54]-[59], [62-68] and [70], and can e-mail latex versions of
new: papers [69] and [71-75].
---
deleted: [48]-[51], [54]-[59], and [62-68], and can e-mail latex versions of
deleted: papers [69-75].
new: group of the random graph, Journal of group theory 9 (2006), 815-836.
---
deleted: group of the random graph,
deleted: University of Leeds preprint, 16, 2005, to appear in the Journal of Group
deleted: Theory. dvi file |
deleted: Postscript file
new: Last changed 19-2-2007.
---
deleted: Last changed 9-2-2007.


Fri 16 Feb, 2007


Kechris: . pdf file of this paper
--- .pdf file of this paper

Schindler: Co-editor of the Ontos Verlag series in Mathematical Logic. Information for potential
new: authors may be downloaded here.
--- Co-editor of the Ontos Verlag series in Mathematical Logic.

Thomas: The classification problem for
new: finite rank Butler groups preprint February 2007.

Truss:
new: [48]-[51], [54]-[59], and [62-68], and can e-mail latex versions of
new: papers [69-75].
---
deleted: [48]-[51], [54]-[59], and [61-66], and can e-mail latex versions of
deleted: papers [67-74].
new: Archive for Mathematical Logic 46 (2007), 37-42.
---
deleted: University of Leeds preprint, 19, 2004. To appear in Archive for Mathematical
deleted: Logic. dvi file |
deleted: Postscript file
new: Last changed 9-2-2007.
---
deleted: Last changed 4-1-2007.


Thu 8 Feb, 2007


Apter: Current Publication List (last revised 2/6/07):
--- Current Publication List (last revised 12/6/06): "Indestructibility and Level by
new: Level Equivalence and Inequivalence",
new: Mathematical Logic Quarterly 53, 2007, 78-85. .dvi file, LaTeX file. "Indestructibility and Level by
deleted: Level Equivalence and Inequivalence",
deleted: to appear in the
deleted: Mathematical Logic Quarterly.
deleted: Note: The final revised version of
deleted: this paper is now available. .dvi file, LaTeX file.
new: Note: A revised version of this
new: paper is currently under review.
---
deleted: Note: This paper is currently being
deleted: revised. When the final revised version
deleted: is available, this message will
deleted: be removed. LaTeX file. "Indestructibility and Measurable Cardinals
new: with Few and Many Measures", submitted for
new: publication to the Archive for Mathematical Logic. .dvi file, LaTeX file.
--- LaTeX file. (with
new: J. Cummings) "An L-like Model with
new: Very Large Cardinals", submitted for publication
new: to the Archive for Mathematical Logic.
new: .dvi file,
new: LaTeX file.

Kechris:
new: 2006; to appear in the Proceedings of the AMS
---
deleted: 2006

Schindler: (with J. Steel) The self-iterability of L[E],
new: Journal of Symb. Logic, submitted. PS%e ndtag%,
--- (with J. Steel) The self-iterability of L[E]. PS%e ndtag%,

Steel: with Ralf Schindler. The self-iterability of $L[\vec E]$,
new: preliminary draft. pdf. Models derived from mice, preliminary draft.
new: pdf.
--- Models derived from mice, preliminary draft. pdf.


Mon 5 Feb, 2007


Thomas: Borel superrigidity and the classification
new: problem for
new: the torsion-free Abelian groups of finite rank
new: accepted for publication in the Proceedings of the ICM - Madrid,
new: August 22-30, 2006.


Sun 4 Feb, 2007


Schindler:
new: pictures, more


Fri 2 Feb, 2007


Kechris: Global aspects of ergodic group actions and equivalence relations,
new: preprint (version of January 27, 2007)
--- Global aspects of ergodic group actions and equivalence relations, preprint,
deleted: (version of November 10) 2006 .pdf file of this paper (Note:
new: The main changes over the previous version of
new: November 10, 2006 are in the last part of Section 12 (especially the new
new: 12.9) and in the Addendum in Section 17.)
--- .pdf file of this paper

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