Density of the Medvedev lattice of Π<Superscript>0</Superscript><Subscript>1</Subscript> classes

The partial ordering of Medvedev reducibility restricted to the family of ⁰₁ classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a ⁰₁ class, which we call a ``c.e. separating class'. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes. Mathematics Subject Classification (2000): 03D30, 03D25     

Embeddings into the Medvedev and Muchnik lattices of Π<Superscript>0</Superscript><Subscript>1</Subscript> classes

Let _w and _M be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty ₁⁰ subsets of 2, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of _w. We show that many countable distributive lattices are lattice-embeddable below any non-zero element of _M.Simpsons research was partially supported by NSF Grant DMS-0070718. We thank the anonymous referee for a careful reading of this paper and helpful comments.     

Seas of squares with sizes from a Π<Stack><Subscript>1</Subscript><Superscript>0</Superscript></Stack> set

A family of sets is union-free if there are no three distinct sets in the family such that the union of two of the sets is equal to the third set. Kleitman proved that every union-free family has size at most (1+o(1))( _n/2 ⁿ ). Later, Burosch–Demetrovics–Katona–Kleitman–Sapozhenko asked for the number α(n) of such families, and they proved that \({2^{\left( {\begin{array}{*{20}{c}} n \\ {n/2} \end{array}} \right)}} \leqslant \alpha \left( n \right) \leqslant {2^{2\sqrt 2 \left( {\begin{array}{*{20}{c}} n \\ {n/2} \end{array}} \right)\left( {1 + o\left( 1 \right)} \right)}}\) They conjectured that the constant \(2\sqrt 2 \) can be removed in the exponent of the right-hand side. We prove their conjecture by formulating a new container-type theorem for rooted hypergraphs.     

Local structure of Rogers semilattices of Σ<Subscript>n</Subscript><Superscript>0</Superscript>-computable numberings

We deal in specific features of the algebraic structure of Rogers semilattices of _n ⁰-computable numberings, for n 2. It is proved that any Lachlan semilattice is embeddable (as an ideal) in such every semilattice, and that over an arbitrary non 0-principal element of such a lattice, any Lachlan semilattice is embeddable (as an interval) in it.Supported by INTAS grant No. 00-499, by FP Universities of Russia grant UR.04.01.013, and by the Grant Center for Fundamental Research (GCFR), project PD02-1.1-475.__________Translated from Algebra i Logika, Vol. 44, No. 2, pp. 148–172, March–April, 2005.     

The Δ<Superscript>0</Superscript><Subscript><Emphasis Type="Italic">α</Emphasis></Subscript>-Computable Enumerations of the Classes of Projective Planes

Studying computable representations of projective planes, for the classes K of pappian, desarguesian, and all projective planes, we prove that K ^c /? admits no hyperarithmetical Friedberg enumeration and admits a Friedberg Δ⁰_α+3-computable enumeration up to a Δ⁰ _α -computable isomorphism.     

Containment of c<Subscript>0</Subscript> and ℓ<Subscript>1</Subscript> in π<Subscript>1</Subscript>(<Emphasis Type="Italic">E,F</Emphasis>)

Suppose π₁(E, F) is the space of all absolutely 1-summing operators between two Banach spacesE andF. We show that ifF has a copy of c₀, then π₁ (E, F) will have a copy of c₀, and under some conditions ifE has a copy of ℓ₁ then π₁ (E, F) would have a complemented copy of ℓ₁.     

Spin structures and spectra of ℤ<Subscript>2</Subscript><Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>-manifolds

We give necessary and sufficient conditions for the existence of pin^± and spin structures on Riemannian manifolds with holonomy group ₂^k. For any n4 (resp. n6) we give examples of pairs of compact manifolds (resp. compact orientable manifolds) M₁, M₂, non homeomorphic to each other, that are Laplace isospectral on functions and on p-forms for any p and such that M₁ admits a pin^± (resp. spin) structure whereas M₂ does not.Mathematics Subject Classification (2000):58J53, 57R15, 20H15Partially supported by Conicet and grants from SecytUNC, Foncyt and AgCba.     

A Ring Theoretic Construction of Hadamard Difference Sets in ℤ<Subscript>8</Subscript><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>×ℤ<Subscript>2</Subscript><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

Let be the Galois ring of characteristic 2³ and rank n and let . We give an explicit construction of Hadamard difference sets in .}Research supported by NSA grant MDA 904-02-1-0080.     

A Hilbert-type theorem for spacelike surfaces with constant Gaussian curvature in ℍ<Superscript>2</Superscript> × ℝ<Subscript>1</Subscript>

There are examples of complete spacelike surfaces in the Lorentzian product ℍ² × ℝ₁ with constant Gaussian curvature K ≤ −1. In this paper, we show that there exists no complete spacelike surface in ℍ² × ℝ₁ with constant Gaussian curvature K > −1.     

Biflatness of ℓ<Superscript>1</Superscript>-Semilattice Algebras

We show that if L is a semilattice then the ℓ¹-convolution algebra of L is biflat precisely when L is "uniformly locally finite". Our proof technique shows in passing that if this convolution algebra is biflat then it is isomorphic as a Banach algebra to the Banach space ℓ¹(L) equipped with pointwise multiplication. At the end we sketch how these techniques may be extended to prove an analogous characterisation of biflatness for Clifford semigroup algebras.     

Conformally flat Lorentzian hypersurfaces in ℝ<Stack><Subscript>1</Subscript><Superscript>4</Superscript></Stack> with three distinct principal curvatures

A three dimensional Lorentzian hypersurface x: M ₁ ³ → ? ₁ ⁴ is called conformally flat if its induced metric is conformal to the flat Lorentzian metric, and this property is preserved under the conformal transformation of ? ₁ ⁴ . Using the projective light-cone model, for those whose shape operators have three distinct real eigenvalues, we calculate the integrability conditions by constructing a scalar conformal invariant and a canonical moving frame in this paper. Similar to the Riemannian case, these hypersurfaces can be determined by the solutions to some system of partial differential equations.     

Stabilization of Linear Switched Delay Systems: ℋ<Subscript>2</Subscript> and ℋ<Subscript>∞</Subscript> Methods

This paper presents new results pertaining to the delay-dependent stability and control synthesis of a class of linear switched continuous-time systems with time-varying delays. A new state transformation is introduced to exhibit the delay-dependent dynamics in the slow-time scale. For stability, we construct an appropriate selective Lyapunov functional to derive delay-dependent LMI-based sufficient conditions under arbitrary switching and without relying to overbounding. For the control synthesis, we design switched feedback schemes based on quadratic ℋ₂, ℋ_∞ and simultaneous ℋ₂/ℋ_∞ performance criteria. Under the developed transformation, it is established that both the instantaneous and delayed feedback control yield identical results. Numerical examples are presented to illustrate the analytical development.     

Topological recursion relation for <Emphasis Type="Italic">ψ</Emphasis><Subscript>1</Subscript><Emphasis Type="Italic">ψ</Emphasis><Subscript>2</Subscript> in

We give the definition of the full potential with descendants, which is a genus expansion of the Barannikov-Kontsevich solution of the WDVV equation. This potential satisfies the Getzler relation, which comes from the geometry of the moduli space of curves Open image in new window .     

Cuts,Trees and ℓ<Subscript>1</Subscript>-Embeddings of Graphs*

Motivated by many recent algorithmic applications, this paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred when the graph is embedded into ₁ space. The main results are:1. Explicit constant-distortion embeddings of all series-parallel graphs, and all graphs with bounded Euler number. These are the first natural families known to have constant distortion (strictly greater than 1). Using the above embeddings, algorithms are obtained which approximate the sparsest cut in such graphs to within a constant factor.2. A constant-distortion embedding of outerplanar graphs into the restricted class of ₁-metrics known as dominating tree metrics. A lower bound of (log n) on the distortion for embeddings of series-parallel graphs into (distributions over) dominating tree metrics is also presented. This shows, surprisingly, that such metrics approximate distances very poorly even for families of graphs with low treewidth, and excludes the possibility of using them to explore the finer structure of ₁-embeddability.* A preliminary version of this work appeared in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 399–408. This work was done while the author was at the University of California, Berkeley. Supported in part by NSF grants CCR-9505448 and CCR-9820951.     

Multi-self-similar Markov processes on ℝ<Subscript>+</Subscript><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> and their Lamperti representations

 A classical result, due to Lamperti, establishes a one-to-one correspondence between a class of strictly positive Markov processes that are self-similar, and the class of one-dimensional Lévy processes. This correspondence is obtained by suitably time-changing the exponential of the Lévy process. In this paper we generalise Lamperti's result to processes in n dimensions. For the representation we obtain, it is essential that the same time-change be applied to all coordinates of the processes involved. Also for the statement of the main result we need the proper concept of self-similarity in higher dimensions, referred to as multi-self-similarity in the paper. The special case where the Lévy process ξ is standard Brownian motion in n dimensions is studied in detail. There are also specific comments on the case where ξ is an n-dimensional compound Poisson process with drift. Finally, we present some results concerning moment sequences, obtained by studying the multi-self-similar processes that correspond to n-dimensional subordinators. Received: 22 August 2002 / Revised version: 10 February 2003 Published online: 15 April 2003 RID="*" ID="*" MaPhySto – Centre for Mathematical Physics and Stochastics, funded by a grant from the Danish National Research Foundation Mathematics Subject Classification (2000): 60G18, 60G51, 60J25, 60J60, 60J75 Key words or phrases: Lévy process – Self-similarity – Time-change – Exponential functional – Brownian motion – Bessel process – Piecewise deterministic Markov process – Moment sequence     

Aut0(Λ<Superscript>2</Superscript>)-symmetrical 4-extensions of the 2-dimensional grid Λ<Superscript>2</Superscript>

There are different non-equivalent definitions of attractors in the theory of dynamical systems. The most common are two definitions: the maximal attractor and the Milnor attractor. The maximal attractor is by definition Lyapunov stable, but it is often in some ways excessive. The definition of Milnor attractor is more realistic from the physical point of view. The Milnor attractor can be Lyapunov unstable though. One of the central problems in the theory of dynamical systems is the question of how typical such a phenomenon is. This article is motivated by this question and contains new examples of so-called relatively unstable Milnor attractors. Recently I. Shilin has proved that these attractors are Lyapunov stable in the case of one-dimensional fiber under some additional assumptions. However, the question of their stability in the case of multidimensional fiber is still an open problem.     

On complexity reduction of Σ<Subscript>1</Subscript> formulas

 For a fixed q  ℕ and a given Σ₁ definition φ(d,x), where d is a parameter, we construct a model M of 1 Δ₀ + ? exp and a non standard d  M such that in M either φ has no witness smaller than d or phgr; is equivalent to a formula ϕ(d,x) having no more than q alternations of blocks of quantifiers. Received: 29 September 1998 / Revised version: 7 November 2001 Published online: 10 October 2002 RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13. RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13.     

Discrete subgroups of <Emphasis Type="Italic">PU</Emphasis> (2, 1) acting on P<Stack><Subscript>ℂ</Subscript><Superscript>2</Superscript></Stack> and the Kobayashi metric

In this paper, we prove following: If G ⊂ PU (2, 1) is an infinite, discrete group, acting on P_ℂ² without complex invariant lines, then the component containing ℍP_ℂ² of the domain of discontinuity Ω(G) = PP_ℂ²∖ Λ (G), according to Kulkarni, is G-invariant complete Kobayashi hyperbolic. The authors were supported by the Universidad Autónoma de Yucatán and the Universidad Nacional Autónoma de México.