Continuous time random walks and the Cauchy problem for the heat equation

We deal with anomalous diffusions induced by continuous time random walks - CTRW in ?ⁿ. A particle moves in ?ⁿ in such a way that the probability density function u(·, t) of finding it in region Ω of ?ⁿ is given by ∫_Ωu(x, t)dx. The dynamics of the diffusion is provided by a space time probability density J(x, t) compactly supported in {t ≥ 0}. For t large enough, u satisfies the equation

$$u\left( {x,t} \right) = \left[ {\left( {J - \delta } \right)*u} \right]\left( {x,t} \right)$$

, where δ is the Dirac delta in space-time. We give a sense to a Cauchy type problem for a given initial density distribution f. We use Banach fixed point method to solve it and prove that under parabolic rescaling of J, the equation tends weakly to the heat equation and that for particular kernels J, the solutions tend to the corresponding temperatures when the scaling parameter approaches 0.

     

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.     

Almost Sure Approximation of the Superposition of the Random Processes

This article presents sufficient conditions, which provide almost sure (a.s.) approximation of the superposition of the random processes S(N(t)), when càd-làg random processes S(t) and N(t) themselves admit a.s. approximation by a Wiener or stable Lévy processes. Such results serve as a source of numerous strong limit theorems for the random sums under various assumptions on counting process N(t) and summands. As a consequence we obtain a number of results concerning the a.s. approximation of the Kesten–Spitzer random walk, accumulated workload input into queuing system, risk processes in the classical and renewal risk models with small and large claims and use such results for investigation the growth rate and fluctuations of the mentioned processes.     

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.     

Estimation Problems for Periodically Correlated Isotropic Random Fields

Spectral theory of isotropic random fields in Euclidean space developed by M. I. Yadrenko is exploited to find a solution to the problem of optimal linear estimation of the functional

$$ A\zeta ={\sum\limits_{t=0}^{\infty}}\,\,\,{\int_{S_n}} \,\,a(t,x)\zeta (t,x)\,m_n(dx) $$

which depends on unknown values of a periodically correlated (cyclostationary with period T) with respect to time isotropic on the sphere S _n in Euclidean space E ⁿ random field ζ(t, x), t?∈?Z, x?∈?S _n . Estimates are based on observations of the field ζ(t, x)?+?θ(t, x) at points (t, x), t?=???1,???2, ..., x?∈?S _n , where θ(t, x) is an uncorrelated with ζ(t, x) periodically correlated with respect to time isotropic on the sphere S _n random field. Formulas for computing the value of the mean-square error and the spectral characteristic of the optimal linear estimate of the functional Aζ are obtained. The least favourable spectral densities and the minimax (robust) spectral characteristics of the optimal estimates of the functional Aζ are determined for some special classes of spectral densities.

     

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.     

Probabilities of high extremes for a Gaussian stationary process in a random environment

Let ξ(t) be a zero-mean stationary Gaussian process with the covariance function r(t) of Pickands type, i.e., r(t) = 1 ? |t| ^α + o(|t| ^α ), t → 0, 0 < α ≤ 2, and η(t), ζ(t) be periodic random processes. The exact asymptotic behavior of the probabilities P(max _t∈[0,T] η(t)ξ(t) > u), P(max _t∈[0,T] (ξ(t) + η(t)) > u) and P(max _t∈[0,T] (η(t)ξ(t) + ζ(t)) > u) is obtained for u → ∞ for any T > 0 and independent ξ(t), η(t), ζ(t).     

Erdős measures on the Euclidean space and on the group of <Emphasis Type="Italic">A</Emphasis>-adic integers

Let A ∈ M _n (?) be a matrix with eigenvalues greater than 1 in absolute value. The ? ⁿ -valued random variables ξ _t , t ∈ ?, are i.i.d., and P(ξ _t = j) = p _j , j ∈ ? ⁿ , 0 < p ₀ < 1, ∑ _j p _j = 1. We study the properties of the distributions of the ? ⁿ -valued random variable ζ ₁ = ∑ _t=1 ^∞ A ^?t ξ _t and of the random variable ζ = ∑ _t=0 ^∞ A ^t ξ _?t taking integer A-adic values. We obtain a necessary and sufficient condition for the absolute continuity of these distributions. We define an invariant Erd?s measure on the compact abelian group of A-adic integers. We also define an A-invariant Erd?s measure on the n-dimensional torus. We show the connection between these invariant measures and functions of countable stationary Markov chains. In the case when |{j: p _j ≠ 0}| < ∞, we establish the relation between these invariant measures and finite stationary Markov chains.     

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

A tournament approach to pattern avoiding matrices

We consider the following Turán-type problem: given a fixed tournament H, what is the least integer t = t(n,H) so that adding t edges to any n-vertex tournament, results in a digraph containing a copy of H. Similarly, what is the least integer t = t(T _n ,H) so that adding t edges to the n-vertex transitive tournament, results in a digraph containing a copy of H. Besides proving several results on these problems, our main contributions are the following:

• Pach and Tardos conjectured that if M is an acyclic 0/1 matrix, then any n × n matrix with n(log n) ^O(1) entries equal to 1 contains the pattern M. We show that this conjecture is equivalent to the assertion that t(T _n ,H) = n(log n) ^O(1) if and only if H belongs to a certain (natural) family of tournaments.
• We propose an approach for determining if t(n,H) = n(log n) ^O(1). This approach combines expansion in sparse graphs, together with certain structural characterizations of H-free tournaments. Our result opens the door for using structural graph theoretic tools in order to settle the Pach–Tardos conjecture.

     

Stability and convergence of a fully discrete local discontinuous Galerkin method for multi-term time fractional diffusion equations

In this paper, a fully discrete local discontinuous Galerkin method for a class of multi-term time fractional diffusion equations is proposed and analyzed. Using local discontinuous Galerkin method in spatial direction and classical L1 approximation in temporal direction, a fully discrete scheme is established. By choosing the numerical flux carefully, we prove that the method is unconditionally stable and convergent with order O(h ^k+1 + (Δt)^2?α ), where k, h, and Δt are the degree of piecewise polynomial, the space, and time step sizes, respectively. Numerical examples are carried out to illustrate the effectiveness of the numerical scheme.     

Weakly nonlinear Schrödinger equation with random initial data

It is common practice to approximate a weakly nonlinear wave equation through a kinetic transport equation, thus raising the issue of controlling the validity of the kinetic limit for a suitable choice of the random initial data. While for the general case a proof of the kinetic limit remains open, we report on first progress. As wave equation we consider the nonlinear Schrödinger equation discretized on a hypercubic lattice. Since this is a Hamiltonian system, a natural choice of random initial data is distributing them according to the corresponding Gibbs measure with a chemical potential chosen so that the Gibbs field has exponential mixing. The solution ψ _t (x) of the nonlinear Schrödinger equation yields then a stochastic process stationary in x∈? ^d and t∈?. If λ denotes the strength of the nonlinearity, we prove that the space-time covariance of ψ _t (x) has a limit as λ→0 for t=λ ^?2 τ, with τ fixed and |τ| sufficiently small. The limit agrees with the prediction from kinetic theory.     

Global existence of real roots and random Newton flow algorithm for nonlinear system of equations

To solve nonlinear system of equation, F(x) = 0, a continuous Newton flow x _t (t) = V (x) = ?(DF(x))^?1 F(x), x(0) = x ⁰ and its mathematical properties, such as the central field, global existence and uniqueness of real roots and the structure of the singular surface, are studied. We concisely introduce random Newton flow algorithm (NFA) for finding all roots, based on discrete Newton flow x ^j+1 = x ^j + hV (x ^j ) with random initial value x ⁰ and h ∈ (0, 1], and three computable quantities, g _j , d _j and K _j . The numerical experiments with dimension n = 300 are provided.     

Inverse problem with nonlocal observation of finding the coefficient multiplying <Emphasis Type="Italic">u</Emphasis> <Subscript> <Emphasis Type="Italic">t</Emphasis> </Subscript> in the parabolic equation

We study the inverse problem of the reconstruction of the coefficient ?(x, t) = ?⁰(x, t) + r(x) multiplying u_t in a nonstationary parabolic equation. Here ?⁰(x, t) ≥ ?⁰ > 0 is a given function, and r(x) ≥ 0 is an unknown function of the class L_∞(Ω). In addition to the initial and boundary conditions (the data of the direct problem), we pose the problem of nonlocal observation in the form ∫₀^Tu(x, t) dμ(t) = χ(x) with a known measure dμ(t) and a function χ(x). We separately consider the case dμ(t) = ω(t)dt of integral observation with a smooth function ω(t). We obtain sufficient conditions for the existence and uniqueness of the solution of the inverse problem, which have the form of ready-to-verify inequalities. We suggest an iterative procedure for finding the solution and prove its convergence. Examples of particular inverse problems for which the assumptions of our theorems hold are presented.     

The graph Kre(4) does not exist

Suppose that a strongly regular graph Γ with parameters (v, k, λ, μ) has eigenvalues k, r, and s. If the graphs Γ and \(\bar \Gamma \) are connected, then the following inequalities, known as Krein’s conditions, hold: (i) (r + 1)(k + r + 2rs) ≤ (k + r)(s + 1)² and (ii) (s + 1)(k + s + 2rs) ≤ (k + s)(r + 1)². We say that Γ is a Krein graph if one of Krein’s conditions (i) and (ii) is an equality for this graph. A triangle-free Krein graph has parameters ((r ² + 3r)², r ³ + 3r ² + r, 0, r ² + r). We denote such a graph by Kre(r). It is known that, in the cases r = 1 and r = 2, the graphs Kre(r) exist and are unique; these are the Clebsch and Higman–Sims graphs, respectively. The latter was constructed in 1968 together with the Higman–Sims sporadic simple group. A.L. Gavrilyuk and A.A. Makhnev have proved that the graph Kre(3) does not exist. In this paper, it is proved that the graph Kre(4) (a strongly regular graph with parameters (784, 116, 0, 20)) does not exist either.     

Certain bivariate distributions and random processes connected with maxima and minima

The minimum and the maximum of t independent, identically distributed random variables have \(\bar F^{t}\) and F ^t for their survival (minimum) and the distribution (maximum) functions, where \(\bar F = 1-F\) and F are their common survival and distribution functions, respectively. We provide stochastic interpretation for these survival and distribution functions for the case when t >?0 is no longer an integer. A new bivariate model with these margins involve maxima and minima with a random number of terms. Our construction leads to a bivariate max-min process with t as its time argument. The second coordinate of the process resembles the well-known extremal process and shares with it the one-dimensional distribution given by F ^t . However, it is shown that the two processes are different. Some fundamental properties of the max-min process are presented, including a distributional Markovian characterization of its jumps and their locations.     

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

A note on Hamiltonicity of uniform random intersection graphs

We consider a collection of n independent random subsets of [m] = {1, 2, . . . , m} that are uniformly distributed in the class of subsets of size d, and call any two subsets adjacent whenever they intersect. This adjacency relation defines a graph called the uniform random intersection graph and denoted by G _n,m,d . We fix d = 2, 3, . . . and study when, as n,m → ∞, the graph G _n,m,d contains a Hamilton cycle (the event denoted \( {G_{n,m,d}} \in \mathcal{H} \)). We show that \( {\mathbf{P}}\left( {{G_{n,m,d}} \in \mathcal{H}} \right) = o(1) \) for d ² nm ^?1 ? lnm ? 2 ln lnm → ?∞ and \( {\mathbf{P}}\left( {{G_{n,m,d}} \in \mathcal{H}} \right) = 1 - o(1) \) for 2nm ^?1 ? lnm ? ln lnm → +∞.     

On the sectionwise connectedness of a contingent

Let X be a real normed space and let f: ? → X be a continuous mapping. Let T _f (t ₀) be the contingent of the graph G(f) at a point (t ₀, f(t ₀)) and let S ⁺ ? (0,∞) × X be the “right” unit hemisphere centered at (0, 0 _X ). We show that

1. 1.
   If dimX < ∞ and the dilation D(f, t ₀) of f at t ₀ is finite then T _f (t ₀) ∩ S ⁺ is compact and connected. The result holds for \(T_f (t_0 ) \cap \overline {S^ + } \) even with infinite dilation in the case f: [0,∞) → X.
    
2. 2.
   If dimX = ∞, then, given any compact set F ? S ⁺, there exists a Lipschitz mapping f: ? → X such that T _f (t ₀) ∩ S ⁺ = F.
    
3. 3.
   But if a closed set F ? S ⁺ has cardinality greater than that of the continuum then the relation T _f (t ₀) ∩ S ⁺ = F does not hold for any Lipschitz f: ? → X.
    

     

Perturbations of strongly continuous operator semigroups,and matrix Muckenhoupt weights

Let A and A ₀ be linear continuously invertible operators on a Hilbert space ? such that A ^?1 ? A ₀ ^?1 has finite rank. Assuming that σ(A ₀) = ? and that the operator semigroup V ₊(t) = exp{iA ₀ t}, t ≥ 0, is of class C ₀, we state criteria under which the semigroups U _±(t) = exp{±iAt}, t ≥ 0, are of class C ₀ as well. The analysis in the paper is based on functional models for nonself-adjoint operators and techniques of matrix Muckenhoupt weights.