von Neumann��s mean ergodic theorem on complete random inner product modules

We first prove two forms of von Neumann’s mean ergodic theorems under the framework of complete random inner product modules. As applications, we obtain two conditional mean ergodic convergence theorems for random isometric operators which are defined on L _ℱ ^p (ℰ, H) and generated by measure-preserving transformations on Ω, where H is a Hilbert space, L ^p (ℰ, H) (1 ⩽ p < ∞) the Banach space of equivalence classes of H-valued p-integrable random variables defined on a probability space (Ω, ℰ, P), F a sub σ-algebra of ℰ, and L _ℱ ^p (ℰ(E,H) the complete random normed module generated by L ^p (ℰ, H).     

The relation of Banach-Alaoglu theorem and Banach-Bourbaki-Kakutani-Šmulian theorem in complete random normed modules to stratification structure

Let (Ω,A,μ) be a probability space, K the scalar field R of real numbers or C of complex numbers,and (S,X) a random normed space over K with base (ω,A,μ). Denote the support of (S,X) by E, namely E is the essential supremum of the set {A ∈ A: there exists an element p in S such that X _p (ω) > 0 for almost all ω in A}. In this paper, Banach-Alaoglu theorem in a random normed space is first established as follows: The random closed unit ball S ^*(1) = {f ∈ S ^*: X ^* _f ⩽ 1} of the random conjugate space (S ^*,X ^*) of (S,X) is compact under the random weak star topology on (S ^*,X ^*) iff E∩A=: {E∩A | A ∈ A} is essentially purely μ-atomic (namely, there exists a disjoint family {A _n : n ∈ N} of at most countably many μ-atoms from E ∩ A such that E = ∪ _n=1^∞ A _n and for each element F in E ∩ A, there is an H in the σ-algebra generated by {A _n : n ∈ N} satisfying μ(FΔH) = 0), whose proof forces us to provide a key topological skill, and thus is much more involved than the corresponding classical case. Further, Banach-Bourbaki-Kakutani-Šmulian (briefly, BBKS) theorem in a complete random normed module is established as follows: If (S,X) is a complete random normed module, then the random closed unit ball S(1) = {p ∈ S: X _p ⩽ 1} of (S,X) is compact under the random weak topology on (S,X) iff both (S,X) is random reflexive and E ∩ A is essentially purely μ-atomic. Our recent work shows that the famous classical James theorem still holds for an arbitrary complete random normed module, namely a complete random normed module is random reflexive iff the random norm of an arbitrary almost surely bounded random linear functional on it is attainable on its random closed unit ball, but this paper shows that the classical Banach-Alaoglu theorem and BBKS theorem do not hold universally for complete random normed modules unless they possess extremely simple stratification structure, namely their supports are essentially purely μ-atomic. Combining the James theorem and BBKS theorem in complete random normed modules leads directly to an interesting phenomenum: there exist many famous classical propositions that are mutually equivalent in the case of Banach spaces, some of which remain to be mutually equivalent in the context of arbitrary complete random normed modules, whereas the other of which are no longer equivalent to another in the context of arbitrary complete random normed modules unless the random normed modules in question possess extremely simple stratification structure. Such a phenomenum is, for the first time, discovered in the course of the development of random metric theory.     

On a characterization of orthogonality with respect to particular sequences of random variables in <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>

This note deals with the orthogonality between sequences of random variables. The main idea of the note is to apply the results on equidistant systems of points in a Hilbert space to the case of the space L ²(Ω, F, ℙ) of real square integrable random variables. The main result gives a necessary and sufficient condition for a particular sequence of random variables (elements of which are taken from sets of equidistant elements of L ²(Ω, F, ℙ) to be orthogonal to some other sequence in L ²(Ω, F, ℙ). The result obtained is interesting from the point of view of the time series analysis, since it can be applied to a class of sequences random variables that exhibit a monotonically increasing variance. An application to ergodic theorem is also provided.     

-Operator frames for a Banach space

In this paper, (p,Y)-Bessel operator sequences, operator frames and (p,Y)-Riesz bases for a Banach space X are introduced and discussed as generalizations of the usual concepts for a Hilbert space and of the g-frames. It is proved that the set of all (p,Y)-Bessel operator sequences for a Banach space X is a Banach space and isometrically isomorphic to the operator space B(X,ℓ^p(Y)). Some necessary and sufficient conditions for a sequence of operators to be a (p,Y)-Bessel operator sequence are given. Also, a characterization of an independent (p,Y)-operator frame for X is obtained. Lastly, it is shown that an independent (p,Y)-operator frame for X is just a (p,Y)-Riesz basis for X and has a unique dual (q,Y^*)-operator frame for X^*.     

MAX k‐CUT and approximating the chromatic number of random graphs

We consider the MAX k‐CUT problem on random graphs G_n,p. First, we bound the probable weight of a MAX k‐CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAX k‐CUT in expected polynomial time, with approximation ratio 1 + O((np)^‐1/2). Our main technical tool is a new bound on the probable value of Frieze and Jerrum's semidefinite programming (SDP)‐relaxation of MAX k‐CUT on random graphs. To obtain this bound, we show that the value of the SDP is tightly concentrated. As a further application of our bound on the probable value of the SDP, we obtain an algorithm for approximating the chromatic number of G_n,p, 1/n ≤ p ≤ 0.99, within a factor of O((np)^1/2) in polynomial expected time, thereby answering a question of Krivelevich and Vu. We give similar algorithms for random regular graphs. The techniques for studying the SDP apply to a variety of SDP relaxations of further NP‐hard problems on random structures and may therefore be of independent interest. For instance, to bound the SDP we estimate the eigenvalues of random graphs with given degree sequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

Merging percolation on Zd and classical random graphs: Phase transition

We study a random graph model which is a superposition of bond percolation on Z^d with parameter p, and a classical random graph G(n,c/n). We show that this model, being a homogeneous random graph, has a natural relation to the so‐called “rank 1 case” of inhomogeneous random graphs. This allows us to use the newly developed theory of inhomogeneous random graphs to describe the phase diagram on the set of parameters c ≥ 0 and 0 ≤ p < p_c, where p_c = p_c(d) is the critical probability for the bond percolation on Z^d. The phase transition is of second order as in the classical random graph. We find the scaled size of the largest connected component in the supercritical regime. We also provide a sharp upper bound for the largest connected component in the subcritical regime. The latter is a new result for inhomogeneous random graphs with unbounded kernels. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Unconditional and symmetric sets inn-dimensional normed spaces

Isoperimetric inequalities are used to obtain measure estimates on almost constancy sets of functions on product spaces. These are applied to produce almost unconditional or symmetric block sequences from given sequences. Their length, which is (logn)^1/2 in the general case, improves ton ^a where a cotype condition is imposed or when the given sequences arep-type attaining for somep<2. In thep-type attaining case, block sequences (1+ε)-equivalent to the unit vector basis ofl _p ^m can be obtained when log logm ∼ log logn. Research supported in part by NSF Grant MCS 7902489.     

Large Closed Queueing Networks in Semi-Markov Environment and Their Application

The paper studies closed queueing networks containing a server station and k client stations. The server station is an infinite server queueing system, and client stations are single-server queueing systems with autonomous service, i.e. every client station serves customers (units) only at random instants generated by a strictly stationary and ergodic sequence of random variables. The total number of units in the network is N. The expected times between departures in client stations are (N μ _j )⁻¹. After a service completion in the server station, a unit is transmitted to the jth client station with probability p _j (j=1,2,…,k), and being processed in the jth client station, the unit returns to the server station. The network is assumed to be in a semi-Markov environment. A semi-Markov environment is defined by a finite or countable infinite Markov chain and by sequences of independent and identically distributed random variables. Then the routing probabilities p _j (j=1,2,…,k) and transmission rates (which are expressed via parameters of the network) depend on a Markov state of the environment. The paper studies the queue-length processes in client stations of this network and is aimed to the analysis of performance measures associated with this network. The questions risen in this paper have immediate relation to quality control of complex telecommunication networks, and the obtained results are expected to lead to the solutions to many practical problems of this area of research.      

<Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">r</Emphasis></Superscript> convergence for <Emphasis Type="Italic">B</Emphasis>-valued random elements

The paper investigates L ^p convergence and Marcinkiewicz-Zygmund strong laws of large numbers for random elements in a Banach space under the condition that the Banach space is of Rademacher type p, 1 < p < 2. The paper also discusses L ^r convergence and L ^r bound for random elements without any geometric restriction condition on the Banach space.     

Generalized Interpolation in Bergman Spaces and Extremal Functions

In a recent paper A. Schuster and K. Seip [SchS] have characterized interpolating sequences for Bergman spaces in terms of extremal functions (or canonical divisors). As these are natural analogues in Bergman spaces of Blaschke products, this yields a Carleson type condition for interpolation. We intend to generalize this idea to generalized free interpolation in weighted Bergman spaces B^{p, α} as was done by V. Vasyunin [Va1] and N. Nikolski [Ni1] (cf.also [Ha2]) in the case of Hardy spaces. In particular we get a strong necessary condition for free interpolation in B^{p, α} on zero–sets of B^{p, α}–functions that in the special case of finite unions of B^{p, α}–interpolating sequences turns out to be also sufficient.     

Cesàro-type operators on Hardy, BMOA and bloch spaces

Let H ^p, p ∈ (0, ∞], BMOA and B ^a, a ∈ (0, ∞) be the classical p-Hardy, analytic BMO(∂) (bounded mean oscillation on the unit circle) and a-Bloch space on the unit disk. In this paper, we prove that the Cesàro-type operator: C ^α, α ∈ (−1, ∞) is bounded on H ^p, p ∈ (0, ∞) and on B ^a, a ∈ (1, ∞), but, unbounded on H ^∞, BMOA and B ^a, a ∈ (0, 1]. In particular, we give an answer to the Stempak’s open problem.     

On the subspaces ofL p (p>2) spanned by sequences of independent random variables

Let 2<p<∞. The Banach space spanned by a sequence of independent random variables inL ^p , each of mean zero, is shown to be isomorphic tol ²,l ^p ,l ²⊕l ^p , or a new spaceX _p , and the linear topological properties ofX _p are investigated. It is proved thatX _p is isomorphic to a complemented subspace ofL ^p and another uncomplemented subspace ofL ^p , whence there exists an uncomplemented subspace ofl ^p isomorphic tol ^p . It is also proved thatX _p is not isomorphic to the previously knownℒ _p spaces. The work for this research was partially supported by the National Science Foundation GP-12997.     

The degree sequence of a random graph. I. The models

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of random graphs with n vertices and ½m edges. For a wide range of values of m, this distribution is almost everywhere in close correspondence with the conditional distribution {(X₁,…,X_n) | ∑ X_i=m}, where X₁,…,X_n are independent random variables, each having the same binomial distribution as the degree of one vertex. We also consider random graphs with n vertices and edge probability p. For a wide range of functions p=p(n), the distribution of the degree sequence can be approximated by {(X₁,…,X>_n) | ∑ X_i is even}, where X₁,…,X_n are independent random variables each having the distribution Binom (n−1, p′), where p′ is itself a random variable with a particular truncated normal distribution. To facilitate computations, we demonstrate techniques by which statistics in this model can be inferred from those in a simple model of independent binomial random variables. Where they apply, the accuracy of our method is sufficient to determine asymptotically all probabilities greater than n^−k for any fixed k. In this first paper, we use the geometric mean of degrees as a tutorial example. In the second paper, we will determine the asymptotic distribution of the tth largest degree for all functions t=t(n) as n→∞. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 97–117 (1997)     

Existence and comparison results for nonlinear volterra integral equations in a banach space

Let L ⁰(ΩA,P) be the space of equivalent classes of random variables defined on a probability space (Ω,A,P). Let H be the closed subspace of L ⁰(Ω,A,P) spanned by a sequence of i.i.d. (independent and identically distributed) random variables having the symmetric nondegenerate law F. It is proved that H is linearly homeomorphic to l _p for 0<p≤2 if F belongs to the domain of normal attraction of symmetric stable law withexponent p.     

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

Recently much attention has been focused on the theory of quasi-random graph and hypergraph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. We shall investigate propertiesP which do not imply quasi-randomnes for sequences (G _n ) of graphs on their own, but do imply if they hold not only for the whole graphG _n but also for every sufficiently large subgraph ofG _n . Here the properties are strongly connected to countingnot necessarily induced subgraphs of a given type, while in a subsequent paper we shall investigate the properties connected with counting induced subgraphs.Dedicated to the memory of Paul ErdsResearch supported by OTKA N1909.     

An L0（F,R）-valued Function＇s Intermediate Value Theorem and Its Applications to Random Uniform Convexity

Let (Ω , F , P ) be a probability space and L0 ( F, R ) the algebra of equivalence classes of real- valued random variables on (Ω , F , P ). When L0 ( F, R ) is endowed with the topology of convergence in probability, we prove an intermediate value theorem for a continuous local function from L0 ( F, R ) to L0 ( F, R ). As applications of this theorem, we first give several useful expressions for modulus of random convexity, then we prove that a complete random normed module ( S,|| · ||) is random uniformly convex iff Lp ( S ) is uniformly convex for each fixed positive number p such that 1 p + ∞ .     

On the strong law of large numbers for sequences of random variables without the independence condition

New sufficient conditions for the applicability of the strong law of large numbers to a sequence of dependent random variables X ₁, X ₂, …, with finite variances are established. No particular type of dependence between the random variables in the sequence is assumed. The statement of the theorem involves the classical condition Σ _n ^∞ (log₂ n)²/n ² < ∞, which appears in various theorems on the strong law of large numbers for sequences of random variables without the independence condition.     

A new approach to the giant component problem

We study the largest component of a random (multi)graph on n vertices with a given degree sequence. We let n → ∞. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability all the components are small, and other conditions that imply that with high probability there is a giant component and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the results by Molloy and Reed on the size of the largest component in a random graph with a given degree sequence. We further obtain a new sharp result for the giant component just above the threshold, generalizing the case of G(n,p) with np = 1 + ω(n)n^?1/3, where ω(n) → ∞ arbitrarily slowly. Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Strongly almost convergent generalized difference sequences associated with multiplier sequences

Let Λ = (λ _k ) be a sequence of non-zero complex numbers. In this paper we introduce the strongly almost convergent generalized difference sequence spaces associated with multiplier sequences i.e. w ₀[A,Δ ^m ,Λ,p], w ₁[A,Λ ^m ,Λ,p], w _∞[A,Δ ^m ,Λ,p] and study their different properties. We also introduce Δ _Λ ^m -statistically convergent sequences and give some inclusion relations between w ₁[Δ ^m ,λ,p] convergence and Δ _Λ ^m -statistical convergence. Communicated by Pavel Kostyrko