k-regular factors and semi-k-regular factors in bipartite graphs

LetG be a graph, andk1 an integer. LetU be a subset ofV(G), and letF be a spanning subgraph ofG such that deg _F (x)=k for allx V(G)–U. If deg _F (x)k for allxU, thenF is called an upper semi-k-regular factor with defect setU, and if deg _F (x)k for allxU, thenF is called a lower semi-k-regular factor with defect setU. Now letG=(X, Y;E(G)) be a bipartite graph with bipartition (X,Y) such that X=Yk+2. We prove the following two results.(1) Suppose that for each subsetU ₁X such that U ₁=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.(2) Suppose that for each subsetU ₁X such that U ₁=X–1/k+1,G has a lower semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=X–1/k+1,G has a lower semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.     

Rates of convergence for the stability of large order statistics

Forr1 and eachnr, letM _nr be therth largest ofX ₁,X ₂, ...,X _n , where {X _n ,n1} is an i.i.d. sequence. Necessary and sufficient conditions are presented for the convergence of for all >0 and some –1, where {a _n } is a real sequence. Furthermore, it is shown that this series converges for all >–1, allr1 and all >0 if it converges for some >–1, somer1 and all >0.     

A note on the addition of residues

LetA andB be two proper subsets of _n such thatA + B _n .The Cauchy-Davenport Theorem states that|A + B| |A| + |B| – 1 for a primen. As mentioned by Cauchy the inequality may not hold for a compositen. Chowla generalized the Cauchy-Davenport as follows.Suppose 0 B andgcd(x, n) = 1 for allx B0, then|A + B| |A| + |B| – 1. We show that if 0 B and for allx, y B0 such thatx y gcd(x,y,n) = 1, then|A + B| |A| + |B| – 2. Moreover|A + B| |A| + |B| – 1 unless |B| = 2 or b B such thatB {0, b} is a union of cosets modulo the cyclic group generated byb.     

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.     

The periodic Dirac operator is absolutely continuous

We consider the periodic Dirac operatorD inL ₂( ^d ). The magnetic potentialA and the electric potentialV are periodic. Ford=2 the absolute continuity ofD is established forA,VL _{r, loc} ,r>2; the proof is based on the estimates, obtained by the authors earlier [BSu2] for the periodic magnetic Schrödinger operatorM. Ford3 our considerations are based on the estimates forM, obtained in [So] forAC ^2d+3 . Under the same condition onA, forVC, the absolute continuity ofD, d3, is proved. ForA=0 the arguments of the paper give a new (and much simpler) proof of the main result of [D].The research was completed in the framework of the project INTAS-93-351.     

Reconstruction of a wiener field from its realizations on a curve

Let w(x, y), x 0 and y 0 be a Wiener field on the plane; be a curve given parametrically x=x() and y=y(), [0, 1], where x() is a positive, continuous, nondecreasing function; y() is a positive, continuous, nonincreasing function. A best estimate in the mean-square sense is constructed for w(u, v)(u, v) , based on the values w(x, y), (x, y) and its error is found.Translated from Teoriya Sluchainykh Protsessov, No. 16, pp. 87–93, 1988.     

A self normalized law of the iterated logarithm for random walk in random scenery

LetX,X _i ,i1, be a sequence of i.i.d. random vectors in ^d . LetS _o=0 and, forn1, letS _n =X ₁+...+X _n . LetY,Y(), ^d , be i.i.d. -valued random variables which are independent of theX _i . LetZ _n =Y(S _o )+...+Y(S _n ). We will callZ _n arandom walk in random scenery.In this work, we consider the law of the iterated logarithm for random walk in random sceneries. Under fairly general conditions, we obtain arandomly normalized law of the iterated logarithm.Supported in part by NSF Grants DMS-85-21586 and DMS-90-24961.     

A Class of Iterative Algorithms and Solvability of Nonlinear Variational Inequalities Involving Multivalued Mappings

The solvability of the following class of nonlinear variational inequality (NVI) problems based on a class of iterative procedures, which possess an equivalence to a class of projection formulas, is presented.Determine an element x ^* K and u ^* T(x ^*) such that u ^*, x – x ^* 0 for all x K where T: K P(H) is a multivalued mapping from a real Hilbert space H into P(H), the power set of H, and K is a nonempty closed convex subset of H. The iterative procedure adopted here is represented by a nonlinear variational inequality: for arbitrarily chosen initial points x ⁰, y ⁰ K, u ⁰ T(y ⁰) and v ⁰ T(x ⁰), we have u ^k + x ^k+1 – y ^k , x – x ^k+1 0, x K, for u ^k T(y ^k ) and for k 0where v ^k + y ^k – x ^k , x – y ^k 0, x K and for v ^k T(x ^k ).     

Kite-freeP- andQ-polynomial schemes

LetY = (X, {R _i } _oid) denote aP-polynomial association scheme. By a kite of lengthi (2 i d) inY, we mean a 4-tuplexyzu (x, y, z, u X) such that(x, y) R ₁,(x, z) R ₁,(y, z) R ₁,(u, y) R _i–1,(u, z) R _i–1,(u, x) R _i. Our main result in this paper is the following.     

Striktionseigenschaften von Regelscharen imE n

Let ={e(u)|uI} be a one-parameter family of straight lines forming a ruledC ^r-2-surface E ⁿ (n2,r1) without singular generatorse(u) (uI). As a synopsis, a generalization and an improvement of various results already known about the strictional properties of ruled surfaces E ⁿ (especially in the casen=3) the author demonstrates a uniform geometrical way of defining and uniquely obtaining thestriction point S(u) and theparameter of distribution d(u) of a generatore(u) under the minimal assumptions thate(u)E ⁿ (n2) be noncylindrical andr1. Other methods of obtainingS(u) andd(u) are discussed in comparison, and special strictional properties ofskew ruled surfaces E ⁿ are proved.

---

---

Herrn Prof. Dr. H. R. Müller zum 65. Geburtstag     

Abschnittspositive Matrizen und Positivitätsfaktoren in der Limitierungstheorie

Let A and B be normal matrices. In :={x=(x_k) ¦ x_k} we define the order relation _A by x_A0:<=> _k=0 ⁿ a_nkx_k0 (n ). Let T be a row-finite matrix. A is called T-section-positive, if _kt_mkx_ke^(k) _A0 (m ) for x_A0 (see [5]). We study the relation between T-sectional positivity and T-sectional boundedness. An (A,B)-summability factor sequence =(_k) is called positive, if (_kx_k)_B0 for each xc_A with x_A0. For B-section-positive matrices A we give a functional analytic characterization of positive (A,B)-summability factor sequences.

---

---

Die Arbeit entstand während eines vom DAAD unterstützten Forschungsaufenthalts an der Fernuniversität-Gesamthochschule Hagen     

Algorithms for proportional matrices in reals and integers

LetR be the set of nonnegative matrices whose row and column sums fall between specific limits and whose entries sum to some fixedh > 0. Closely related axiomatic approaches have been developed to ascribe meanings to the statements: the real matrixf R and the integer matrixa R are proportional to a given matrixp 0.These approaches are described, conditions under which proportional solutions exist are characterized, and algorithms are given for finding proportional solutions in each case.     

A perturbation result for the asymptotic behavior of matrix powers

We prove a perturbation result for the asymptotic behavior of the sequence (A ⁿ c) _nN , whereAG|(d), the space of invertibled×d matrices, andc ^d .     

Invariant measures ofC 2-diffeomorphisms of Markov type inR d

A class of uniformly expanding, piecewiseC ²-diffeomorphisms from domainsIR ^d (bounded or not) into themselves is considered. It is shown that the number of the extreme points of Fix (P )={gG:Pg=g} whereP is the Frobenius-Perron operator associated with andG={gL ¹: g0 g=1}, can be determined in an effective way. Moreover, it is shown that the sequence {P ^j g} is convergent inL ¹ for anygG, and in the topology of uniform convergence for anygG(1). The limit is a linear projectionR inL ¹ (defined by (3.1)) which mapsG onto Fix (P ) (see Th. 3.1).Dedicated to professor A. Lasota on the occasion of his 60th birthday     

Some best possible bounds concerning the traces of finite sets II

LetX be ann-element set and be a family of its subsets. Consider the family _x = {F – {x} : F } for a givenx X. We write(m, n) (m – k, n – 1), when for all with || m, there exists an elementx ofX such that| _x| m – k. We show that (m, n) (m – 10,n – 1) for allm 5n and (m, n) (m – 13,n – 1) for allm 29n/5.     

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.     

A generalization of a theorem of M. Riesz to the case of functions of several variables

The following theorem was proved by M. Riesz: Iff(x) L(–,),f(x) 0 and the conjugate functionf (x) is also integrable on [-, ], thenf(x) L log⁺L. The analog of this theorem for functions of several variables is established.Translated from Matematicheskie Zametki, Vol. 4, No. 3, pp. 269–280, November, 1968.     

Minimaxity and admissibility of the product limit estimator

In this article we examine the minimaxity and admissibility of the product limit (PL) estimator under the loss function% MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqaqpepeea0xe9qqVa0l% b9peea0lb9sq-JfrVkFHe9peea0dXdarVe0Fb9pgea0xa9pue9Fve9% Ffc8meGabaqaciGacaGaaeqabaWaaeaaeaaakeaacaWGmbGaaiikai% aadAeacaGGSaGabmOrayaajaGaaiykaiabg2da9maapeaabaGaaiik% aiaadAeacaGGOaGaamiDaiaacMcaaSqabeqaniabgUIiYdGccqGHsi% slceWGgbGbaKaacaGGOaGaamiDaiaacMcacaGGPaWaaWbaaSqabeaa% caaIYaaaaOGaamOramaaCaaaleqabaaccmGae8xSdegaaOGaaiikai% aadshacaGGPaGaaiikaiaaigdacqGHsislcaWGgbGaaiikaiaadsha% caGGPaGaaiykamaaCaaaleqabaGaeqOSdigaaOGaamizaiaadEfaca% GGOaGaamiDaiaacMcaaaa!5992!\[L(F,\hat F) = \int {(F(t)} - \hat F(t))^2 F^\alpha (t)(1 - F(t))^\beta dW(t)\].To avoid some pathological and uninteresting cases, we restrict the parameter space to ={F: F(ymin) }, where (0, 1) and y ₁,...y,_n are the censoring times. Under this set up, we obtain several interesting results. When y ₁=···=y _n, we prove the following results: the PL estimator is admissible under the above loss function for , {–1, 0}; if n=1, ==–1, the PL estimator is minimax iff dW ({y})=0; and if n2, , {–1, 0}, the PL estimator is not minimax for certain ranges of . For the general case of a random right censorship model it is shown that the PL estimator is neither admissible nor minimax. Some additional results are also indicated.Partially supported by the Governor's Challenge Grant.Part of the work was done while the author was visiting William Paterson College.     

Continuous-Time Controlled Markov Chains with Discounted Rewards

This paper studies denumerable state continuous-time controlled Markov chains with the discounted reward criterion and a Borel action space. The reward and transition rates are unbounded, and the reward rates are allowed to take positive or negative values. First, we present new conditions for a nonhomogeneous Q(t)-process to be regular. Then, using these conditions, we give a new set of mild hypotheses that ensure the existence of -optimal (0) stationary policies. We also present a martingale characterization of an optimal stationary policy. Our results are illustrated with controlled birth and death processes.     

On properties of the probabilistic constrained linear programming problem and its dual

In this paper, the two problems inf{inf{cx:x R ⁿ,A ₁ xy,A ₂ xb}:y suppF R ^m,F(y)p} and sup{inf{uy:y suppF R ^m,F(y)p}+vb:uA ₁+vA ₂=c, (u,v0} are investigated, whereA ₁,A ₂,b,c are given matrices and vectors of finite dimension,F is the joint probability distribution of the random variables ₁,..., _m, and 0<p<1. The first problem was introduced as the deterministic equivalent and the second problem was introduced as the dual of the probabilistic constrained linear programming problem inf{cx:P(A ₁ x)p,A ₂ xb}.b}. Properties of the sets and the functions involved in the two problems and regularity conditions of optimality are discussed.