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.     

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)².     

Spectra of short monadic sentences about sparse random graphs

A random graph G(n, p) is said to obey the (monadic) zero–one k-law if, for any monadic formula of quantifier depth k, the probability that it is true for the random graph tends to either zero or one. In this paper, following J. Spencer and S. Shelah, we consider the case p = n ^?α. It is proved that the least k for which there are infinitely many α such that a random graph does not obey the zero–one k-law is equal to 4.     

Boundary value problem with normal derivatives for a higher-order elliptic equation on the plane

For an elliptic operator of order 2l with constant (and only leading) real coefficients, we consider a boundary value problem in which the normal derivatives of order (k _j ?1), j = 1,..., l, where 1 ≤ k ₁ < ··· < k _l, are specified. It becomes the Dirichlet problem for kj = j and the Neumann problem for k _j = j + 1. We obtain a sufficient condition for the Fredholm property of which problem and derive an index formula.     

The asymptotic formula in Waring’s problem for one square and seventeen fifth powers

Let R _k,s(n) denote the number of solutions of the equation \({n= x^2 + y_1^k + y_2^k + \cdots + y_s^k}\) in natural numbers x, y ₁, . . . , y _s . By a straightforward application of the circle method, an asymptotic formula for R _k,s(n) is obtained when k ≥ 3 and s ≥ 2^k–1 + 2. When k ≥ 6, work of Heath-Brown and Boklan is applied to establish the asymptotic formula under the milder constraint s ≥ 7 · 2^k–4 + 3. Although the principal conclusions provided by Heath-Brown and Boklan are not available for smaller values of k, some of the underlying ideas are still applicable for k = 5, and the main objective of this article is to establish an asymptotic formula for R _5,17(n) by this strategy.     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

Compound Geometric Distribution of Order <Emphasis Type="Italic">k</Emphasis>

The distribution of the number of trials until the first k consecutive successes in a sequence of Bernoulli trials with success probability p is known as geometric distribution of order k. Let T _k be a random variable that follows a geometric distribution of order k, and Y ₁,Y ₂,… a sequence of independent and identically distributed discrete random variables which are independent of T _k . In the present article we develop some results on the distribution of the compound random variable \(S_{k} =\sum_{t=1}^{T_{k}}Y_{t}\).     

On the k-polygonal numbers and the mean value of Dedekind sums

For any positive integer k ≥ 3, it is easy to prove that the k-polygonal numbers are a_n(k) = (2n+n(n?1)(k?2))/2. The main purpose of this paper is, using the properties of Gauss sums and Dedekind sums, the mean square value theorem of Dirichlet L-functions and the analytic methods, to study the computational problem of one kind mean value of Dedekind sums S(a_n(k)ā_m(k), p) for k-polygonal numbers with 1 ≤ m, n ≤ p ? 1, and give an interesting computational formula for it.     

On the number of nonstationary bounded trajectories of a class of autonomous systems on the plane

We study the number of nonstationary bounded trajectories of autonomous systems of the form z′ = \(\overline {P_n (z)} \), z = x + iy ∈ C, where P _n (z) is a polynomial of degree n with complex coefficients that has k distinct roots, n, k > 1. We prove that the number N of nonstationary bounded trajectories of this system satisfies the following assertions (Theorem 1): (a) N = n + k ? N ₊, N ₊ = N _?, n + 1 ≤ N ₊ ≤ n + k, where N ₊ and N _? are the numbers of system trajectories unbounded as t → +∞ and t → ?∞, respectively; (b) if some r distinct roots \(c_{j_1 } \), ..., \(c_{j_r } \) of the polynomial P _n satisfy the relations V _n+1 (\(c_{j_1 } \)) = ··· = V _n+1 (\(c_{j_r } \)), where V _n+1 is the imaginary part of the indeterminate integral of P _n , then N ≥ \(m_{j_1 } \) + ··· + \(m_{j_r } \) + r ? n ? 1; (c) if k = 2, then the conditions N = 1 and V _n+1 (c ₁) = V _n+1 (c ₂) are equivalent. For n = k = 3, we derive a formula for the number of nonstationary bounded trajectories (Theorem 2).     

Generalized separants of differential polynomials

Let f ∈ K{y} be an element of the ring of differential polynomials in one differential variable y with one differential operator δ. For any variable y _k , the polynomial g = δ ⁿ (f) can be represented in the form g = A _k y _k + go, where go does not depend on y _k . If y _k is the leader of g, then A _k is a separant of the polynomial f. A formula for A _k is obtained for sufficiently large numbers n and k and some applications of this formula are presented.     

Counting sets with small sumset and applications

We study the number of k-element sets A? {1,...,N} with |A+A| ≤ K|A| for some (fixed) K > 0. Improving results of the first author and of Alon, Balogh, Samotij and the second author, we determine this number up to a factor of 2 ^{o ( k )} N ^{o (1)} for most N and k. As a consequence of this and a further new result concerning the number of sets A??/N? with |A+A| ≤ c|A|², we deduce that the random Cayley graph on ?/N? with edge density ½ has no clique or independent set of size greater than (2+o(1)) log₂ N, asymptotically the same as for the Erd?s-Rényi random graph. This improves a result of the first author from 2003 in which a bound of 160log₂ N was obtained. As a second application, we show that if the elements of A ? ? are chosen at random, each with probability 1/2, then the probability that A+A misses exactly k elements of ? is equal to (2+O(1))^?k/2 as k → ∞.     

Superlarge deviations for sums of random variables with arithmetical super-exponential distributions

Local limit theorems are obtained for superlarge deviations of sums S(n) = ξ(1) + ... + ξ(n) of independent identically distributed random variables having an arithmetical distribution with the right-hand tail decreasing faster that that of a Gaussian law. The distribution of ξ has the form ?(ξ = k) = \(e^{ - k^\beta L(k)} \), where β > 2, k ∈ ? (? is the set of all integers), and L(t) is a slowly varying function as t → ∞ which satisfies some regularity conditions. These theorems describing an asymptotic behavior of the probabilities ?(S(n) = k) as k/n → ∞, complement the results on superlarge deviations in [4, 5].     

A Formula for the Partition Function That “Counts”

We derive a combinatorial multisum expression for the number D(n, k) of partitions of n with Durfee square of order k. An immediate corollary is therefore a combinatorial formula for p(n), the number of partitions of n. We then study D(n, k) as a quasipolynomial. We consider the natural polynomial approximation \({\tilde{D}(n, k)}\) to the quasipolynomial representation of D(n, k). Numerically, the sum \({\sum_{1\leq k \leq \sqrt{n}} \tilde{D}(n, k)}\) appears to be extremely close to the initial term of the Hardy-Ramanujan-Rademacher convergent series for p(n).     

On the automorphism group of the Aschbacher graph

A Moore graph is a regular graph of degree k and diameter d with v vertices such that v ≤ 1 + k + k(k ? 1) + ... + k(k ? 1)^d?1. It is known that a Moore graph of degree k ≥ 3 has diameter 2; i.e., it is strongly regular with parameters λ = 0, µ = 1, and v = k ² + 1, where the degree k is equal to 3, 7, or 57. It is unknown whether there exists a Moore graph of degree k = 57. Aschbacher showed that a Moore graph with k = 57 is not a graph of rank 3. In this connection, we call a Moore graph with k = 57 the Aschbacher graph and investigate its automorphism group G without additional assumptions (earlier, it was assumed that G contains an involution).     

On Functional Versions of the Arc-Sine Law

Let X ₁,X ₂,… be a sequence of random variables. Let S _k =X ₁+???+X _k and assume that S _k /b _k converges in distribution for some numerical sequence (b _k ). We study the weak convergence of the random processes {Λ _n (z), z∈?}, where

$\Lambda_{n}(z)=\frac{1}{n}\sum_{k=1}^{n}I\left\{\frac{S_{k}}{b_{k}}\leq z\right\}.$

We consider the same problem when the normalized partial sums S _k /b _k are replaced by other functionals of the sequence (X _n ). In particular, we investigate the case of sample extremes in detail.

     

On existence of a universal function for <Emphasis Type="Italic">L</Emphasis> <Superscript> <Emphasis Type="Italic">p</Emphasis> </Superscript>[0, 1] with <Emphasis Type="Italic">p</Emphasis>∈(0, 1)

We show that, for every number p ∈ (0, 1), there is g ∈ L¹[0, 1] (a universal function) that has monotone coefficients c_k(g) and the Fourier–Walsh series convergent to g (in the norm of L¹[0, 1]) such that, for every f ∈ L^p[0, 1], there are numbers δ_k = ±1, 0 and an increasing sequence of positive integers N_q such that the series ∑ _k=0^+∞δ_kc_k(g)W_k (with {W_k} theWalsh system) and the subsequence \(\sigma _{{N_q}}^{\left( \alpha \right)}\), α ∈ (?1, 0), of its Cesáro means converge to f in the metric of L^p[0, 1].     

The Number of Labeled Outerplanar <Emphasis Type="Italic">k</Emphasis>-Cyclic Graphs

A k-cyclic graph is a graph with cyclomatic number k. An explicit formula for the number of labeled connected outerplanar k-cyclic graphs with a given number of vertices is obtained. In addition, such graphs with fixed cyclomatic number k and a large number of vertices are asymptotically enumerated. As a consequence, it is found that, for fixed k, almost all labeled connected outerplanar k-cyclic graphs with a large number of vertices are cacti.     

Membership of distributions of polynomials in the Nikolskii–Besov class

The main result of this paper asserts that the distribution density of any non-constant polynomial f(ξ₁,ξ₂,...) of degree d in independent standard Gaussian random variables ξ₁ (possibly, in infinitely many variables) always belongs to the Nikol’skii–Besov space B^1/d (R¹) of fractional order 1/d (see the definition below) depending only on the degree of the polynomial. A natural analog of this assertion is obtained for the density of the joint distribution of k polynomials of degree d, also with a fractional order that is independent of the number of variables, but depends only on the degree d and the number of polynomials. We also give a new simple sufficient condition for a measure on R^k to possess a density in the Nikol’skii–Besov class B^α(R)^k. This result is applied for obtaining an upper bound on the total variation distance between two probability measures on R^k via the Kantorovich distance between them and a certain Nikol’skii–Besov norm of their difference. Applications are given to estimates of distributions of polynomials in Gaussian random variables.     

Form preservation under approximation by local exponential splines of an arbitrary order

We continue the study of the properties of local L-splines with uniform knots (such splines were constructed in the authors’ earlier papers) corresponding to a linear differential operator L of order r with constant coefficients and real pairwise different roots of the characteristic polynomial. Sufficient conditions (which are also necessary) are established under which an L-spline locally inherits the property of the generalized k-monotonicity (k ≤ r ? 1) of the input data, which are the values of the approximated function at the nodes of a uniform grid shifted with respect to the grid of knots of the L-spline. The parameters of an L-spline that is exact on the kernel of the operator L are written explicitly.     

Universal zero-one <Emphasis Type="Italic">k</Emphasis>-law

The limit probabilities of first-order properties of a random graph in the Erd?s–Rényi model G(n, n^?α), α ∈ (0, 1), are studied. For any positive integer k ≥ 4 and any rational number t/s ∈ (0, 1), an interval with right endpoint t/s is found in which the zero-one k-law holds (the zero-one k-law describes the behavior of the probabilities of first-order properties expressed by formulas of quantifier depth at most k).Moreover, it is proved that, for rational numbers t/s with numerator not exceeding 2, the logarithm of the length of this interval is of the same order of smallness (as n→∞) as that of the length of the maximal interval with right endpoint t/s in which the zero-one k-law holds.