Crystal algebra

We define the crystal algebra, an algebra which has a base of elements of crystal bases of a quantum group. The multiplication is defined by the tensor product rule of crystal bases. A universal n-colored crystal algebra is defined. We study the relation between those algebras and the tensor algebras of the crystal algebra of U _q (sl(2)) and give a presentation by generators and relations for the case of U _q (sl(n)).     

One-dimensional perturbations of the shift

The structure of isometries on a Hilbert space are well studied. In this paper we study contractions which are one-dimensional perturbations of isometries, in particular, perturbations of the shift operator onH ².     

A Bound on the Total Chromatic Number

. The proof is probabilistic. Received: November 26, 1996     

On the distance to uncontrollability and the distance to instability and their relation to some condition numbers in control

Summary. According to the methodology of [6], many measures of distance arising in problems in numerical linear algebra and control can be bounded by a factor times the reciprocal of an appropriate condition number, where the distance is thought of as the distance between a given problem to the nearest ill-posed problem. In this paper, four major problems in numerical linear algebra and control are further considered: the computation of system Hessenberg form, the solution of the algebraic Riccati equation, the pole assignment problem and the matrix exponential. The distances considered here are the distance to uncontrollability and the distance to instability. Received November 4, 1995 / Revised version received March 4, 1996     

A Bahadur efficiency comparison between one and two sample rank statistics and their sequential rank statistic analogues

One and two sample rank statistics are shown in general to be more efficient in the Bahadur sense than their sequential rank statistic analogues as defined by Mason (1981, Ann. Statist.9 424–436) and Lombard (1981, South African Statist. J.15 129–152), even though the two families of statistics (those based on full ranks and those based on sequential ranks) have the same Pitman efficiency against local alternatives. In the process, general results on large deviation probabilities and laws of large numbers for statistics based on sequential ranks are obtained.     

What must and what need not be contained in a graph of uncountable chromatic number?

We investigate the following problem: What countable graphs must a graph of uncountable chromatic number contain? We define two graphsΓ andΔ which are very similar and we show thatΓ is contained in every graph of uncountable chromatic number, whileΔ is (consistently) not.     

Additivity of the crossing number of graphs with connectivity 2

We prove that the crossing number of graphs with connectivity 2 has in certain cases an additive property analogous to that of crossing number of graphs with connectivity ≤1.     

Rates of convergence of random walk on distance regular graphs

When run on any non-bipartite q-distance regular graph from a family containing graphs of arbitrarily large diameter d, we show that d steps are necessary and sufficient to drive simple random walk to the uniform distribution in total variation distance, and that a sharp cutoff phenomenon occurs. For most examples, we determine the set on which the variation distance is achieved, and the precise rate at which it decays. The upper bound argument uses spectral methods – combining the usual Cauchy-Schwarz bound on variation distance with a bound on the tail probability of a first-hitting time, derived from its generating function. Received: 2 April 1997 / Revised version: 10 May 1998     

Detecting embedded pure network structures in LP problems

Recently, linear programming problems with special structures have assumed growing importance in mathematical programming. It is well known that exploiting network structures within linear programs can lead to considerable improvement of the computational solution of large-scale linear programming problems. A linear program is said to contain an embedded network structure provided that some subset of its constraints can be interpreted as specifying conservation of flow. If a column of the constraint matrix has at most two non-zeros, then it leads to embedded generalized network structure and if these non-zeros are unit elements and of opposite signs, then it leads to embedded pure network structure. In this paper, we are concerned with algorithms for detecting embedded pure network structures within linear programs. The network extraction methods are presented in two groups. The first group covers deletion and addition based algorithms and the second group covers GUB based algorithms. We have extended the GUB based algorithm appearing in the second group by introducing Markowitz merit count approach for exploiting matrix non zeros. A set of well known test problems has been used to carry out computational experiments which show that our extensions to the GUB based algorithms give better results than the algorithms reported earlier.