Region-Fault Tolerant Geometric Spanners

We introduce the concept of region-fault tolerant spanners for planar point sets and prove the existence of region-fault tolerant spanners of small size. For a geometric graph on a point set P and a region F, we define to be what remains of after the vertices and edges of intersecting F have been removed. A  -fault tolerant t-spanner is a geometric graph  on P such that for any convex region F, the graph is a t-spanner for , where is the complete geometric graph on P. We prove that any set P of n points admits a -fault tolerant (1+ε)-spanner of size for any constant ε>0; if adding Steiner points is allowed, then the size of the spanner reduces to  , and for several special cases, we show how to obtain region-fault tolerant spanners of size without using Steiner points. We also consider fault-tolerant geodesic t -spanners: this is a variant where, for any disk D, the distance in between any two points u,v∈P∖D is at most t times the geodesic distance between u and v in ℝ²∖D. We prove that for any P, we can add Steiner points to obtain a fault-tolerant geodesic (1+ε)-spanner of size  . M.A. Abam was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 612.065.307 and by the MADALGO Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation. M. de Berg was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301. M. Farshi was supported by Ministry of Science, Research and Technology of I.R. Iran. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.     

On the Number of Topological Types Occurring in a Parameterized Family of Arrangements

Let be an o-minimal structure over ℝ, a closed definable set, and

Compact and Finite Rank Perturbations of Closed Linear Operators and Relations in Hilbert Spaces

For closed linear operators or relations A and B acting between Hilbert spaces and the concepts of compact and finite rank perturbations are defined with the help of the orthogonal projections P _A and P _B in onto the graphs of A and B. Various equivalent characterizations for such perturbations are proved and it is shown that these notions are a natural generalization of the usual concepts of compact and finite rank perturbations. Sadly, our colleague and friend Peter Jonas passed away on July, 18th 2007.     

<Emphasis Type="Italic">F</Emphasis>-isocristaux surconvergents et surcohérence différentielle

Résumé Soient un anneau de valuation discrète complet d’inégales caractéristiques, de corps résiduel parfait k, un -schéma formel propre et lisse, T un diviseur de la fibre spéciale P de , U l’ouvert de P complémentaire de T, Y un sous-k-schéma fermé lisse de U. Nous prouvons que la catégorie des F-isocristaux surconvergents sur Y est équivalente à celle des F-isocristaux surcohérents sur Y (voir [Car, 6.2.1 et 6.4.3.a)]). Plus généralement, nous établissons par recollement une telle équivalence pour tout k-schéma séparé lisse Y. Nous vérifions de plus que les F-complexes de -modules à cohomologie bornée et -surcohérente se dévissent en F-isocristaux surconvergents.     

Primitive Ideals and Automorphisms of Quantum Matrices

Let be a field and q be a nonzero element of that is not a root of unity. We give a criterion for 〈0〉 to be a primitive ideal of the algebra of quantum matrices. Next, we describe all height one primes of ; these two problems are actually interlinked since it turns out that 〈0〉 is a primitive ideal of whenever has only finitely many height one primes. Finally, we compute the automorphism group of in the case where m ≠ n. In order to do this, we first study the action of this group on the prime spectrum of . Then, by using the preferred basis of and PBW bases, we prove that the automorphism group of is isomorphic to the torus when m ≠ n and (m,n) ≠ (1, 3),(3, 1). This research was supported by a Marie Curie Intra-European Fellowship within the 6th European Community Framework Programme and by Leverhulme Research Interchange Grant F/00158/X.     

Constructions of p-ary Quadratic Bent Functions

Bent functions have many applications in the fields of coding theory, communications and cryptography. This paper studies the constructions of bent functions having the form for odd n and for even n, over the finite field of odd characteristic p, where . Based on the irreducibility of some polynomials on , we focus on characterizing the bent functions for n=p ^v q ^r and n=2p ^v q ^r , where is an odd prime and p a primitive root modulo q ². Moreover, the enumerations of those functions are also considered. Partially supported by the NSF of China under Grants No. 60603012 and No. 60573053.     

Matching Points with Squares

Given a class of geometric objects and a point set P, a -matching of P is a set of elements of such that each C _i contains exactly two elements of P and each element of P lies in at most one C _i . If all of the elements of P belong to some C _i , M is called a perfect matching. If, in addition, all of the elements of M are pairwise disjoint, we say that this matching M is strong. In this paper we study the existence and characteristics of -matchings for point sets in the plane when is the set of isothetic squares in the plane. A consequence of our results is a proof that the Delaunay triangulations for the L _∞ metric and the L ₁ metric always admit a Hamiltonian path.     

Base subsets of symplectic Grassmannians

Let V and V′ be 2n-dimensional vector spaces over fields F and F′. Let also Ω: V× V→ F and Ω′: V′× V′→ F′ be non-degenerate symplectic forms. Denote by Π and Π′ the associated (2n−1)-dimensional projective spaces. The sets of k-dimensional totally isotropic subspaces of Π and Π′ will be denoted by and ${\mathcal G}'_{k}$, respectively. Apartments of the associated buildings intersect and by so-called base subsets. We show that every mapping of to sending base subsets to base subsets is induced by a symplectic embedding of Π to Π′.     

Shellable Complexes and Topology of Diagonal Arrangements

We prove that if a simplicial complex Δ is shellable, then the intersection lattice L _Δ for the corresponding diagonal arrangement is homotopy equivalent to a wedge of spheres. Furthermore, we describe precisely the spheres in the wedge, based on the data of shelling. Also, we give some examples of diagonal arrangements  where the complement is K(π,1), coming from rank-3 matroids. This work forms part of the author’s doctoral dissertation at the University of Minnesota, supervised by Vic Reiner, and partially supported by NSF grant DMS-0245379.     

On the relation of Voevodsky’s algebraic cobordism to Quillen’s <Emphasis Type="Italic">K</Emphasis>-theory

Quillen’s algebraic K-theory is reconstructed via Voevodsky’s algebraic cobordism. More precisely, for a ground field k the algebraic cobordism P¹-spectrum MGL of Voevodsky is considered as a commutative P¹-ring spectrum. Setting we regard the bigraded theory MGL ^p,q as just a graded theory. There is a unique ring morphism which sends the class [X]_MGL of a smooth projective k-variety X to the Euler characteristic of the structure sheaf . Our main result states that there is a canonical grade preserving isomorphism of ring cohomology theories

On Some Properties of Randomly Indexed Sequences of Random Elements

Let be a probability space with a nonatomic measure P and let (S,ρ) be a separable complete metric space. Let {N _n ,n≥1} be an arbitrary sequence of positive-integer valued random variables. Let {F _k ,k≥1} be a family of probability laws and let X be some random element defined on and taking values in (S,ρ). In this paper we present necessary and sufficient conditions under which one can construct an array of random elements {X _n,k ,n,k≥1} defined on the same probability space and taking values in (S,ρ), and such that , and moreover as  n→∞. Furthermore, we consider the speed of convergence to X as n→∞.      

Chains and antichains in partial orderings

We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is or , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two sets. Our main result is that there is a computably axiomatizable theory K of partial orderings such that K has a computable model with arbitrarily long finite chains but no computable model with an infinite chain. We also prove the corresponding result for antichains. Finally, we prove that if a computable partial ordering has the feature that for every , there is an infinite chain or antichain that is relative to , then we have uniform dichotomy: either for all copies of , there is an infinite chain that is relative to , or for all copies of , there is an infinite antichain that is relative to .     

Formality Theorem with Coefficients in a Module

In this paper, X will denote a manifold. In a very famous paper, Kontsevich [Ko] showed that the differential graded Lie algebra (DGLA) of polydifferential operators on X is formal. Calaque [C1] extended this theorem to any Lie algebroid. More precisely, given any Lie algebroid E over X, he defined the DGLA of E-polydifferential operators, and showed that it is formal. Denote by the DGLA of E-polyvector fields. Considering M, a module over E, we define the-module of E-polyvector fields with values in M. Similarly, we define the-module of E-polydifferential operators with values in M,. We show that there is a quasi-isomorphism of L _∞-modules over from to . Our result extends Calaque’s (and Kontsevich’s) result.     

A Functorial Framework for Constraint Normal Logic Programming

The semantic constructions and results for definite programs do not extend when dealing with negation. The main problem is related to a well-known problem in the area of algebraic specification: if we fix a constraint domain as a given model, its free extension by means of a set of Horn clauses defining a set of new predicates is semicomputable. However, if the language of the extension is richer than Horn clauses its free extension (if it exists) is not necessarily semicomputable. In this paper we present a framework that allows us to deal with these problems in a novel way. This framework is based on two main ideas: a reformulation of the notion of constraint domain and a functorial presentation of our semantics. In particular, the semantics of a logic program P is defined in terms of three functors: that apply to constraint domains and provide the operational, the least fixpoint and the logical semantics of P, respectively. To be more concrete, the idea is that the application of to a specific constraint solver provides the operational semantics of P that uses this solver; the application of to a specific domain provides the least fixpoint of P over this domain; and, the application of to a theory of constraints provides the logic theory associated to P. In this context, we prove that these three functors are in some sense equivalent.      

Invariant subspaces for operators in a general II<Subscript>1</Subscript>-factor

Let ℳ be a von Neumann factor of type II₁ with a normalized trace τ. In 1983 L. G. Brown showed that to every operator T∈ℳ one can in a natural way associate a spectral distribution measure μ _T (now called the Brown measure of T), which is a probability measure in ℂ with support in the spectrum σ(T) of T. In this paper it is shown that for every T∈ℳ and every Borel set B in ℂ, there is a unique closed T-invariant subspace affiliated with ℳ, such that the Brown measure of is concentrated on B and the Brown measure of is concentrated on ℂ∖B. Moreover, is T-hyperinvariant and the trace of is equal to μ _T(B). In particular, if T∈ℳ has a Brown measure which is not concentrated on a singleton, then there exists a non-trivial, closed, T-hyperinvariant subspace. Furthermore, it is shown that for every T∈ℳ the limit exists in the strong operator topology, and the projection onto is equal to 1_[0,r](A), for every r>0. Supported by The Danish National Research Foundation.     

A Relation Between Closure Operators on a Small Category and Its Category of Presheaves

In this paper we show that each factorization structure on a small category , satisfying certain conditions, yields a presheaf on and a morphism of presheaves . We then give connections, and set up one to one correspondences, between subclasses of the following classes: (a) closure operators on (b) subobjects of (c) morphisms from to (d) weak Lawvere–Tierney topologies (e) weak Grothendieck topologies (f) closure operators on .     

Transversality and Lefschetz numbers for foliation maps

Let be a smooth foliation on a closed Riemannian manifold M, and let Λ be a transverse invariant measure of . Suppose that Λ is absolutely continuous with respect to the Lebesgue measure on smooth transversals. Then a topological definition of the Λ-Lefschetz number of any leaf preserving diffeomorphism is given. For this purpose, standard results about smooth approximation and transversality are extended to the case of foliation maps. It is asked whether this topological Λ-Lefschetz number is equal to the analytic Λ-Lefschetz number defined by Heitsch and Lazarov, which would be a version of the Lefschetz trace formula. Heitsch and Lazarov have shown such a trace formula when the fixed point set is transverse to . Dedicated to V. I. Arnold