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 .     

Connected components of arithmetic graphs

Let . LetG _m (R) be the graph whose vertices are the numbers 1, 2, ...,m and whose edges are all pairs {a, b} such thata+br (modm) for somerR. LetC _m (R) be the number of connected components ofG _m (R). Letd be the greatest common divisor ofm and the differencesr _j –r _j or allr _i ,r _j R. ThenC _m (R) is equal to (i) (d+1)/2 ifd is odd, (ii)d/2 ifd is even andr is odd for allrR, or (iii) (d/2)+1 ifd is even andr is even for allrR.This research was supported in part by the National Science Foundation under grant No. MCS78-07908.     

The Ramsey property for collections of sequences not containing all arithmetic progressions

A family of sequences has the Ramsey property if for every positive integerk, there exists a least positive integerf (k) such that for every 2-coloring of {1,2, ...,f (k)} there is a monochromatick-term member of . For fixed integersm > 1 and 0 q < m, let _q(m) be the collection of those increasing sequences of positive integers {x ₁,..., x_k} such thatx _i+1 – x_i q(modm) for 1 i k – 1. Fort a fixed positive integer, denote byA _t the collection of those arithmetic progressions having constant differencet. Landman and Long showed that for allm 2 and 1 q < m, _q(m) does not have the Ramsey property, while _q(m) A _m does. We extend these results to various finite unions of _q(m) 's andA _t 's. We show that for allm 2, _q=1 ^m–1 _q(m) does not have the Ramsey property. We give necessary and sufficient conditions for collections of the form _q(m) ( _{t T} A _t) to have the Ramsey property. We determine when collections of the form _a(m₁) _b(m₂) have the Ramsey property. We extend this to the study of arbitrary finite unions of _q(m)'s. In all cases considered for which has the Ramsey property, upper bounds are given forf .     

Arithmetic Properties of Summands of Partitions

Let d d, d2 2. We prove that for almost all partitions of an integer the parts are well distributed in residue classes mod d. The limitations of the uniformity of this distribution are also studied.     

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.     

Integral representation of linear operators

In this paper we obtain necessary and sufficient conditions in order that a linear operator, acting in spaces of measurable functions, should admit an integral representation. We give here the fundamental results. Let (T_i, _i) (i=1,2) be spaces of finite measure, and let (T,) be the product of these spaces. Let E be an ideal in the space S(T₁, ₁) of measurable functions (i.e., from |e₁||e₂|, e₁ S (T₁, ₁), e₂E it follows that e₁E). THEOREM 2. Let U be a linear operator from E into S(T₂, ₂). The following statements are equivalent: 1) there exists a-measurable kernel K(t,S) such that (Ue)(S)=K(t,S) e(t)d(t) (eE); 2) if 0e_nE (n=1,2,...) and e_n0 in measure, then (Ue_n)(S) 0 ₂ a.e. THEOREM 3. Assume that the function (t,S) is such that for any eE and for s a.e., the ₂-measurable function Y(S)=(t,S)e(t)d ₁(t) is defined. Then there exists a-measurable function K(t,S) such that for any eE we have (t,S)e(t)d ₁(t)=K(t,S)e(t)d ₁(t) ₁a.e.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 47, pp. 5–14, 1974.     

Orthogonality and additivity modulo a subgroup

Summary LetE be a real inner product space of dimension at least 2,F a topological Abelian group, andK a discrete subgroup ofF. Assume also thatF is continuously divisible by 2 (that is, the functionu 2u is a homeomorphism ofF ontoF). Iff: E F fulfils the conditionf(x + y) – f(x) – f(y) K for all orthogonalx, y E and is continuous at the origin then there exist continuous additive functionsa: R F andA: E F such thatf(x) – a(x ²)– A(x) K for everyx E. Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.     

On signpost systems and connected graphs

By a signpost system we mean an ordered pair (W, P), where W is a finite nonempty set, P W × W × W and the following statements hold: if (u, v, w) P, then (v, u, u) P and (v, u, w) P, for all u, v, w W; if u v; then there exists r W such that (u, r, v) P, for all u, v W. We say that a signpost system (W, P) is smooth if the folowing statement holds for all u, v, x, y, z W: if (u, v, x), (u, v, z), (x, y, z) P, then (u, v, y) P. We say thay a signpost system (W, P) is simple if the following statement holds for all u, v, x, y W: if (u, v, x), (x, y, v) P, then (u, v, y), (x, y, u) P.By the underlying graph of a signpost system (W, P) we mean the graph G with V(G) = W and such that the following statement holds for all distinct u, v W: u and v are adjacent in G if and only if (u, v, v) P. The main result of this paper is as follows: If G is a graph, then the following three statements are equivalent: G is connected; G is the underlying graph of a simple smooth signpost system; G is the underlying graph of a smooth signpost system.Research was supported by Grant Agency of the Czech Republic, grant No. 401/01/0218.     

Quadratically constrained quadratic programming: Some applications and a method for solution

The problem (QPQR) considered here is: minimizeQ ₁ (x) subject toQ _i (x) 0,i M ₁ {2,...,m},x P R ⁿ, whereQ _i (x), i M {1} M ₁ are quadratic forms with positive semi-definite matrices, andP a compact nonempty polyhedron of Rⁿ. Applications of (QPQR) and a new method to solve it are presented.Letu S={u R ^m;u 0, u _i= l}be fixed;then the problem:iM minimize u _iQ_i (x (u)) overP, always has an optimal solutionx (u), which is either feasible, iM i.e. u C₁ {u S;Q _i (x (u)) 0,i M ₁} or unfeasible, i.e. there exists ani M ₁ withu C {u S; Q_i(x(u)) 0}.Let us defineC _i C_i S _i withS _i {u S; u _i=0}, i M. A constructive method is used to prove that C _i is not empty and thatx (û) withiM û C _i characterizes an optimal solution to (QPQR). Quite attractive numerical results have been reached with this method.

---

Zusammenfassung Die vorliegende Arbeit befaßt sich mit Anwendungen und einer neuen Lösungsmethode der folgenden Aufgabe (QPQR): man minimiere eine konvexe quadratische ZielfunktionQ _i (x) unter Berücksichtigung konvexer quadratischer RestriktionenQ _i (x) 0, iM ₁ {2,...,m}, und/oder linearer Restriktionen.·Für ein festesu S {u R ^m;u 0, u _i=1},M {1} M₁ besitzt das Problem:iM minimiere die konvexe quadratische Zielfunktion u _i Q_i (x (u)) über dem durch die lineareniM Restriktionen von (QPQR) erzeugten, kompakten und nicht leeren PolyederP R ⁿ, immer eine Optimallösungx (u), die entweder zulässig ist: u C₁ {u S;Q ₁ (x (u)) 0,i M ₁} oder unzulässig ist, d.h. es existiert eini M ₁ mitu C_i {u S;Q _i (x(u))0}.Es seien folgende MengenC _i C_i S _i definiert, mitS _i {u S;u _i=0}, i M. Es wird konstruktiv bewiesen, daß C _i 0 undx (û) mitû C _i eine Optimallösung voniM iM (QPQR) ist; damit ergibt sich eine Methode zur Lösung von (QPQR), die sich als sehr effizient erwiesen hat. Ein einfaches Beispiel ist angegeben, mit dem alle Schritte des Algorithmus und dessen Arbeitsweise graphisch dargestellt werden können.

---

---

An earlier version of this paper was written during the author's stay at the Institute for Operations Research, Swiss Federal Institute of Technology, Zürich.     

Sugli insiemi di permutazioni strettamente k-transitivi (k ≥ 3)

Summary Let G be a sharply 3-transitive permutation set on a finite set E of even cardinality and let 1 be in G. The following theorems are proved. G is one of the known examples if and only if there exists a non-identity normal subgroup N of G and an element of E such that NG G.G is a group if and only if G for every G and for every G and for every G .By using the classification of finite single groups a result concerning sharply k-transitive permutation sets k>3 is also proved.

---

---

Dedicato a Guido Zappa in occasione del suo 70° compleanno

---

Lavoro eseguito nell'ambito dei progetti finanziati dal Ministero della Pubblica Istruzione.     

Analysis of a class of fractional programming problems

We propose a solution strategy for fractional programming problems of the form max _xx g(x)/ (u(x)), where the function satisfies certain convexity conditions. It is shown that subject to these conditions optimal solutions to this problem can be obtained from the solution of the problem max _xx g(x) + u(x), where is an exogenous parameter. The proposed strategy combines fractional programming andc-programming techniques. A maximal mean-standard deviation ratio problem is solved to illustrate the strategy in action.     

On measures integrating all functions of a given vector lattice

LetE be a vector lattice of real-valued functions defined on a setX, and (E):={{f1}:fE}. Among others, it is shown that, under some additional assumptions onE, every measure that integrates all functionsfE is (E)--smooth iffX is (E)-complete. An application of this general result to various topological situations yields some new measure-theoretic characterizations of realcompact, Borel-complete andN-compact spaces, respectively.     

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     

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.     

Symmetrische Permutationsmengen

A permutation set (M, I) consisting of a setM and a set of permutations ofM, is calledsymmetric, if for any two permutations, the existence of anx M with (x) (x) and ^–1 (x) = ^–1 (x) implies ^–1 = ^–1 , andsharply 3-transitive, if for any two triples (x ₁,x ₂,x ₃), (y ₁,y ₂,y ₃) M ³ with|{x ₁,x ₂,x ₃ }| = |{y ₁,y ₂,y ₃ }| = 3 there is exactly one permutation with(x ₁) =y ₁,(x ₂) =y ₂,(x ₃) =y ₃. The following theorem will be proved.THEOREM.Let (M, ) be a sharply 3-transitive symmetric permutation set with |M|3, such that contains the identity. Then is a group and there is a commutative field K such that and the projective linear group PGL(2, K) are isomorphic.     

Joint convergence of conditional expectations

Let P_n, nIN{0}, be probability measures on a-fieldA; f_n, nIN{0}, be a family of uniformly boundedA-measurable functions andA _n, nIN, be a sequence of sub--fields ofA, increasing or decreasing to the-fieldA _o. It is shown in this paper that the conditional expectations converge in P_o-measure to with k, n, m , if P_n|A, nIN, converges uniformly to P_n|A and f_n, nIN, converges in P_o-measure to f_o.     

A White Noise Approach to Stochastic Neumann Boundary-Value Problems

We illustrate the use of white noise analysis in the solution of stochastic partial differential equations by explicitly solving the stochastic Neumann boundary-value problem LU(x)–c(x)U(x)=0, xDR ^d ,(x)U(x)=–W(x), xD, where L is a uniformly elliptic linear partial differential operator and W(x), xR ^d , is d-parameter white noise.     

Aufeinanderfolgende Elemente in multiplikativen Zahlenmengen

LetM be a multiplicative set with 1M andmnM if and only ifmM,nM for (m,n)=1. It is shown by elementary means that there exists the asymptotic density of the setM(M–1) for every multiplicative setM. The density is positive if and only ifM possesses a positive density and 2M for some . This result is slightly generalized to sums over multiplicative functionsf with |f|1.     

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.     

Distribution density of the norm of a stable vector

Let B be a Banach space,X be a stable B -valued random vector with exponentd(0,2), and P(·) be the distribution density of the norm of X. In this paper we study the question of the boundedness of P. In particular, we construct examples of a space B with a symmetric stable vector X with exponentd(1,2) with unbounded P and prove that if X is a nondegenerate strictly stable vector with exponentd(0,1), then P is bounded.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 158, pp. 105–114, 1987.The author is grateful to Yu. A. Davydov, V. I. Paulauskas, V. Yu. Bentkus, and D. Pap for stimulating discussions of the subject of this paper. When the paper was finished the author learned that similar results are found in [9].