Vertex coloring acyclic digraphs and their corresponding hypergraphs

We consider vertex coloring of an acyclic digraph in such a way that two vertices which have a common ancestor in receive distinct colors. Such colorings arise in a natural way when bounding space for various genetic data for efficient analysis. We discuss the corresponding down-chromatic number and derive an upper bound as a function of , the maximum number of descendants of a given vertex, and the degeneracy of the corresponding hypergraph. Finally, we determine an asymptotically tight upper bound of the down-chromatic number in terms of the number of vertices of and .     

Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems

A complete classification of the computational complexity of the fixed-point existence problem for Boolean dynamical systems, i.e., finite discrete dynamical systems over the domain {0, 1}, is presented. For function classes and graph classes , an ()-system is a Boolean dynamical system such that all local transition functions lie in and the underlying graph lies in . Let be a class of Boolean functions which is closed under composition and let be a class of graphs which is closed under taking minors. The following dichotomy theorems are shown: (1) If contains the self-dual functions and contains the planar graphs, then the fixed-point existence problem for ()-systems with local transition function given by truth-tables is NP-complete; otherwise, it is decidable in polynomial time. (2) If contains the self-dual functions and contains the graphs having vertex covers of size one, then the fixed-point existence problem for ()-systems with local transition function given by formulas or circuits is NP-complete; otherwise, it is decidable in polynomial time.      

Generalized doubling meets Poincaré

We establish a modified segment inequality on metric spaces that satisfy a generalized volume doubling property. This leads to Sobolev and Poincaré inequalities for such spaces. We also give several examples of spaces that satisfy the generalized doubling condition.     

Isomorphism of Coloured Graphs with Slowly Increasing Multiplicity of Jordan Blocks

n -vertex edge coloured graphs with multiplicity of Jordan blocks bounded by k can be done in time . Received: November 29, 1994     

Weighted Bergman spaces¶associated with causal symmetric spaces

Let H\G be a causal symmetric space sitting inside its complexification H _ℂ\G _ℂ. Then there exist certain G-invariant Stein subdomains Ξ of H _ℂ\G _ℂ. The Haar measure on H _ℂ\G _ℂ gives rise to a G-invariant measure on Ξ. With respect to this measure one can define the Bergman space B ²(Ξ) of square integrable holomorphic functions on Ξ. The group G acts unitarily on the Hilbert space B ²(Ξ) by left translations in the arguments. The main result of this paper is the Plancherel Theorem for B ²(Ξ), i.e., the disintegration formula for the left regular representation into irreducibles. Received: Received: 23 November 1998     

Exact asymptotics of the characteristic polynomial of the symmetric Pascal matrix

We have obtained the exact asymptotics of the determinant . Inverse symbolic computing methods were used to obtain exact analytical expressions for all terms up to relative order L⁻¹⁴ to the leading term. This determinant is known to give weighted enumerations of cyclically symmetric plane partitions, weighted enumerations of certain families of vicious walkers and it has been conjectured to be proportional to the one point function of the O(1) loop model on a cylinder of circumference L. We apply our result to the loop model and give exact expressions for the asymptotics of the average of the number of loops surrounding a point and the fluctuation in this number. For the related bond percolation model at the critical point, we give exact expressions for the asymptotics of the probability that a point is on a cluster that wraps around a cylinder of even circumference and the probability that a point is on a cluster spanning a cylinder of odd circumference.     

Extremal positive and self-adjoint extensions of suboperators

This work is supported in part by the fund OTKA (No. 5-134).     

Pompeiu sets in compact Heisenberg manifolds

A necessary and sufficient condition is presented for a set to be a Pompeiu subset of any compact homogeneous space with a finite invariant measure. The condition, which is expressed in terms of the intertwining operators of each primary summand of the quasi-regular representation, is then interpreted in the case of the compact Heisenberg manifolds. Examples are presented demonstrating that the condition to be Pompeiu in these manifolds is quite different from the corresponding condition for a torus of the same dimension. This provides a contrast with the existing comparison between the Heisenberg group itself and Euclidean space in terms of Pompeiu sets. In addition, the closed linear span of all translates of any square integrable function on any compact homogeneous space is determined.