The Constrained Solutions of Two Matrix Equations

We study the symmetric positive semidefinite solution of the matrix equation AX ₁ A ^T + BX ₂ B ^T = C, where A is a given real m×n matrix, B is a given real m×p matrix, and C is a given real m×m matric, with m, n, p positive integers; and the bisymmetric positive semidefinite solution of the matrix equation D ^T XD = C, where D is a given real n×m matrix, C is a given real m×m matrix, with m, n positive integers. By making use of the generalized singular value decomposition, we derive general analytic formulae, and present necessary and sufficient conditions for guaranteeing the existence of these solutions. Received December 17, 1999, Revised January 10, 2001, Accepted March 5, 2001     

Adaptive policies for time-varying stochastic systems under discounted criterion

We consider a class of time-varying stochastic control systems, with Borel state and action spaces, and possibly unbounded costs. The processes evolve according to a discrete-time equation x _{n + 1}=G _n (x _n , a _n , ξ_n), n=0, 1, … , where the ξ_n are i.i.d. ℜ^k-valued random vectors whose common density is unknown, and the G _n are given functions converging, in a restricted way, to some function G _∞ as n→∞. Assuming observability of ξ_n, we construct an adaptive policy which is asymptotically discounted cost optimal for the limiting control system x _n+1=G _∞ (x _n , a _n , ξ_n).     

All directed BIBDs with k = 3 exist

A directed BIBD with parameters ($\text{υ, b, r, k, λ}{}^1$) is a BIBD with parameters ($\text{υ, b, r, k, 2λ}{}^1$) in which each ordered pair of varieties occurs together in exactly $\text{λ}{}^1$ blocks. It is shown that $\text{λ}{}^1\text{υ(υ ? 1) ≡ 0}$ (mod 3) is a necessary and sufficient condition for the existence of a directed ($\text{υ, b, r, k, λ}{}^1$) BIBD with k = 3.     

PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS

Let Qn,k(n≥3,1≤k≤n-1) be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges,fv and fe be the numbers of faulty vertices and faulty edges,respectively.In this paper,we give three main results.First,a fault-free path P [u,v] of length at least 2n-2fv-1(respectively,2n-2fv-2) can be embedded on Qn,k with fv+fe≤n-1 when d Qn,k(u,v) is odd(respectively,d Qn,k(u,v) is even).Secondly,an Qn,k is(n-2) edgefault-free hyper Hamiltonian-laceable when n(≥3) and k have the same parity.Lastly,a fault-free cycle of length at least 2n-2fv can be embedded on Qn,k with fe≤n-1 and fv+fe≤2n-4.     

Kp,q-factorization of complete bipartite graphs

Let K _m,nbe a complete bipartite graph with two partite sets having m and n vertices, respectively. A K _p,q-factorization of K _m,n is a set of edge-disjoint K _p,q-factors of K _m,n which partition the set of edges of K _m,n. When p = 1 and q is a prime number, Wang, in his paper “On K _1,k -factorizations of a complete bipartite graph” (Discrete Math, 1994, 126: 359—364), investigated the K _1,q -factorization of K _m,nand gave a sufficient condition for such a factorization to exist. In the paper “K _1,k -factorizations of complete bipartite graphs” (Discrete Math, 2002, 259: 301—306), Du and Wang extended Wang’s result to the case that q is any positive integer. In this paper, we give a sufficient condition for K _m,n to have a K _p,q-factorization. As a special case, it is shown that the Martin’s BAC conjecture is true when p : q = k : (k+ 1) for any positive integer k.     

Approximate Shortest Paths and Geodesic Diameter on a Convex Polytope in Three Dimensions

Given a convex polytope P with n edges in ³ , we present a relatively simple algorithm that preprocesses P in O(n) time, such that, given any two points , and a parameter 0 < 1, it computes, in O(log n) /ɛ ^1.5 + 1/ ɛ ³ ) time, a distance Δ _P (s,t) , such that d _P (s,t) Δ _P (s,t) (1+ɛ )d _P (s,t) , where d _P (s,t) is the length of the shortest path between s and t on . The algorithm also produces a polygonal path with O (1/ɛ ^1.5 ) segments that avoids the interior of P and has length Δ _P (s,t) . Our second related result is: Given a convex polytope P with n edges in ³ , and a parameter 0 < 1, we present an O (n + 1/ ɛ ⁵ )-time algorithm that computes two points such that , where is the geodesic diameter of P . Received April 8, 1997, and in revised form August 3, 1997.     

An extremal set theoretical characterization of some steiner systems

Letn, k, t be integers,n>k>t≧0, and letm(n, k, t) denote the maximum number of sets, in a family ofk-subsets of ann-set, no two of which intersect in exactlyt elements. The problem of determiningm(n, k, t) was raised by Erdős in 1975. In the present paper we prove that ifk≦2t+1 andk−t is a prime, thenm(n, k, t)≦( _t ⁿ )( _k ^2k-t-1 )/( _t ^2k-t-1 ). Moreover, equality holds if and only if an (n, 2k−t−1,t)-Steiner system exists. The proof uses a linear algebraic approach.     

Construction of Some Optimal Ternary Linear Codes and the Uniqueness of [294, 6, 195; 3]-Codes Meeting the Griesmer Bound

Let n_q(k, d) denote the smallest value of n for which there exists an [n, k, d; q]-code. It is known (cf. (J. Combin. Inform. Syst. Sci.18, 1993, 161–191)) that (1) n₃(6, 195) {294, 295}, n₃(6, 194) {293, 294}, n₃(6, 193) {292, 293}, n₃(6, 192) {290, 291}, n₃(6, 191) {289, 290}, n₃(6, 165) {250, 251} and (2) there is a one-to-one correspondence between the set of all nonequivalent [294, 6, 195; 3]-codes meeting the Griesmer bound and the set of all {v₂ + 2v₃ + v₄, v₁ + 2v₂ + v₃; 5, 3}-minihypers, where v_i = (3ⁱ − 1)/(3 − 1) for any integer i ≥ 0. The purpose of this paper is to show that (1) n₃(6, 195) = 294, n₃(6, 194) = 293, n₃(6, 193) = 292, n₃(6, 192) = 290, n₃(6, 191) = 289, n₃(6, 165) = 250 and (2) a [294, 6, 195; 3]-code is unique up to equivalence using a characterization of the corresponding {v₂ + 2v₃ + v₄, v₁ + 2v₂ + v₃; 5, 3}-minihypers.     

Limiting process for integral functionals of a wiener process on a cylinder

We prove that integral functionals, whose integrands are bounded functions of a Wiener process on a cylinder, weakly converge to the processw ₁(τ(t)), τ(t) = β₁ t + (β₂ − β₁)mes {s:w ₂(s)≥0,s<t}, wherew ₁(t andw ₂(t) are independent one-dimensional Wiener processes, β₁ and β₂ are nonrandom values, and β₂≥β₁≥0. Kiev University, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 6, pp. 765–768, June, 1994.     

On a Function Related to Multinomial Coefficients (I)

Let F _p,t (n) denote the number of the coefficients of (x ₁+1x ₂+...+x _t ) ^j , 0 ≤j≤n− 1, which are not divisible by the prime p. Define G _p,t (n) = F _p,t /n ^θ and β(p,t) = lim infF _p,t )(n)/n ^θ, where θ = (log)/(log p). In this paper, we mainly prove that G _p,t can be extended to a continuous function on ℝ⁺, and the function G _p,t is nowhere monotonic. Both the set of differential points of the function G _p,t and the set of non-differential points of the function G _p,t are dense in ℝ⁺. Received February 18, 2000, Accepted December 7, 2000     

Plane Sections of Convex Bodies of Maximal Volume

Let K = {K ₀ ,... ,K _k } be a family of convex bodies in R ⁿ , 1≤ k≤ n-1 . We prove, generalizing results from [9], [10], [13], and [14], that there always exists an affine k -dimensional plane A _k (subset, dbl equals) R ⁿ , called a common maximal k-transversal of K , such that, for each i∈ {0,... ,k} and each x∈ R ⁿ , where V _k is the k -dimensional Lebesgue measure in A _k and A _k +x . Given a family K = {K _i } _i=0 ^l of convex bodies in R ⁿ , l < k , the set C _k ( K ) of all common maximal k -transversals of K is not only nonempty but has to be ``large' both from the measure theoretic and the topological point of view. It is shown that C <sub>k</sub> ( K ) cannot be included in a ν -dimensional C <sup>1</sup> submanifold (or more generally in an ( H <sup>ν</sup> , ν) -rectifiable, H <sup>ν</sup> -measurable subset) of the affine Grassmannian AGr <sub>n,k</sub> of all affine k -dimensional planes of R <sup>n</sup> , of O(n+1) -invariant ν -dimensional (Hausdorff) measure less than some positive constant c <sub>n,k,l</sub> , where ν = (k-l)(n-k) . As usual, the ``affine' Grassmannian AGr _n,k is viewed as a subspace of the Grassmannian Gr _n+1,k+1 of all linear (k+1) -dimensional subspaces of R ⁿ⁺¹ . On the topological side we show that there exists a nonzero cohomology class θ∈ H ^n-k (G _n+1,k+1 ;Z ₂ ) such that the class θ ^l+1 is concentrated in an arbitrarily small neighborhood of C _k ( K ) . As an immediate consequence we deduce that the Lyusternik—Shnirel'man category of the space C _k ( K ) relative to Gr _n+1,k+1 is ≥ k-l . Finally, we show that there exists a link between these two results by showing that a cohomologically ``big' subspace of Gr _n+1,k+1 has to be large also in a measure theoretic sense. Received May 22, 1998, and in revised form March 27, 2000. Online publication September 22, 2000.     

On some new generalized difference sequence spaces defined by a sequence of moduli

In this paper, we define the new generalized difference sequence spaces [V, λ, F, p, q]₀(Δ _v ^m ), [V, λ, F, p, q]₁(Δ _v ^m ) and [V, λ, F, p, q]_∞(Δ _v ^m ). We also study some inclusion relations between these spaces.     

Lattice Polytopes with Distinct Pair-Sums

Let P be a lattice polytope in R ⁿ , and let P \cap Z ⁿ = {v ₁ ,\ldots,v _N } . If the N + N\choose 2 points 2v ₁ ,\ldots, 2v _N ;v ₁ +v ₂ ,\ldots, v _N-1 + v _N are distinct, we say that P is a ``distinct pair-sum' or ``dps' polytope. We show that if P is a dps polytope in R ⁿ , then N≤ 2 ⁿ , and, for every n , we construct dps polytopes in R ⁿ which contain 2 ⁿ lattice points. We also discuss the relation between dps polytopes and the study of sums of squares of real polynomials. Received November 10, 2000, and in revised form June 28, 2001. Online publication November 2, 2001.     

Δ-Monotone arrangements of real numbers

Given a set of M × N real numbers, can these always be labeled as x_i,j; i = 1,…, M; j = 1,…, N; such that x_i+1,j+1 ? x_i+1,j ? x_i,j+1 + x_ij ≥ 0, for every (i, j) where 1 ≤ i ≤ M ? 1, 1 ≤ j ≤ N ? 1? For M = N = 3, or smaller values of M, N it is shown that there is a “uniform” rule. However, for max(M, N) > 3 and min(M, N) ≥ 3, it is proved that no uniform rule can be given. For M = 3, N = 4 a way of labeling is demonstrated. For general M, N the problem is still open although, for a special case where all the numbers are 0's and 1's, a solution is given.     

Linear maps that strongly preserve regular matrices over the Boolean algebra

The set of all m × n Boolean matrices is denoted by $ \mathbb{M} $ \mathbb{M} _m,n . We call a matrix A ∈ $ \mathbb{M} $ \mathbb{M} _m,n regular if there is a matrix G ∈ $ \mathbb{M} $ \mathbb{M} _n,m such that AGA = A. In this paper, we study the problem of characterizing linear operators on $ \mathbb{M} $ \mathbb{M} _m,n that strongly preserve regular matrices. Consequently, we obtain that if min{m, n} ⩽ 2, then all operators on $ \mathbb{M} $ \mathbb{M} _m,n strongly preserve regular matrices, and if min{m, n} ⩾ 3, then an operator T on $ \mathbb{M} $ \mathbb{M} _m,n strongly preserves regular matrices if and only if there are invertible matrices U and V such that T(X) = UXV for all X ε $ \mathbb{M} $ \mathbb{M} _m,n , or m = n and T(X) = UX ^T V for all X ∈ $ \mathbb{M} $ \mathbb{M} _n .     

A Schur test for weighted mixed-norm spaces

Summary We prove a Schur test for mixed-norm spaces L^p,q, 1 < p,q < ∞. Also we prove another version of the Schur test for discrete weighted mixed-norm spaces l^p,q _w, 1 < p,q < ∞, and wis a weight. We show that if w ₁, and w ₂are two weight functions on the index sets Jx Iand K x Lrespectively, and A =(a _{ji, kl} ) _{j∈J, i∈I, k∈K, l∈L} is an infinite matrix, then under certain conditions, Ais a bounded operator from l^p,q _w1, 1 < p,q < ∞ to l^p,q _w2. This will be a key result in proving boundedness of important operators in our work in time-frequency analysis.</o:p>     

Two finiteness theorems for periodic tilings of d-dimensional euclidean space

Consider the d -dimensional euclidean space E ^d . Two main results are presented: First, for any N∈ N, the number of types of periodic equivariant tilings that have precisely N orbits of (2,4,6, . . . ) -flags with respect to the symmetry group Γ , is finite. Second, for any N∈ N, the number of types of convex, periodic equivariant tilings that have precisely N orbits of tiles with respect to the symmetry group Γ , is finite. The former result (and some generalizations) is proved combinatorially, using Delaney symbols, whereas the proof of the latter result is based on both geometric arguments and Delaney symbols. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p143.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received September 5, 1996, and in revised form January 6, 1997.     

On linear widths of classesH ω

We obtain new results related to the estimation of the linear widths λ _N and λ ^N in the spacesC andL _p for the classesH ^ω (in particular, forH ^α, 0<α<1). Institute of Mathematics, Ukrainian Academy of Sciences, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 48, No. 9, pp. 1255–1264, September, 1996.     

The Characterization for a Graphic Sequence to have a Realization Containing K 1,1,s

A graphic sequence π?=?(d ₁, d ₂, . . . , d _n ) is said to be potentially K _1,1,s -graphic if there is a realization of π containing K _1,1,s as a subgraph, where K _1,1,s is the 1?× 1?× s complete 3-partite graph. In this paper, a simple characterization of potentially K _1,1,s -graphic sequences for s?≥ 2 and n?≥ 3s?+?1 is obtained. This characterization implies Lai’s conjecture on σ(K _1,1,s , n), which was confirmed by J.H. Yin, J.S. Li and W.Y. Li, and the values of σ(K _2,s , n) for s?≥ 4 and n?≥ 3s?+?1, where K _2,s is the 2?× s complete bipartite graph.     

Asymptotic stability of some quasilinear parabolic equations in divergence form. L∞ results

In this paper we study the behavior of solutions of some quasilinear parabolic equations of the form

$\text{(}\text{?u}\text{?t}\text{) ?}\text{∑}\text{i=1}\text{n}\text{(}\text{d}\text{dx}{}_{\mathrm{i}}\text{) a}{}_{\mathrm{i}}\text{(x, t, u, u}{}_{\mathrm{x}}\text{) + a(x, t, u, u}{}_{\mathrm{x}}\text{)u + f(x, t) = O,}$

as t → ∞. In particular, the solutions of these equations will decay to zero as t → ∞ in the L^∞ norm.