Symmetric Generalized Galois Logics

Symmetric generalized Galois logics (i.e., symmetric gGls) are distributive gGls that include weak distributivity laws between some operations such as fusion and fission. Motivations for considering distribution between such operations include the provability of cut for binary consequence relations, abstract algebraic considerations and modeling linguistic phenomena in categorial grammars. We represent symmetric gGls by models on topological relational structures. On the other hand, topological relational structures are realized by structures of symmetric gGls. We generalize the weak distributivity laws between fusion and fission to interactions of certain monotone operations within distributive super gGls. We are able to prove appropriate generalizations of the previously obtained theorems—including a functorial duality result connecting classes of gGls and classes of structures for them.      

Definable groups of partial automorphisms

The motivation for this paper is to extend the known model-theoretic treatment of differential Galois theory to the case of linear difference equations (where the derivative is replaced by an automorphism). The model-theoretic difficulties in this case arise from the fact that the corresponding theory ACFA does not eliminate quantifiers. We therefore study groups of restricted automorphisms, preserving only part of the structure. We give conditions for such a group to be (infinitely) definable, and when these conditions are satisfied we describe the definition of the group and the action explicitly. We then examine the special case when the theory in question is obtained by enriching a stable theory with a generic automorphism. Finally, we interpret the results in the case of ACFA, and explain the connection of our construction with the algebraic theory of Picard–Vessiot extensions. The only model-theoretic background assumed is the notion of a definable set.      

On the algebraic points of a definable set

This paper studies diophantine properties of sets definable in an o-minimal structure over the real field. The main theorem of the author’s recent paper with A. J. Wilkie is refined, and used to deduce a strong result on the density of algebraic points of such sets.      

Categoricity of computable infinitary theories

Computable structures of Scott rank are an important boundary case for structural complexity. While every countable structure is determined, up to isomorphism, by a sentence of , this sentence may not be computable. We give examples, in several familiar classes of structures, of computable structures with Scott rank whose computable infinitary theories are each -categorical. General conditions are given, covering many known methods for constructing computable structures with Scott rank , which guarantee that the resulting structure is a model of an -categorical computable infinitary theory. Work on this paper began at the Workshop on Model Theory and Computable Structure Theory at University of Florida Gainesville, in February, 2007. The authors are grateful to the organizers of this workshop. They are also grateful for financial support from National Science Foundation grants DMS DMS 05-32644, DMS 05-5484. The second author is also grateful for the support of grants RFBR 08-01-00336 and NSc-335.2008.1.     

Low regularity classes and entropy numbers

We note a sharp embedding of the Besov space into exponential classes and prove entropy estimates for the compact embedding of subclasses with logarithmic smoothness, considered by Kashin and Temlyakov. A.S. was supported in part by the National Science Foundation grant 0652890.     

Point localization and spectral theory for symmetric random operators

In a Hilbert space context, we propose a rather general notion of “random operators” which allows for taking stochastic limits. After establishing a connection with measurable fields of closed operators, we may speak of a spectral theory for symmetric random operators. Received: 18 December 2008     

Note on limits of finite graphs

We prove that for any weakly convergent sequence of finite graphs with bounded vertex degrees, there exists a topological limit graphing.     

Semifree actions of free groups

We study countable universes similar to a free action of a group G. It turns out that this is equivalent to the study of free semi-actions of G, with two universes being transformable iff one corresponding free semi-action can be obtained from the other by a finite alteration. In the case of a free group G (in finitely many or countably many generators), a classification is given. Research partially supported by a DAAD Doktorandenstipendium D/02/02345.     

When does the giant component bring unsatisfiability?

We study random constraint satisfaction problems using the wide class of models introduced by the author [36], which includes various forms of random SAT and other well-studied problems. We determine precisely which of these models remain almost surely satisfiable when the number of clauses is increased beyond the point at which a giant component appears in the underlying constraint hypergraph. This work is supported by an NSERC Research Grant and a Sloan Research Fellowship. Much of this work was done while the author was a Visiting Researcher at Microsoft Research.     

Birth control for giants

The standard Erdős-Rényi model of random graphs begins with n isolated vertices, and at each round a random edge is added. Parametrizing n/2 rounds as one time unit, a phase transition occurs at time t = 1 when a giant component (one of size constant times n) first appears. Under the influence of statistical mechanics, the investigation of related phase transitions has become an important topic in random graph theory. We define a broad class of graph evolutions in which at each round one chooses one of two random edges {v ₁, v ₂}, {v ₃, v ₄} to add to the graph. The selection is made by examining the sizes of the components of the four vertices. We consider the susceptibility S(t) at time t, being the expected component size of a uniformly chosen vertex. The expected change in S(t) is found which produces in the limit a differential equation for S(t). There is a critical time t _c so that S(t) → ∞ as t approaches t _c from below. We show that the discrete random process asymptotically follows the differential equation for all subcritical t < t _c . Employing classic results of Cramér on branching processes we show that the component sizes of the graph in the subcritical regime have an exponential tail. In particular, the largest component is only logarithmic in size. In the supercritical regime t > t _c we show the existence of a giant component, so that t = t _c may be fairly considered a phase transition. Computer aided solutions to the possible differential equations for susceptibility allow us to establish lower and upper bounds on the extent to which we can either delay or accelerate the birth of the giant component. Research supported by the Australian Research Council, the Canada Research Chairs Program and NSERC. Research partly carried out while the author was at the Department of Mathematics and Statistics, University of Melbourne.     

A new approach to interior regularity of elliptic systems with quadratic Jacobian structure in dimension two

We prove a new regularity result for systems of nonlinear elliptic equations with quadratic Jacobian type nonlinearity in dimension two. Our proof is based on an adaptation of John Lewis’ method which has not been used for such systems so far. Parts of this work have been done while the second and the third author had been enjoying the hospitality of the Department of Mathematics of the University of Pittsburgh. P.H. was supported by NSF grant DMS-0500966. P.S. was partially supported by the MNiSzW grant no 1 PO 3A 005 29. X.Z. was supported by the Academy of Finland, project 207288.     

The elementary diagram of a trivial,weakly minimal structure is near model complete

We prove that if M is any model of a trivial, weakly minimal theory, then the elementary diagram T(M) eliminates quantifiers down to Boolean combinations of certain existential formulas. M. C. Laskowski has been partially supported by NSF grant DMS-0600217.     

The Leray separating operator in the theory of the Cauchy problem

The paper is devoted to the presentation of Leray’s approach to the Cauchy problem for strictly hyperbolic operators. In the first section we give the main definitions of strictly hyperbolic operators and separating operators corresponding to them. We present the plan of derivation of the a priori estimates necessary for the proof of solvability of the Cauchy problem. In the second section we generalize the Leray approach to some classes of PDO which are not hyperbolic.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

Linear orders with distinguished function symbol

We consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably categorical. Particularly, we consider computable copies of the rationals with a fixed-point free automorphism, and also ω with a non-decreasing function. D. Cenzer was partially supported by National Science Foundation grants DMS 0532644 and 0554841 and 652372. B. Csima was partially supported by Canadian NSERC Discovery Grant 312501. B. Khoussainov has partially been supported by Marsden Fund of Royal New Zealand Society.     

The influence of the boundary behavior on isometric immersions in the hyperbolic space

This paper studies how the behavior of a proper isometric immersion into the hyperbolic space is influenced by its behavior at infinity. Our first result states that a proper isometric minimal immersion into the hyperbolic space with the asymptotic boundary contained in a sphere reduces codimension. This result is a corollary of a more general one that establishes a sharp lower bound for the sup-norm of the mean curvature vector of a Proper isometric immersion into the Hyperbolic space whose Asymptotic boundary is contained in a sphere. We also prove that a properly immersed hypersurface with mean curvature satisfying sup _{p∈Σ ||H(p)|| < 1} has no isolated points in its asymptotic boundary. Our main tool is a Tangency principle for isometric immersions of arbitrary codimension. This work is partially supported by CAPES, Brazil.     

A Generalization of the Hutchinson Measure

The Hutchinson measure is the invariant measure associated with an iterated function system with probabilities. Generalized iterated function systems (GIFS) are generalizations of iterated function systems which are obtained by considering contractions from X × X to X, rather than contractions from a metric space X to itself. Along the lines of this generalization we consider GIFS with probabilities. In this paper we prove the existence of an analogue of Hutchinson measure associated with a GIFS with probabilities and present some of its properties. The work was supported by CNCSIS grant 8A;1067/2006.     

Multi-state Systems with Graduate Failure and Equal Transition Intensities

We consider unrecoverable homogeneous multi-state systems with graduate failures, where each component can work at M + 1 linearly ordered levels of performance. The underlying process of failure for each component is a homogeneous Markov process such that the level of performance of one component can change only for one level lower than the observed one, and the failures are independent for different components. We derive the probability distribution of the random vector X, representing the state of the system at the moment of failure and use it for testing the hypothesis of equal transition intensities. Under the assumption that these intensities are equal, we derive the method of moments estimators for probabilities of failure in a given state vector and the intensity of failure. At the end we calculate the reliability function for such systems. Received: May 18, 2007., Revised: July 8, 2008., Accepted: September 29, 2008.     

“Setting” n-Opposition

Our aim is to show that translating the modal graphs of Moretti’s “n-opposition theory” (2004) into set theory by a suited device, through identifying logical modal formulas with appropriate subsets of a characteristic set, one can, in a constructive and exhaustive way, by means of a simple recurring combinatory, exhibit all so-called “logical bi-simplexes of dimension n” (or n-oppositional figures, that is the logical squares, logical hexagons, logical cubes, etc.) contained in the logic produced by any given modal graph (an exhaustiveness which was not possible before). In this paper we shall handle explicitly the classical case of the so-called 3(3)-modal graph (which is, among others, the one of S5), getting to a very elegant tetraicosahedronal geometrisation of this logic.