Hilbert bases of cuts

Let X be a set of vectors in R^m. X is said to be a Hilbert base if every vector in R^m which can be written both as a linear combination of members of X with nonnegative coefficients and as a linear combination with integer coefficients can also be written as a linear combination with nonnegative integer coefficients. Denote by H the collection of the graphs whose family of cuts is a Hilbert base. It is known that K₅ and graphs with no K₅-minor belong to H and that K₆ does not belong to H. We show that every proper subgraph of K₆ belongs to H and that every graph from H does not have K₆ as a minor. We also study how the class H behaves under several operations.     

Using Complex Integration to Compute Multivariate Normal Probabilities

Abstract

The execution of most multiple comparison methods involves, at least in part, the computation of the probability that a multivariate normal or multivarite t random vector is in a hyper-rectangle. In multiple comparison with a control as well as multiple comparison with the best (of normal populations or multinomial cell probabilities), the correlation matrix R of the random vector is nonsingular and of the form , where D is a diagonal matrix and is a known vector. It is well known that, in this case, the multivariate normal rectangular probability can be expressed as a one-dimensional integral and successfully computed using Gaussian quadrature techniques. However, in multiple comparison with the mean (sometimes called analysis of means) of normal distributions, all-pairwise comparisons of three normal distributions, as well as simultaneous inference on multinomial cell probabilities themselves, the correlation matrix is singular and of the form . It is not well known that, in this latter case, the multivariate normal rectangular probability can still be expressed as a single integral, albeit one with complex variables in its integrand. Previously published proofs of the validity of this expression either contained a gap or relied on a numerical demonstration, and this article will provide an analytic proof. Furthermore, we explain how this complex integral can be computed accurately, using Romberg integration of complex variables when the dimension is low, and using ?idák's inequality as an approximation when the dimension is at least moderate.     

Networks with small stretch number

In a previous work, the authors introduced the class of graphs with bounded induced distance of order k (BID(k) for short), to model non-reliable interconnection networks. A network modeled as a graph in BID(k) can be characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between these nodes in the faulty graph is at most k times the distance in the non-faulty graph. The smallest k such that GBID(k) is called stretch number of G. We show an odd characteristic of the stretch numbers: every rational number greater or equal 2 is a stretch number, but only discrete values are admissible for smaller stretch numbers. Moreover, we give a new characterization of classes BID(2−1/i), i1, based on forbidden induced subgraphs. By using this characterization, we provide a polynomial time recognition algorithm for graphs belonging to these classes, while the general recognition problem is Co-NP-complete.     

Lp - Logistic discrimination

The paper presents L_p-solution for logistic discriminant function in dichotomous as well as in the polychotomous problem.     

More examples on ordered set reconstruction

We show that there are nonisomorphic ordered sets P and Q that have the same maximal and minimal decks and a rank k such that there is a map B from the elements of rank k in P to the elements of rank k in Q such that P{x} is isomorphic to Q{B(x)} for all x of rank k in P. The examples are preceded by a criterion as to when two nonisomorphic ordered sets will have a rank k and a map B as above.     

全矩阵环上理想包含图的自同构群

设R是一个环,其上的理想包含图,记为Γ_I(R),是一个有向图,它以R的非平凡左理想为顶点,从R的左理想I_1到I_2有一条有向边当且仅当I_1真包含于I_2.环R上的理想关系图,记为Γ_i(R),也是一个有向图,它以R为顶点集,从R中元素A到B有一条有向边当且仅当A生成的左理想真包含于B生成的左理想.设F_q为有限域,其上n阶全矩阵环记为M_n(F_q),本文刻画了环M_n(F_q)上的理想包含图以及理想关系图的任意自同构.     

Recurrences and formulae in an extension of the Eulerian numbers

In this paper, the author develops a general formula for numbers which are extensions of the Eulerian numbers. A_m ^tn, r) is defined to be the number of n-permutations with r rises of magnitude at least m. Intermediate steps in the derivation include a vertical recurrence relation. recurrence relations of the diagonals both as numbers and as polynomials, and recurrences and formulae strictly on the diagonals.     

Voronoi drawings of trees

We study the problem of characterizing sets of points whose Voronoi diagrams are trees and if so, what are the combinatorial properties of these trees. The second part of the problem can be naturally turned into the following graph drawing question: Given a tree T, can one represent T so that the resulting drawing is a Voronoi diagram of some set of points? We investigate the problem both in the Euclidean and in the Manhattan metric. The major contributions of this paper are as follows.

• We characterize those trees that can be drawn as Voronoi diagrams in the Euclidean metric.

• We characterize those sets of points whose Voronoi diagrams are trees in the Manhattan metric.

• We show that the maximum vertex degree of any tree that can be drawn as a Manhattan Voronoi diagram is at most five and prove that this bound is tight.

• We characterize those binary trees that can be drawn as Manhattan Voronoi diagrams.

On parallel rectilinear obstacle- avoiding paths

We give improved space and processor complexities for the problem of computing, in parallel, a data structure that supports queries about shortest rectilinear obstacle-avoiding paths in the plane, where the obstacles are disjoint rectangles. That is, a query specifies any source and destination in the plane, and the data structure enables efficient processing of the query. We now can build the data structure with O(n²/log n) CREW PRAM processors, as opposed to the previous O(n²), and with O(n²) space, as opposed to the previous O(n²(log n)²). The time complexity remains unchanged, at O((log n)²). As before, the data structure we compute enables a query to be processed in O(log n) time, by one processor for obtaining a path length, or by O(k/log n) processors for retrieving a shortest path itself, where k is the number of segments on that path. The new ideas that made our improvement possible include a new partitioning scheme of the recursion tree, which is used to schedule the computations performed on that tree. Since a number of other related shortest paths problems are solved using this technique as a subroutine our improvement translates into a similar improvement in the complexities of these problems as well.     

On quasi-linear stochastic partial differential equations

Summary We prove existence and uniqueness of the solution of a parabolic SPDE in one space dimension driven by space-time white noise, in the case of a measurable drift and a constant diffusion coefficient, as well as a comparison theorem.and INRIAPartially supported by DRET under contract 901636/A000/DRET/DS/SR     

行动载荷作用下的连续梁的横向振动问题

本文在考虑行动载荷质量、惯性力及阻尼影响的情况下,研究了机车通过连续梁时横向振动问题的整个过程,并得出了在任意行动载荷PF(t)作用下的连续梁的动力方程的一般解.我们具体计算了单个行动载荷为P_i+Q_isin(a_it+ε_i)时的情形并建立了行动载荷作用下的连续梁横向振动问题的动力理论.最后,做为例子,我们求解了两跨梁的横向振动问题,跨中点的挠度如图2和图3所示.     

Planar and axially symmetric configurations which are circumvented with the maximum critical mach number

The structure of planar and axially symmetric configurations which, by satisfying a number of geometrical constraints, are circumvented in a boundless space or in a cylindrical channel by an ideal (non-viscous and non-thermally conducting) gas with a maximal critical Mach number M* is found. The analysis is carried out using the “rectilinearity property” of a sonic line in “subsonic” flows (SF), the “principle of a maximum” for an SF and “comparison theorems” which are either taken from /1/ or serve as a generalization of the corresponding assertions from /1/. Following /1/, configurations are considered which have a plane or axis of symmetry parallel to the velocity V_∞ of the approach stream, while flows in which (including the boundary) the Mach number M 1 are said to be “subsonic”. As usual, by M* we mean a value of M_∞ such that the inequality M1, which is satisfied in the whole stream when M_∞ M*, is violated when M_∞>M*.

The configurations investigated include closed bodies and the leading (trailing) parts of a semi-infinite plate or a circular cylinder in an unbounded flow and in a channel as well as lattices of symmetric profiles. Both in /1/, where the structure of closed planar and axially symmetric bodies was found, as well as in /2/, where such bodies were constructed numerically, the generatrices of all the configurations investigated contain the end planes or the segments replacing them of the maximum permissible slope (in modulus) and the “free” streamlines with M 1. Now, however, unlike in /1, 2/, segments of the horizontals are added to it in the general case. Furthermore, in the case of flows in channels and lattices, the configurations which have been found can be circumvented with the development of finite domains of advancing sonic flow.     

On the quasi-stationary distribution of a stochastic Ricker model

We model the evolution of a single-species population by a size-dependent branching process Z_t in discrete time. Given that Z_t = n the expected value of Z_t+1 may be written nexp(r − γn) where r> 0 is a growth parameter and γ > 0 is an (inhibitive) environmental parameter. For small values of γ the short-term evolution of the normed process γZ_t follows the deterministic Ricker model closely. As long as the parameter r remains in a region where the number of periodic points is finite and the only bifurcations are the period-doubling ones (r in the beginning of the bifurcation sequence), the quasi-stationary distribution of γZ_t is shown to converge weakly to the uniform distribution on the unique attracting or weakly attracting periodic orbit. The long-term behavior of γZ_t differs from that of the Ricker model, however: γZ_t has a finite lifetime a.s. The methods used rely on the central limit theorem and Markov's inequality as well as dynamical systems theory.     

The SU(v) Calogero spin system

A one-dimensional quantum particle system in which particles with su(v) spins interact through inverse square interactions is introduced. We refer to it as the SU(v) Calogero spin system. Using the quantum inverse scattering method, we reveal algebraic structures of the system: hidden symmetry is the U(v) − SU(v) U(1) current algebra. This is consistent with the fact that the ground-state wave function is a solution of the Knizhnik-Zamolodchikov equation. Furthermore we show that the system has a higher symmetry, known as the w_{1 + ∞}-algebra. With this W-algebra we have a unified viewpoint on the integrable quantum particle systems with long-range interactions such as the Calogero type (1/x²-interactions) and Sutherland type (1/sin²x-interactions). The Yangian symmetry is briefly discussed.     

Input control in nonnegative matrix equations

In this paper we consider the nonnegative matrix system c_iA+u_iB=c_i+1 where the nonnegative matrix A is allowed to vary, within bounds. The cone control problem is to find a nonnegative matrix B such that if C_i is a nonnegative vector in a specified cone, then there is a nonnegative vector u_i such that c_i+1 is in that cone. We extend this problem to input control by finding a B such that the cone, generated by the rows of B, is as small as possible. Thus, the percent distribution of ∣u_iB∣ through the states of the sustem by u_iB is either constant or varies little.     

Area-efficient algorithms for straight-line tree drawings

We investigate several straight-line drawing problems for bounded-degree trees in the integer grid without edge crossings under various types of drawings: (1) upward drawings whose edges are drawn as vertically monotone chains, a sequence of line segments, from a parent to its children, (2) order-preserving drawings which preserve the left-to-right order of the children of each vertex, and (3) orthogonal straight-line drawings in which each edge is represented as a single vertical or horizontal segment.

Main contribution of this paper is a unified framework to reduce the upper bound on area for the straight-line drawing problems from O(nlogn) (Crescenzi et al., 1992) to O(nloglogn). This is the first solution of an open problem stated by Garg et al. (1993). We also show that any binary tree admits a small area drawing satisfying any given aspect ratio in the orthogonal straight-line drawing type.

Our results are briefly summarized as follows. Let T be a bounded-degree tree with n vertices. Firstly, we show that T admits an upward straight-line drawing with area O(nloglogn). If T is binary, we can obtain an O(nloglogn)-area upward orthogonal drawing in which each edge is drawn as a chain of at most two orthogonal segments and which has O(n/logn) bends in total. Secondly, we present O(nloglogn)-area (respectively, -volume) orthogonal straight-line drawing algorithms for binary trees with arbitrary aspect ratios in 2-dimension (respectively, 3-dimension). Finally, we present some experimental results which shows the area requirements, in practice, for (order-preserving) upward drawing are much smaller than theoretical bounds obtained through analysis.     

On an optimal stopping problem of Gusein-Zade

We study the problem of selecting one of the r best of n rankable individuals arriving in random order, in which selection must be made with a stopping rule based only on the relative ranks of the successive arrivals. For each r up to r=25, we give the limiting (as n→∞) optimal risk (probability of not selecting one of the r best) and the limiting optimal proportion of individuals to let go by before being willing to stop. (The complete limiting form of the optimal stopping rule is presented for each r up to r=10, and for r=15, 20 and 25.) We show that, for large n and r, the optical risk is approximately (1−t^*)^r, where t^*≈0.2834 is obtained as the roof of a function which is the solution to a certain differential equation. The optimal stopping rule τ_r,n lets approximately t^*n arrivals go by and then stops ‘almost immediately’, in the sense that τ_r,n/n→t^* in probability as n→∞, r→∞     

New Rapidly Convergent Series Concerning ζ(2k+1)

Values of new series sum(((2n-1)!ζ(2n))/(2n + 2k)!)α2n from n=1 to ∞,sum(((2n-1)!ζ(2n))/(2n+2k +1)!)β2n from n=1 to ∞ are given concerning ζ(2k + 1),where k is a positive integer,α can be taken as 1,1/2,1/3,2/3,1/4,3/4,1/6,5/6 and β can be taken as 1,1/2.Some previous results are included as special cases in the present paper and new series converges more rapidly than those exsiting results for α = 1/3,or α = 1/4,or α = 1/6.     

Chapter 4:algebraic sets, polynomials, and other functions

Let T be a linear operator on the vector space V ofn×n matrices over a field F. We discuss two types of problems in this chapter. First, what can we say about T if we assume that T maps a given algebraic set such as the special linear group into itself? Second, let p(x) be a polynomial function (such as det) on V into F. What can we say about T if Tpreserves p(x), i.e. p(T(X)) = p(X) for all X in V?