Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem

We consider the problem of maintaining a dynamic ordered set of n integers in a universe U under the operations of insertion, deletion and predecessor queries. The computation model used is a unit-cost RAM, with a word length of w bits, and the universe size is |U|=2^w. We present a data structure that uses O(|U|/log|U|+n) space, performs all the operations in O(loglog|U|) time and needs O(loglog|U|/logloglog|U|) structural changes per update operation. The data structure is a simplified version of the van Emde Boas' tree introducing, in its construction and functioning, new concepts, which help to keep the important information for searching along the path of the tree, in a more compact and organized way.     

GLOUDS: Representing tree-like graphs

The Graph Level Order Unary Degree Sequence (GLOUDS) is a new succinct data structure for directed graphs that are “tree-like,” in the sense that the number of “additional” edges (w.r.t. a spanning tree) is not too high. The algorithmic idea is to represent a BFS-spanning tree of the graph (consisting of n nodes) with a well known succinct data structure for trees, named LOUDS, and enhance it with additional information that accounts for the non-tree edges. In practical tests, our data structure performs well for graphs containing up to $m=5n$ edges, while still having competitive running times for listing adjacent nodes.     

Symplectic structures on locally compact abelian groups and polarizations

LetX be a locally compact abelian group and ω(.,.) a symplectic structure on it. A polarization for (X, ω) is a pair of totally isotropic closed subgroupsG, G* ofX such thatX =G.G* and ω(.,.) defines a dual pairing ofG andG*. In this paper we describe a class of such groups which always admit a polarization and also discuss their structure. Dedicated to the memory of Professor K G Ramanathan     

调和复结构

利用向量丛值微分形式的调和理论来研究近复结构, 称之为调和复结构, 它是介于复结构与 K?hler结构之间的一种新结构.特别地,证明了S⁶上不允许此种结构.     

On finite reflexive homomorphism-homogeneous binary relational systems

A structure is called homogeneous if every isomorphism between finitely induced substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešet?il introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finitely induced substructures of the structure extends to an endomorphism of the structure.In this paper, we consider finite homomorphism-homogeneous relational systems with one reflexive binary relation. We show that for a large part of such relational systems (bidirectionally connected digraphs; a digraph is bidirectionally connected if each of its connected components can be traversed by ?-paths) the problem of deciding whether the system is homomorphism-homogeneous is coNP-complete. Consequently, for this class of relational systems there is no polynomially computable characterization (unless P=NP). On the other hand, in case of bidirectionally disconnected digraphs we present the full characterization. Our main result states that if a digraph is bidirectionally disconnected, then it is homomorphism-homogeneous if and only if it is either a finite homomorphism-homogeneous quasiorder, or an inflation of a homomorphism-homogeneous digraph with involution (a specific class of digraphs introduced later in the paper), or an inflation of a digraph whose only connected components are and .     

Homomorphism-Homogeneous Partially Ordered Sets

A structure is called homogeneous if every isomorphism between finite substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finite substructures of the structure extends to an endomorphism of the structure. In this paper we characterize homomorphism-homogeneous partially ordered sets (where a homomorphism between partially ordered sets A and B is a mapping f : A →B satisfying ). We show that there are five types of homomorphism-homogeneous partially ordered sets: partially ordered sets whose connected components are chains; trees; dual trees; partially ordered sets which split into a tree and a dual tree; and X ₅-dense locally bounded partially ordered sets. Supported by the Ministry od Science and Environmental Protection of the Republic of Serbia, Grant No. 144017.     

On certain locally homogeneous Clifford manifolds

Given a manifoldM, a Clifford structure of orderm onM is a family ofm anticommuting complex structures generating a subalgebra of dimension 2 ^m of End(T(M)). In this paper we investigate the existence of locally invariant Clifford structures of orderm2 on a class of locally homogeneous manifolds. We study the case of solvable extensions ofH-type groups, showing in particular that the solvable Lie groups corresponding to the symmetric spaces of negative curvature carry invariant Clifford structures of orderm2. We also show that for eachm and any finite groupF, there is a compact flat manifold with holonomy groupF and carrying a Clifford structure of orderm.Partially supported by Conicor (Argentina)Partially supported by grants from Conicet, Conicor, SECYTUNg (Argentina), and I.C.T.P. (Trieste)Partially supported by grants from Conicet, Conicor, SECYTUNC (Argentina), T.W.A.S and I.C.T.P. (Trieste)     

On the Number of Non-Hamiltonian Graphs

In this paper, maximal non-Hamiltonian graphs ( MNH graphs), i.e., non-Hamiltonian graphs such that the addition of any new edge violates their property of being non-Hamiltonian are studied. It is shown that the study of MNH graphs can be reduced to the study of the so-called simplified MNH graphs. Restrictions on the structure of maximal cliques of simplified MNH graphs are obtained, the orders and the number of such graphs are estimated.     

Dirichlet regularity in arbitrary o‐minimal structures on the field ℝ up to dimension 4

In this article we show that the set of Dirichlet regular boundary points of a bounded domain of dimension up to 4, definable in an arbitrary o‐minimal structure on the field ?, is definable in the same structure. Moreover we give estimates for the dimension of the set of non‐regular boundary points, depending on whether the structure is polynomially bounded or not. This paper extends the results from the author's Ph.D. thesis [6, 7] where the problem was solved for polynomially bounded o‐minimal structures expanding the real field. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A coradiant based scalarization to characterize approximate solutions of vector optimization problems with variable ordering structures

This paper investigates some properties of approximate efficiency in variable ordering structures where the variable ordering structure is given by a special set valued map. We characterize $\epsilon$-minimal and $\epsilon$- nondominated elements as approximate solutions of a multiobjective optimization problem with a variable ordering structure and give necessary and sufficient conditions for these solutions, via scalarization.     

On the path representation of networks

A compact data structure for networks is obtained by storing arcs of paths sequentially. This structure allows forward and backward access from a node to its neighbors.     

调和复结构

利用向量从值微分形式的调和理论来研究近复结构,称之为调和复结构,它是介于复结构与K(a)hler结构之间的一种新结构.特别地,证明了S~6上不允许此种结构.     

Tight contact structures via dynamics

We consider the problem of realizing tight contact structures on closed orientable three-manifolds. By applying the theorems of Hofer et al., one may deduce tightness from dynamical properties of (Reeb) flows transverse to the contact structure. We detail how two classical constructions, Dehn surgery and branched covering, may be performed on dynamically-constrained links in such a way as to preserve a transverse tight contact structure.

     

Geometric angle structures on triangulated surfaces

In this paper we characterize the edge invariant and Delaunay invariant of a spherical angle structure on a triangulated surface. We also characterize the edge invariant of a hyperbolic angle structure on a triangulated surface.

     

Pin c and Lipschitz Structures on Products of Manifolds

The topological condition for the existence of a pin ^c structure on the product of two Riemannian manifoldsis derived and applied to construct examples of manifolds havingthe weaker Lipschitz structure, but no pin ^c structure.An example of a five-dimensional manifold with this property is given;it is pointed out that there are no manifolds of lower dimension withthis property.     

Basic structures on derived critical loci

We review the derived algebraic geometry of derived zero loci of sections of vector bundles, with particular emphasis on derived critical loci. In particular we some of the structures carried by derived critical loci: the homotopy Batalin-Vilkovisky structure, the action of the 2-monoid of the self-intersection of the zero section, and the derived symplectic structure of degree −1. We also show how this structure exists, more generally, on derived lagrangian intersections inside a symplectic algebraic manifold.     

Über eine gemeinsame verallgemeinerung endlicher affiner ebenen und MDS-codes mit anwendung in der versuchsplanung

The definition of the structure T(t, q, r, n), a common generalisation of affine planes, MDS-codes, Laguerre- and Minkowski-m-structures, is simplified. Furthermore, every T-structure constructed by nearfields (disregarding isomorphism) is characterized by a new rectangle-axiom connected with the diagonal-axiom.