On Domination Number of 4-Regular Graphs

Let G be a simple graph. A subset S V is a dominating set of G, if for any vertex v V – S there exists a vertex u S such that uv E(G). The domination number, denoted by (G), is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n, then (G) ⁴/₁₁ n     

Method of moments on semigroups

If ( _j ) is a sequence of measures onR ^k having momentss _n ( _j ) of all ordersnN ₀ ^k and if for eachnN ₀ ^k the sequence (s _{n j} )) _jN converges to somet _n R then some subsequence of ( _j ) converges weakly to a measure with moments of all orders satisfyings _n ()=t _n for allnN^0/k . Thisindeterminate method of moments and the continuity theorems in probability theory suggest a common generalization, dealing with a commutative semigroupS, with involution and a neutral element, and measures on the dual semigroupS ^* ofcharacters on S—hermitian multiplicative complex functions not identically zero. In this setting, a continuity theorem holds for measures on the set of bounded characters,⁽²⁾ and an indeterminate method of moments whenS is finitely generated.⁽²⁾ The latter result is generalized in the present paper to the case of arbitraryS. This leads to a generalization of Haviland's criterion for theK-moment problem, and to a continuity theorem for the so-called perfect semigroups.     

Reconstructing dimensions of intersections of convex sets

Denoting by dimA the dimension of the affine hull of the setA, we prove that if {K _i:i T} and {K _i ^j :i T} are two finite families of convex sets inR ⁿ and if dim {K _i :i S} = dim {K _i ^j :i S}for eachS T such that|S| n + 1 then dim {K _i :i T} = dim {K _i : {i T}}.     

Regularity and Unit-regularity of Generalized Semigroups of Linear Transformations

Let V and W be vector spaces over a division ring D and L_D (V, W) the set of all linear transformations from V into W. For L_D(W, V), let (L_D (V, W), ) denote the semigroup L_D (V, W) with the operation * defined by * = for all , L_D(V, W). By a unit-regular semigroup we mean a semigroup S with identity having the property that for each a S, a = aua for some unit u S. The main purpose of this paper is to prove the following statements. The semigroup (L_D(V, W), ) is regular if and only if V = {0}, W = {0} or is an isomorphism from W onto V. The semigroup (L_D (V, W), ) is unit-regular if and only if (i) V = {0}, (ii) W = {0} or (iii) is an isomorphism from W onto V and dim_D V .     

Connected and alternating vectors: Polyhedra and algorithms

Given a graphG = (V, E), leta ^S, S L, be the edge set incidence vectors of its nontrivial connected subgraphs.The extreme points of = {x R ^E: a^sx |V(S)| - |S|, S L} are shown to be integer 0/± 1 and characterized. They are the alternating vectorsb ^k, k K, ofG. WhenG is a tree, the extreme points ofB 0,b ^kx 1,k K} are shown to be the connected vectors ofG together with the origin. For the four LP's associated with andA, good algorithms are given and total dual integrality of andA proven.On leave from Swiss Federal Institute of Technology, Zurich.     

On a Property of Subexponential Distributions

Let F be a distribution function (d.f.) on [0, ) with finite first moment m >0. We define the integrated tail distribution function F ₁ of F by F ₁(t)=m^-1 ₀ ^t (1- F(u))du, t0. In this paper, we obtain sufficient conditions under which implications FSF ₁S and F ₁S FS hold, where S is the class of subexponential distributions.     

Measure properties of the set of initial data yielding non uniqueness for a class of differential inclusions

We study uniqueness property for the Cauchy problemxV(x), x(0)=, whereVR ⁿR is a locally Lipschitz continuous, quasiconvex function (i.e. the sublevel sets {Vc} are convex) and V(x) is the generalized gradient ofV atx. We prove that if 0V(x) forV(x)b, then the set of initial data {V=b} yielding non uniqueness of solution in a geometric sense has (n–1)-dimensional Hausdorff measure zero in {V=b}.     

A “from scratch” proof of a theorem of Rockafellar and Fulkerson

The theorem of this paper is of the same general class as Farkas' Lemma, Stiemke's Theorem, and the Kuhn—Fourier Theorem in the theory of linear inequalities. LetV be a vector subspace ofR ⁿ , and let intervalsI ¹,, I ⁿ of real numbers be prescribed. A necessary and sufficient condition is given for existence of a vector (x ¹ ,, x ⁿ ) inV such thatx ⁱ I ⁱ (i = 1, ,n); this condition involves the elementary vectors (nonzero vectors with minimal support) ofV . The proof of the theorem uses only elementary linear algebra.The author at present holds a Senior Scientist Award of the Alexander von Humboldt Stiftung.     

Quasi sure version of a theorem of littlewood

Let (c _n) _nZ be a double-sided sequence of complex numbers; if, for quasi-all (i.e. in the Baire sense) choices of signs ( _n) _nZ , ( _n c _n) _nZ is a Fourier-Stieltjes sequence, then we prove that (c _n) _nZ l ² (Z); this extends a result of Littlewood and at the same time provides a very simple proof of this result.     

On the unique finite (SI) decomposition of the Jordan operator ⊕ i=1 n S(θ) for certain inner function θ

In this paper, we have proven that for the Jordan blockS() withS() (SI), _i=1 ⁿ S() =S() ⁽ⁿ⁾ (n 1) has unique finite (SI) decomposition up to a similarity. As result, we obtain that ifV is a Volterra operator onH=L ²([0, 1]), thenV ⁽ⁿ⁾ has unique finite (SI) decomposition.This project was supported by National Natural Science Foundation of China.     

Holomorphic rank of hypersurfaces with an isolated singularity

LetV be a germ at 0 C ²,n3, of hypersurface with an isolated singularity at 0. In this paper we prove that the maximal number of germs of vector fields inV ^*=V–0, which are linearly independent in all points ofV ^* is two. In the casesn=3,4 and of quasi homogeneous hypersurfaces (n3), we prove that this number is one.Dedicated to the memory of R. MañéThis research was partially supported by Pronex.     

Independent sets,cliques and hamiltonian graphs

LetG be ak-connected (k 2) graph onn vertices. LetS be an independent set ofG. S is called essential if there exist two distinct vertices inS which have a common neighbor inG. LetV _r, be a clique which is a complete subgraph ofG. In this paper it is proven that if every essential independent setS ofk + 1 vertices satisfiesS V _r , thenG is hamiltonian, orG{u} is hamiltonian for someu V _r, orG is one of three classes of exceptional graphs. Our theorem generalizes several well-known theorems.     

On the existence of wave operators for the Klein-Gordon equation

The problem of existence of wave operators for the Klein-Gordon equation ( _t ² –+²+iV_1t+V₂)u(x,t)=0 (x R ⁿ,t R, n3, >0) is studied where V₁ and V₂ are symmetric operators in L₂(R ⁿ) and it is shown that conditions similar to those of Veseli-Weidmann (Journal Functional Analysis 17, 61–77 (1974)) for a different class of operators are also sufficient for the Klein-Gordon equation.     

Large-Deviation Local Theorem for Additive Functionals of a Markov Gaussian Field. I

We prove a local limit theorem (LLT) on Cramer-type large deviations for sums S _V = _t V ( _t ), where _t , t Z , 1, is a Markov Gaussian random field, V Z , and is a bounded Borel function. We get an estimate from below for the variance of S _V and construct two classes of functions , for which the LLT of large deviations holds.     

Asymptotic behavior of the number of certaink-dimensional subspaces over a finite field

For some values ofk, we find the asymptotic behavior, asn , of the probability that a subspace, whose choice is random and equiprobable, chosen among the set of all differentk-dimensional subspaces of ann-dimensional vector space over a finite field, has a given weight {1, 2, ...,n}. In particular, for {1, 2}, this probability can have exponential behavior.Translated fromMatematicheskie Zametki, Vol. 59, No. 5, pp. 729–736, May, 1996.     

A note on constructing a symmetric matrix with specified diagonal entries and eigenvalues

A finite step algorithm is given such that for any two vectorsa, R ⁿ witha majorized by , it computes a symmetric matrixH R ^{n x n} with the elements ofa and as its diagonal entries and eigenvalues, respectively.Supported in part by NSF grant CCR-9308399.Supported in part by China State Major Key Project for Basic Researches.     

A characterization of subgroups of the orthogonal group

LetG be a subgroup of the general linear group GL_n(K), where charK 2. Put Kⁿ =V. AssumeG is generated by the setS of all elements inG for which dimV( – 1) = 1, and suppose ²=1_V for each inS. If {V(–1)¦S} contains a simplex, if – 1_V G, and if inG is a product of dim v(–1) elements inS wheneverV(–1) is not contained in the kernel of–1, thenG is a subgroup of an orthogonal group.This research was supported in part by NSERC Canada grant A7251.To Helmut Mäurer on his 60th birthday     

On the product of sign vectors and unit vectors

For a fixed unit vectora=(a ₁,...,a _n )S ^n-1, consider the 2 ⁿ sign vectors=(₁,..., _n ){±1{ ⁿ and the corresponding scalar products^·a = _n ⁱ⁼¹ = _i a _i . The question that we address is: for how many of the sign vectors must^.a lie between–1 and 1. Besides the straightforward interpretation in terms of the sums ±a ₂ , this question has appealing reformulations using the language of probability theory or of geometry.The natural conjectures are that at least 1/2 the sign vectors yield |.a|1 and at least 3/8 of the sign vectors yield |.a|<1 (the latter excluding the case when |a _i |=1 for somei). These conjectured lower bounds are easily seen to be the best possible. Here we prove a lower bound of 3/8 for both versions of the problem, thus completely solving the version with strict inequality. The main part of the proof is cast in a more general probabilistic framework: it establishes a sharp lower bound of 3/8 for the probability that |X+Y|<1, whereX andY are independent random variables, each having a symmetric distribution with variance 1/2.We also consider an asymptotic version of the question, wheren along a sequence of instances of the problem satisfying ||a||0. Our result, best expressed in probabilistic terms, is that the distribution of .a converges to the standard normal distribution, and in particular the fraction of sign vectors yielding .a between –1 and 1 tends to 68%.This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.     

The Adjoints of Dilation Operators on H-Cones

If S is an H-cone and P:SS is a localizable dilation operator on S (i.e., P is additive increasing, contractive, continuous in order from below and s(Ps+t–Pt+Pf)S, s,tS,f(S–S)₊), then it is proved that its adjoint P ^*:S ^*S ^* (i.e., P ^*=P) is also a localizable dilation operator. This is an improvement of a result obtained by G. Mokobodzki in the frame of excessive functions.     

Semistable measures and limit theorems on real andp-adic groups

For any locally compact groupG, we show that any locally tight homomorphism from a real directed semigroup intoM ¹ (G) (semigroup of probability measures onG) has a shift which extends to a continuous one-parameter semigroup. IfG is ap-adic algebraic group then the above holds even iff is not locally tight. These results are applied to give sufficient conditions for embeddability of some translate of limits of sequences of the form {v _n ^kn } and M ¹ (G) such that ()= ^M , for somek>1 and AutG (cf. Theorems 2.1, 2.4, 3.7).