Irregular,extremal perfect systems of difference sets II

An (m, n; u, v; c)-system is a collection of components,m of valencyu – 1 andn of valencyv – 1, whose difference sets form a perfect system with thresholdc. A necessary condition for the existence of an (m, n; u, v; c)-system foru = 3 or 4 is thatm 2c – 1; and there are (2c – 1,n; 3, 6;c)-systems for all sufficiently largec at least whenn = 1 or 2. It is shown here that if there is a (2c – 1,n; u, 6;c)-system thenn = 0 whenu = 4 andn 2c – 1 whenu = 3. Moreover, if there is a (2c – 1,n; 3, 6;c)-system with a certain splitting property thenn c – 1, this last result being of possible interest in connection with the multiplication theorem for perfect systems.     

Some examples of homotopy Π-algebras

The homotopy Π-algebra of a pointed topological space, X, consists of the homotopy groups of X together with the additional structure of the primary homotopy operations. We extend two well-known results for homotopy groups to homotopy Π-algebras and look at some examples illustrating the depth of structure on homotopy groups; from graded group to graded Lie ring, to Π-algebra and beyond. We also describe an abstract Π-algebra and give three abstract Π-algebra structures on the homotopy groups of the loop space of X which can be realized as the homotopy Π-algebras of three different spaces.     

Some Asymptotic Formulae for Gaussian Distributions

This paper considers asymptotic expansions of certain expectations which appear in the theory of large deviation for Gaussian random vectors with values in a separable real Hilbert space. A typical application is to calculation of the “tails” of distributions of smooth functionals,p(r)=P{Φ(r⁻¹ξ)0},r→∞, e.g., the probability that a centered Gaussian random vector hits the exterior of a large sphere surrounding the origin. The method provides asymptotic formulae for the probability itself and not for its logarithm in a situation, where it is natural to expect thatp(r)=c′r^D exp{−c″r²}. Calculations are based on a combination of the method of characteristic functionals with the Laplace method used to find asymptotics of integrals containing a fast decaying function with “small” support.     

Finitary bases and formal generating functions

Let k be a nonzero, commutative ring with 1, and let R be a k-algebra with a countably-infinite ordered free k-basis B = [p_n: n 0]. We characterize and analyze those bases from which one can construct a k-algebra of ‘formal B-series’ of the form f=∑c_np_n, with c_n ε k, showing inter alia that many classical polynomial bases fail to have this property.     

Initial Enlargement of Filtrations and Entropy of Poisson Compensators

Let μ be a Poisson random measure, let \mathbbF\mathbb{F} be the smallest filtration satisfying the usual conditions and containing the one generated by μ, and let \mathbbG\mathbb{G} be the initial enlargement of \mathbbF\mathbb{F} with the σ-field generated by a random variable G. In this paper, we first show that the mutual information between the enlarging random variable G and the σ-algebra generated by the Poisson random measure μ is equal to the expected relative entropy of the \mathbbG\mathbb{G}-compensator relative to the \mathbbF\mathbb{F}-compensator of the random measure μ. We then use this link to gain some insight into the changes of Doob–Meyer decompositions of stochastic processes when the filtration is enlarged from  \mathbbF\mathbb{F} to  \mathbbG\mathbb{G}. In particular, we show that if the mutual information between G and the σ-algebra generated by the Poisson random measure μ is finite, then every square-integrable \mathbbF\mathbb{F}-martingale is a \mathbbG\mathbb{G}-semimartingale that belongs to the normed space S¹\mathcal{S}^{1} relative to  \mathbbG\mathbb{G}.     

Shuffling algorithm for boxed plane partitions

We introduce discrete time Markov chains that preserve uniform measures on boxed plane partitions. Elementary Markov steps change the size of the box from a×b×c to (a−1)×(b+1)×c or (a+1)×(b−1)×c. Algorithmic realization of each step involves O((a+b)c) operations. One application is an efficient perfect random sampling algorithm for uniformly distributed boxed plane partitions.Trajectories of our Markov chains can be viewed as random point configurations in the three-dimensional lattice. We compute the bulk limits of the correlation functions of the resulting random point process on suitable two-dimensional sections. The limiting correlation functions define a two-dimensional determinantal point processes with certain Gibbs properties.     

Tail bounds for occupancy and the satisfiability threshold conjecture

The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well-known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3-SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c* ≈? 4.2. We provide a strong upper bound on the value of c*, showing that for c > 4.758 a random 3-SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds.     

Continuity of generalized derivations on JB*-algebras

We prove that every generalized Jordan derivation D from a JB?-algebra 𝒜 into itself or into its dual space is automatically continuous. In particular, we establish that every generalized Jordan derivation from a C?-algebra to a Jordan Banach module is continuous. As a consequence, every generalized derivation from a C?-algebra to a Banach bimodule is continuous.     

Bisecting sparse random graphs

Consider partitions of the vertex set of a graph G into two sets with sizes differing by at most 1: the bisection width of G is the minimum over all such partitions of the number of “cross edges” between the parts. We are interested in sparse random graphs G_{n, c/n} with edge probability c/n. We show that, if c>ln 4, then the bisection width is Ω(n) with high probability; while if c<ln 4, then it is equal to 0 with high probability. There are corresponding threshold results for partitioning into any fixed number of parts. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 31–38, 2001     

Topology of Random 2-Complexes

We study the Linial–Meshulam model of random two-dimensional simplicial complexes. One of our main results states that for p≪n ⁻¹ a random 2-complex Y collapses simplicially to a graph and, in particular, the fundamental group π ₁(Y) is free and H ₂(Y)=0, asymptotically almost surely. Our other main result gives a precise threshold for collapsibility of a random 2-complex to a graph in a prescribed number of steps. We also prove that, if the probability parameter p satisfies p≫n ^−1/2+ϵ , where ϵ>0, then an arbitrary finite two-dimensional simplicial complex admits a topological embedding into a random 2-complex, with probability tending to one as n→∞. We also establish several related results; for example, we show that for p<c/n with c<3 the fundamental group of a random 2-complex contains a non-abelian free subgroup. Our method is based on exploiting explicit thresholds (established in the paper) for the existence of simplicial embeddings and immersions of 2-complexes into a random 2-complex.     

Random graphs on surfaces

Counting labelled planar graphs, and typical properties of random labelled planar graphs, have received much attention recently. We start the process here of extending these investigations to graphs embeddable on any fixed surface S. In particular we show that the labelled graphs embeddable on S have the same growth constant as for planar graphs, and the same holds for unlabelled graphs. Also, if we pick a graph uniformly at random from the graphs embeddable on S which have vertex set {1,…,n}, then with probability tending to 1 as n→∞, this random graph either is connected or consists of one giant component together with a few nodes in small planar components.     

On some inequalities of probabilistic number theory

Let Q ₊ denote the set of positive rational numbers. We define discrete probability measures ν _x on the σ-algebra of subsets of Q ₊.We introduce additive functions ƒ: Q ₊ → G and obtain a bound for ν_x(ƒ (r) ∉ X+X−X) using a probability related to some independent random variables. This inequality is an analogue to that proved by I. Ruzsa for additive arithmetical functions. Published in Lietuvos Matematikos Rinkinys, Vol. 46, No. 2, pp. 256–266, April–June, 2006.     

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     

A self-normalized Erd s—Rényi type strong law of large numbers

The original Erd s—Rényi theorem states that max_0kn∑^k+[clogn]_i=k+1X_i/[clogn]→α(c),c>0, almost surely for i.i.d. random variables {X_n, n1} with mean zero and finite moment generating function in a neighbourhood of zero. The latter condition is also necessary for the Erd s—Rényi theorem, and the function α(c) uniquely determines the distribution function of X₁. We prove that if the normalizing constant [c log n] is replaced by the random variable ∑^k+[clogn]_i=k+1(X²_i+1), then a corresponding result remains true under assuming only the exist first moment, or that the underlying distribution is symmetric.     

On First Range Times of Linear Diffusions

In this paper we consider first range times (with randomised range level) of a linear diffusion on R. Inspired by the observation that the exponentially randomised range time has the same law as a similarly randomised first exit time from an interval, we study a large family of non-negative 2-dimensional random variables (X,X′) with this property. The defining feature of the family is F^c(x,y)=F^c(x+y,0), ∀ x ≥ 0, y ≥ 0, where F^c(x,y):=P (X > x, X′ > y) We also explain the Markovian structure of the Brownian local time process when stopped at an exponentially randomised first range time. It is seen that squared Bessel processes with drift are serving hereby as a Markovian element.     

Maximum matchings in sparse random graphs: Karp–Sipser revisited

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G_{n, c/n}, where c>0 is constant. The algorithm was first proposed by Karp and Sipser [Proceedings of the Twenty-Second Annual IEEE Symposium on Foundations of Computing, 1981, pp. 364–375]. We give significantly improved estimates of the errors made by the algorithm. For the subcritical case where c<e we show that the algorithm finds a maximum matching with high probability. If c>e then with high probability the algorithm produces a matching which is within n^1/5+o(1) of maximum size. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 111–177, 1998     

Correlated equilibria of games with many players

Let G _m,n be the class of strategic games with n players, where each player has m≥2 pure strategies. We are interested in the structure of the set of correlated equilibria of games in G _m,n when n→∞. As the number of equilibrium constraints grows slower than the number of pure strategy profiles, it might be conjectured that the set of correlated equilibria becomes large. In this paper, we show that (1) the average relative measure of the set of correlated equilibria is smaller than 2⁻ⁿ; and (2) for each 1<c<m, the solution set contains c ⁿ correlated equilibria having disjoint supports with a probability going to 1 as n grows large. The proof of the second result hinges on the following inequality: Let c ₁, …, c _l be independent and symmetric random vectors in R ^k, l≥k. Then the probability that the convex hull of c ₁, …, c _l intersects R ^k ₊ is greater than or equal to . Received: December 1998/Final version: March 2000     

Generating Random Elements in SL n (F q ) by Random Transvections

This paper studies a random walk based on random transvections in SL _n(F _q ) and shows that, given > 0, there is a constant c such that after n + c steps the walk is within a distance from uniform and that after n – c steps the walk is a distance at least 1 – from uniform. This paper uses results of Diaconis and Shahshahani to get the upper bound, uses results of Rudvalis to get the lower bound, and briefly considers some other random walks on SL _n(F _q ) to compare them with random transvections.     

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 + ∞ .