When does the zero-one <Emphasis Type="Italic">k</Emphasis>-law fail?

The limit probabilities of the first-order properties of a random graph in the Erd?s–Rényi model G(n, n^?α), α ∈ (0, 1), are studied. A random graph G(n, n^?α) is said to obey the zero-one k-law if, given any property expressed by a formula of quantifier depth at most k, the probability of this property tends to either 0 or 1. As is known, for α = 1? 1/(2^k?1 + a/b), where a > 2^k?1, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a ≤ 2^k?1 ? 2. It is proved that the k-law also fails for b > 1 and a ≤ 2^k?1 ? (b + 1)².     

Univariate Stochastic Programming with Random Decision Variable

The problem of minimising E(X) subject to the constraints X ? 0, P(X ? b) ? a(0 < a < 1) has been considered, where b is a non-negative random variable with continuous probability distribution. A necessary and sufficient condition for randomised decisions to be superior to the non-randomised one has been derived.     

Non-Monotonic Behavior of One-Signed Solutions of Quasilinear Differential Equations

We consider a class of the second-order quasilinear differential equations. By deriving relations between certain types of monotonic solutions of the quasilinear equation and corresponding reciprocal half-linear equation on a finite interval (a, b), we obtain criteria for all solutions of the main equation, which do not change sign in (a, b), to be non-monotonic in (a, b). This work is also extended to a perturbed half-linear equation as well as to the half-line \((a,\infty )\).     

A Transfer Principle for the Continuations of Real Functions to the Levi-Civita Field

We discuss the properties of the continuations of real functions to the Levi-Civita field. In particular, we show that, whenever a function f is analytic on a compact interval [a, b] ? ?, f and its analytic continuation f?_∞ satisfy the same properties that can be expressed in the language of real closed ordered fields. If f is not analytic, then this equivalence does not hold. These results suggest an analogy with the internal and external functions of nonstandard analysis: while the canonical continuations of analytic functions resemble internal functions, the continuations of non-analytic functions behave like external functions. Inspired by this analogy, we suggest some directions for further research.     

Koszul property of a class of graded algebras with nonpure resolutions

Given any integers a, b, c, and d with a > 1, c ≥ 0, b ≥ a + c, and d ≥ b + c, the notion of (a, b, c, d)-Koszul algebra is introduced, which is another class of standard graded algebras with “nonpure” resolutions, and includes many Artin-Schelter regular algebras of low global dimension as specific examples. Some basic properties of (a, b, c, d)-Koszul algebras/modules are given, and several criteria for a standard graded algebra to be (a, b, c, d)-Koszul are provided.     

Decomposing Hitting Times of Walks on Graphs into Simpler Ones

Using the electric approach, we derive a formula that expresses an expected hitting time of a random walk between two vertices a and b of a graph G as a convex linear combination of expected hitting times of walks between a and b on subgraphs of G, provided certain condition on a and b is satisfied. Then we use this formula in several applications.     

Optimum super-simple mixed covering arrays of type <Emphasis Type="Italic">a</Emphasis><Superscript>1</Superscript><Emphasis Type="Italic">b</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis>−1</Superscript>

A mixed covering array (MCA) of type (_v 1, v ₂,..., v _k ), denoted by MCA_λ (N; t, k, (v ₁, v ₂,..., v _k )), is an N × k array with entries in the i-th column from a set _{V i} of v _i symbols and has the property that each N × t sub-array covers all the t-tuples at least λ times, where 1 ≤ i ≤ k. An MCA _λ (N; t, k, (_v 1, v ₂,..., v _k )) is said to be super-simple, if each of its N × (t + 1) sub-arrays contains each (t + 1)-tuple at most once. Recently, it was proved by Tang, Yin and the author that an optimum super-simple MCA of type (a, b, b,..., b) is equivalent to a mixed detecting array (DTA) of type (a, b, b,..., b) with optimum size. Such DTAs can be used to generate test suites to identify and determine the interaction faults between the factors in a component-based system. In this paper, some combinatorial constructions of optimum super-simple MCAs of type (a, b, b,..., b) are provided. By employing these constructions, some optimum super-simple MCAs are then obtained. In particular, the spectrum across which optimum super-simple MCA₂(2b ²; 2, 4, (a, b, b, b))′s exist, is completely determined, where 2 ≤ a ≤ b.     

Independence numbers of random subgraphs of a distance graph

We consider the so-called distance graph G(n, 3, 1), whose vertices can be identified with three-element subsets of the set {1, 2,..., n}, two vertices being joined by an edge if and only if the corresponding subsets have exactly one common element. We study some properties of random subgraphs of G(n, 3, 1) in the Erd?s–Rényi model, in which each edge is included in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, 3, 1).     

On the numerical solution of a minimax control problem with a positional functional

The probabilistic analysis of an approximation algorithm for the minimum-weight m-peripatetic salesman problem with different weight functions of their routes (Hamiltonian cycles) is presented. The time complexity of the algorithm is O(mn ²). It is assumed that the elements of the distance matrix are independent equally distributed random variables with values in an upper unbounded domain [a _n , ∞), where a _n > 0. The analysis is carried out for the example of truncated normal and exponential distributions. Estimates for the relative error and failure probability, as well as conditions for the asymptotic exactness of the algorithm, are found.     

Block partitions of sequences

Given a sequence A = (a ₁, …, a _n ) of real numbers, a block B of A is either a set B = {a _i , a _i+1, …, a _j } where i ≤ j or the empty set. The size b of a block B is the sum of its elements. We show that when each a _i ∈ [0, 1] and k is a positive integer, there is a partition of A into k blocks B ₁, …, B _k with |b _i ?b _j | ≤ 1 for every i, j. We extend this result in several directions.     

Asymptotics for the partial sum and its maximum of dependent random variables<Superscript>*</Superscript>

Let X ₁,…,X _n be pairwise asymptotically independent or pairwise upper extended negatively dependent real-valued random variables. Under the condition that the distribution of the maximum of X ₁,…,X _n belongs to some subclass of heavy-tailed distributions, we investigate the asymptotic behavior of the partial sum and its maximum generated by dependent X ₁,…,X _n . As an application, we consider a discrete-time risk model with insurance and financial risks and derive the asymptotics for the finite-time ruin probability.     

Regularity in the Local CR Embedding Problem

We consider a formally integrable, strictly pseudoconvex CR manifold M of hypersurface type, of dimension 2n?1≥7. Local CR, i.e., holomorphic, embeddings of M are known to exist from the works of Kuranishi and Akahori. We address the problem of regularity of the embedding in standard Hölder spaces C ^a (M), a∈R. If the structure of M is of class C ^m , m∈Z, 4≤m≤∞, we construct a local CR embedding near each point of M. This embedding is of class C ^a , for every a, 0≤a<m+(1/2). Our method is based on Henkin’s local homotopy formula for the embedded case, some very precise estimates for the solution operators in it, and a substantial modification of a previous Nash–Moser argument due to the second author.     

Empirical examination of Edgeworth series

The material presented is based on a numerical investigation that was made for five types of probability approximations which involve the first seven terms of the Edgeworth series expansion for the distribution of a continuous random variableT. For each approximation, the probability expressions considered in the investigation were Pr(T≦t), Pr(?t≦T≦t) and Pr(?t+1≦T≦t), whereT has zero mean, unit variance, and specified central momentsμ ₃,μ ₄,μ ₅. Computations were made for thoset values in the set ?4.00(0.25) 4.00 that are pertinent for the probability expression being considered and for all combinations of the following values forμ ₃,μ ₄,μ ₅∶μ ₃=?2.0, ?1.0, ?0.5,0.0, 0.5, 1.0, 2.0;μ ₄=1, 2, 3, 5, 10;μ ₅=0.0, 3μ ₃?6.0, 3μ ₃, 3μ ₃+6.0. The principal results of this paper consist of a specification (for each approximation, probability expression, andμ ₃,μ ₄,μ ₅ combination) of limits ont such that within these limits the computed values of the probability expression are meaningful; that is, satisfy required monotonicity properties as a function oft and are neither negative nor greater than unity. Also the values of Pr(T≦0) and of Pr(?1.75≦T≦1.75) are listed for the cases considered. These results indicate that the types of approximations investigated are of doubtful usefulness for the situations examined; that is, for cases where the third and higher order moments of the random variable considered differ substantially from those for the normal variable having the same mean and variance.     

Lie Triple Derivations on von Neumann Algebras

Let A be a von Neumann algebra with no central abelian projections. It is proved that if an additive map δ :A → A satisfies δ([[a, b], c]) = [[δ(a), b], c] + [[a, δ(b)], c] +[[a, b], δ(c)] for any a, b, c∈ A with ab = 0(resp. ab = P, where P is a fixed nontrivial projection in A), then there exist an additive derivation d from A into itself and an additive map f :A → ZA vanishing at every second commutator [[a, b], c] with ab = 0(resp.ab = P) such that δ(a) = d(a) + f(a) for any a∈ A.     

Generalized Bernstein Operators on the Classical Polynomial Spaces

We study generalizations of the classical Bernstein operators on the polynomial spaces \(\mathbb {P}_{n}[a,b]\), where instead of fixing \(\mathbf {1}\) and x, we reproduce exactly \(\mathbf {1}\) and a polynomial \(f_1\), strictly increasing on [a, b]. We prove that for sufficiently large n, there always exist generalized Bernstein operators fixing \(\mathbf {1}\) and \(f_1\). These operators are defined by non-decreasing sequences of nodes precisely when \(f_1^\prime > 0\) on (a, b), but even if \(f_1^\prime \) vanishes somewhere inside (a, b), they converge to the identity.     

Free Choosability of Outerplanar Graphs

A graph G is free (a, b)-choosable if for any vertex v with b colors assigned and for any list of colors of size a associated with each vertex \(u\ne v\), the coloring can be completed by choosing for u a subset of b colors such that adjacent vertices are colored with disjoint color sets. In this note, a necessary and sufficient condition for a cycle to be free (a, b)-choosable is given. As a corollary, we obtain almost optimal results about the free (a, b)-choosability of outerplanar graphs.     

The hole probability for Gaussian entire functions

Consider the random entire function

$f(z) = \sum\limits_{n = 0}^\infty {{\phi _n}{a_n}{z^n}} $

, where the ? _n are independent standard complex Gaussian coefficients, and the a _n are positive constants, which satisfy

$\mathop {\lim }\limits_{x \to \infty } {{\log {a_n}} \over n} = - \infty $

.

We study the probability P _H (r) that f has no zeroes in the disk{|z| < r} (hole probability). Assuming that the sequence a _n is logarithmically concave, we prove that

$\log {P_H}(r) = - S(r) + o(S(r))$

, where

$S(r) = 2 \cdot \sum\limits_{n:{a_n}{r^n} \ge 1} {\log ({a_n}{r^n})} $

, and r tends to ∞ outside a (deterministic) exceptional set of finite logarithmic measure.

     

First-order and monadic properties of highly sparse random graphs

A random graph is said to obey the (monadic) zero–one k-law if, for any property expressed by a first-order formula (a second-order monadic formula) with a quantifier depth of at most k, the probability of the graph having this property tends to either zero or one. It is well known that the random graph G(n, n^–α) obeys the (monadic) zero–one k-law for any k ∈ ? and any rational α > 1 other than 1 + 1/m (for any positive integer m). It is also well known that the random graph does not obey both k-laws for the other rational positive α and sufficiently large k. In this paper, we obtain lower and upper bounds on the largest at which both zero–one k-laws hold for α = 1 + 1/m.     

Optimal combinations bounds of root-square and arithmetic means for Toader mean

We find the greatest value α ₁ and α ₂, and the least values β ₁ and β ₂, such that the double inequalities α ₁ S(a,b)?+?(1???α ₁) A(a,b)?T(a,b)?β ₁ S(a,b)?+?(1???β ₁) A(a,b) and \(S^{\alpha_{2}}(a,b)A^{1-\alpha_{2}}(a,b)< T(a,b)< S^{\beta_{2}}(a,b)A^{1-\beta_{2}}(a,b)\) hold for all a,b?>?0 with a?≠?b. As applications, we get two new bounds for the complete elliptic integral of the second kind in terms of elementary functions. Here, S(a,b)?=?[(a ²?+?b ²)/2]^1/2, A(a,b)?=?(a?+?b)/2, and \(T(a,b)=\frac{2}{\pi}\int\limits_{0}^{{\pi}/{2}}\sqrt{a^2{\cos^2{\theta}}+b^2{\sin^2{\theta}}}{\rm d}\theta\) denote the root-square, arithmetic, and Toader means of two positive numbers a and b, respectively.     

On (<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-absorbing ideals of commutative rings

Let R be a commutative ring with 1 ≠ 0 and U(R) be the set of all unit elements of R. Let m, n be positive integers such that m > n. In this article, we study a generalization of n-absorbing ideals. A proper ideal I of R is called an (m, n)-absorbing ideal if whenever a ₁?a _m ∈I for a ₁,…, a _m ∈R?U(R), then there are n of the a _i ’s whose product is in I. We investigate the stability of (m, n)-absorbing ideals with respect to various ring theoretic constructions and study (m, n)-absorbing ideals in several commutative rings. For example, in a Bézout ring or a Boolean ring, an ideal is an (m, n)-absorbing ideal if and only if it is an n-absorbing ideal, and in an almost Dedekind domain every (m, n)-absorbing ideal is a product of at most m ? 1 maximal ideals.