On dimensional rigidity of bar-and-joint frameworks

Let V={1,2,…,n}. A mapping p:V→R^r, where p¹,…,pⁿ are not contained in a proper hyper-plane is called an r-configuration. Let G=(V,E) be a simple connected graph on n vertices. Then an r-configuration p together with graph G, where adjacent vertices of G are constrained to stay the same distance apart, is called a bar-and-joint framework (or a framework) in R^r, and is denoted by G(p). In this paper we introduce the notion of dimensional rigidity of frameworks, and we study the problem of determining whether or not a given G(p) is dimensionally rigid. A given framework G(p) in R^r is said to be dimensionally rigid iff there does not exist a framework G(q) in R^s for s?r+1, such that ∥qⁱ-q^j∥²=∥pⁱ-p^j∥² for all (i,j)∈E. We present necessary and sufficient conditions for G(p) to be dimensionally rigid, and we formulate the problem of checking the validity of these conditions as a semidefinite programming (SDP) problem. The case where the points p¹,…,pⁿ of the given r-configuration are in general position, is also investigated.     

On the third largest Laplacian eigenvalue of a graph

In this article, a sharp lower bound for the third largest Laplacian eigenvalue of a graph is given in terms of the third largest degree of the graph.     

Coalgebraic representations of distributive lattices with operators

We present a framework for extending Stone's representation theorem for distributive lattices to representation theorems for distributive lattices with operators. We proceed by introducing the definition of algebraic theory of operators over distributive lattices. Each such theory induces a functor on the category of distributive lattices such that its algebras are exactly the distributive lattices with operators in the original theory. We characterize the topological counterpart of these algebras in terms of suitable coalgebras on spectral spaces. We work out some of these coalgebraic representations, including a new representation theorem for distributive lattices with monotone operators.     

Symmetric incidence groupoids

In [7] point-reflection geometries were studied which can be derived from commutative kinematic spaces without involutory elements. But the class of point-reflection geometries is larger. For example, elliptic planes with their reflections cannot be derived from commutative kinematic spaces. Here we investigate a larger class of reflection geometries.This paper was sponsored by Vigoni Program 1999.     

On the null-controllability of the heat equation in unbounded domains

We make two remarks about the null-controllability of the heat equation with Dirichlet condition in unbounded domains. Firstly, we give a geometric necessary condition (for interior null-controllability in the Euclidean setting) which implies that one cannot go infinitely far away from the control region without tending to the boundary (if any), but also applies when the distance to the control region is bounded. The proof builds on heat kernel estimates. Secondly, we describe a class of null-controllable heat equations on unbounded product domains. Elementary examples include an infinite strip in the plane controlled from one boundary and an infinite rod controlled from an internal infinite rod. The proof combines earlier results on compact manifolds with a new lemma saying that the null-controllability of an abstract control system and its null-controllability cost are not changed by taking its tensor product with a system generated by a non-positive self-adjoint operator.     

Sur les grands quotients partiels du développement en fraction continue

In this paper we obtain some metrics results about large partial quotients in the continued fraction expansion.     

Bayesian estimation of keyword confidence in Chinese Continuous speech recognition

In a syllable-based speaker-independent Chinese continuous speech recognition system based on classical Hidden Markov Model(HMM),a Bayesian approach of keyword confidence estimation is studied,which utilizes both acoustic layer scores and syllable-based statistical language model(LM) score.The Maximum a posteriori(MAP) confidence measure is proposed,and the forward-backward algorithm calculating the MAP confidence scores is deduced.The performance of the MAP confidence measure is evaluated in keyword spotting application and the experiment results show that the MAP confidence scores provide high discriminability for keyword candidates.Furthermore,the MAP confidence measure can be applied to various speech recognition applications.     

Laplacians and the Cheeger Inequality for Directed Graphs

We consider Laplacians for directed graphs and examine their eigenvalues. We introduce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then define a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems.Received September 8, 2004