Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

When almost all sets are difference dominated

We investigate the relationship between the sizes of the sum and difference sets attached to a subset of {0,1,…,N}, chosen randomly according to a binomial model with parameter p(N), with N^?1 = o(p(N)). We show that the random subset is almost surely difference dominated, as N → ∞, for any choice of p(N) tending to zero, thus confirming a conjecture of Martin and O'Bryant. The proofs use recent strong concentration results. Furthermore, we exhibit a threshold phenomenon regarding the ratio of the size of the difference to the sumset. If p(N) = o(N^?1/2) then almost all sums and differences in the random subset are almost surely distinct and, in particular, the difference set is almost surely about twice as large as the sumset. If N^?1/2 = o(p(N)) then both the sum and difference sets almost surely have size (2N + 1) ? O(p(N)^?2), and so the ratio in question is almost surely very close to one. If p(N) = c · N^?1/2 then as c increases from zero to infinity (i.e., as the threshold is crossed), the same ratio almost surely decreases continuously from two to one according to an explicitly given function of c. We also extend our results to the comparison of the generalized difference sets attached to an arbitrary pair of binary linear forms. For certain pairs of forms f and g, we show that there in fact exists a sharp threshold at c_f,g · N^?1/2, for some computable constant c_f,g, such that one form almost surely dominates below the threshold and the other almost surely above it. The heart of our approach involves using different tools to obtain strong concentration of the sizes of the sum and difference sets about their mean values, for various ranges of the parameter p. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Multidimensional Oscillations for Non-linear Hyperbolic Mixed Problem: The Justified Non-linear Geometric Optics Method

The mixed-Neumann problem for the non-linear wave equation □u−a(u)(∣∂_tu)∣²−∣∇u∣² = f_ε(z) is studied. The function f_ε(z) = ∑_k∈Kf_k(z,ε⁻¹ϕ_k(z),ε), ε∈[0,1], K is finite, f_k(z,θ_k,ε) are 2π-periodic with respect to θ_k. The existence of solution u_ε on a domain z = (t,x,y)∈[0,T]×ℝ₊×ℝ^d, d = 1 or 2, is proved when ε is sufficiently small; T does not depend on ε. By the non-linear geometric optics method the asymptotic (with respect to ε→0) solution ũ _ε is constructed. The estimation for the rest ε²r_ε = u_ε−ũ_ε is derived and the limit r_ε, ε→0, is studied.     

Asymptotic packing and the random greedy algorithm

Let H be an r-uniform hypergraph satisfying deg(x) = D(1 + o(1)) for each vertex xϵ V(H) and deg(x, y) = o(D) for each pair of vertices x, y ϵ V(H), where D → infinity. Recently, J. Spencer [5] showed, using a branching process approach, that almost surely the random greedy algorithm finds a packing of size at least n/r(1 − o(1)) for this class of hypergraphs. In this paper, we show an alternative proof of this via “nibbles.” Further, let T_α be the number of edges that the random greedy algorithm has to consider before yielding a packing of size [n/r · (1 − α)]. We show that almost surely T_α ∼ (1/α)^r−1 · n/r(r − 1) as α → 0⁺ holds. © 1996 John Wiley & Sons, Inc.     

Equitable coloring of random graphs

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ₌(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ₌*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n^?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n^?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ₌*(G(n,p)) = O_?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Perfect matchings in random uniform hypergraphs

Let ??_k(n, p) be the random k‐uniform hypergraph on V = [n] with edge probability p. Motivated by a theorem of Erd?s and Rényi 7 regarding when a random graph G(n, p) = ??₂(n, p) has a perfect matching, the following conjecture may be raised. (See J. Schmidt and E. Shamir 16 for a weaker version.) Conjecture. Let k|n for fixed k ≥ 3, and the expected degree d(n, p) = p(). Then (Erd?s and Rényi 7 proved this for G(n, p).) Assuming d(n, p)/n^1/2 → ∞, Schmidt and Shamir 16 were able to prove that ??_k(n, p) contains a perfect matching with probability 1 ? o(1). Frieze and Janson 8 showed that a weaker condition d(n, p)/n^1/3 → ∞ was enough. In this paper, we further weaken the condition to A condition for a similar problem about a perfect triangle packing of G(n, p) is also obtained. A perfect triangle packing of a graph is a collection of vertex disjoint triangles whose union is the entire vertex set. Improving a condition p ≥ cn^?2/3+1/15 of Krivelevich 12 , it is shown that if 3|n and p ? n^?2/3+1/18, then © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 111–132, 2003     

Long time approximations for solutions of wave equations associated with the Steklov spectral homogenization problems

The interest in the use of quasimodes, or almost frequencies and almost eigenfunctions, to describe asymptotics for low‐frequency and high‐frequency vibrations in certain singularly perturbed spectral problems, which depend on a small parameter ε, has been recently highlighted in many papers. In this paper we deal with the low frequencies for a Steklov‐type eigenvalue homogenization problem: we consider harmonic functions in a bounded domain of ?², and strongly alternating boundary conditions of the Dirichlet and Steklov type on a part of the boundary. The spectral parameter appears in the boundary condition on small segments T^ε of size O(ε) periodically distributed along the boundary; ε also measures the periodicity of the structure. We consider associated second‐order evolution problems on spaces of traces that depend on ε, and we provide estimates for the time t in which standing waves, constructed from quasimodes, approach their solutions u^ε(t) as ε→0. Copyright © 2009 John Wiley & Sons, Ltd.     

Removable singularities of weak solutions to the navier-stokes equations

Consider the Navier-Stokes equations in Ω×(0,T), where Ω is a domain in R³. We show that there is an absolute constant ε₀ such that ever, y weak solution u with the property that Sup_tε(a,b)|u(t)|_L(D)≤ε0 is necessarily of class C^∞ in the space-time variables on any compact suhset of D × (a,b) , where D?? and 0 a<b<T. As an application. we prove that if the weak solution u behaves around (x_o, t_o) εΩ×(o,T) 1ike u(x, t) = o(|x - xo|^-1) as x→x ₀ uniforlnly in t in some neighbourliood of t_o, then (x_o,t_o) is actually a removable singularity of u.     

Maximal triangle-free graphs with restrictions on the degrees

We investigate the problem that at least how many edges must a maximal triangle-free graph on n vertices have if the maximal valency is ≤D. Denote this minimum value by F(n, D). For large enough n, we determine the exact value of F(n, D) if D ≥ (n ? 2)/2 and we prove that lim F(n, cn)/n = K(c) exists for all 0 < c with the possible exception of a sequence c_k → 0. The determination of K(c) is a finite problem on all intervals [γ, ∞). For D = cn^?, 1/2 < ? < 1, we give upper and lower bounds for F(n, D) differing only in a constant factor. (Clearly, D < (n - 1)^1/2 is impossible in a maximal triangle-free graph.)     

Differentiable Eigenvalues of Perturbed Quadratic Matrix Functions

Let T(λ, ε ) = λ² + λC + λεD + K be a perturbed quadratic matrix polynomial, where C, D, and K are n × n hermitian matrices. Let λ₀ be an eigenvalue of the unperturbed matrix polynomial T(λ, 0). With the falling part of the Newton diagram of det T(λ, ε), we find the number of differentiable eigenvalues. Some results are extended to the general case L(λ, ε) = λ² + λD(ε) + K, where D(ε) is an analytic hermitian matrix function. We show that if K is negative definite on Ker L(λ₀, 0), then every eigenvalue λ(ε) of L(λ, ε) near λ₀ is analytic.     

Layer potentials and regularity for the Dirichlet problem for Laplace's equation in Lipschitz domains

For D, a bounded Lipschitz domain in Rⁿ, n ? 2, the classical layer potentials for Laplace's equation are shown to be invertible operators on L²(?D) and various subspaces of L²(?D). For 1 < p ? 2 and data in L^p(?D) with first derivatives in L^p(?D) it is shown that there exists a unique harmonic function, u, that solves the Dirichlet problem for the given data and such that the nontangential maximal function of ▽u is in L^p(?D). When n = 2 the question of the invertibility of the layer potentials on every L^p(?D), 1 < p < ∞, is answered.     

Critical percolation on random regular graphs

The behavior of the random graph G(n,p) around the critical probability p_c = is well understood. When p = (1 + O(n^1/3))p_c the components are roughly of size n^2/3 and converge, when scaled by n^?2/3, to excursion lengths of a Brownian motion with parabolic drift. In particular, in this regime, they are not concentrated. When p = (1 ‐ ?(n))p_c with ?(n)n^1/3 →∞ (the subcritical regime) the largest component is concentrated around 2?^?2 log(?³n). When p = (1 + ?(n))p_c with ?(n)n^1/3 →∞ (the supercritical regime), the largest component is concentrated around 2?n and a duality principle holds: other component sizes are distributed as in the subcritical regime. Itai Benjamini asked whether the same phenomenon occurs in a random d‐regular graph. Some results in this direction were obtained by (Pittel, Ann probab 36 (2008) 1359–1389). In this work, we give a complete affirmative answer, showing that the same limiting behavior (with suitable d dependent factors in the non‐critical regimes) extends to random d‐regular graphs. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

Homogenization of the Dirichlet problem for elliptic and parabolic systems with periodic coefficients

Let O ? R ^d be a bounded domain of class C ^1,1. Let 0 < ε - 1. In L ₂(O;C ⁿ ) we consider a positive definite strongly elliptic second-order operator B _D,ε with Dirichlet boundary condition. Its coefficients are periodic and depend on x/ε. The principal part of the operator is given in factorized form, and the operator has lower order terms. We study the behavior of the generalized resolvent (B _D,ε ? ζQ ₀(·/ε))^?1 as ε → 0. Here the matrix-valued function Q ₀ is periodic, bounded, and positive definite; ζ is a complex-valued parameter. We find approximations of the generalized resolvent in the L ₂(O;C ⁿ )-operator norm and in the norm of operators acting from L ₂(O;C ⁿ ) to the Sobolev space H ¹(O;C ⁿ ) with two-parameter error estimates (depending on ε and ζ). Approximations of the generalized resolvent are applied to the homogenization of the solution of the first initial-boundary value problem for the parabolic equation Q ₀(x/ε)? _t v _ε (x, t) = ?(B _D,ε v _ε )(x, t).     

Asymptotics of the complexity of systems of integer linear forms for additive computations

The computational complexity of integer linear forms is studied. By l ₂(A) we denote the minimal number of the additions and subtractions required for computing the system of p linear forms in q variables x ₁, x ₂, …, x _q that are defined by an integer matrix A of size p × q (repeated use of the results of intermediate computation is permitted). We show that l ₂(A) ? log D(A), where D(A) is the maximum of the absolute values of the minors of A over all minors from order 1 to order min (p, q) (Theorem 1). Moreover, for each sequence of matrices A(n) of size p(n) × q(n) satisfying the condition p + q = o ((log log D(A))^1/2) as n → ∞ the bound l ₂(A) ? log D(A) + o(log D(A)) is valid (Theorem 2). Hence, for all fixed (and even weakly increasing) sizes of matrices that determine a system of integer linear forms, the upper bound on the computational complexity of this system is asymptotically equal to the lower bound.     

Disjoint bases in a polymatroid

Let f : 2^N → ⁺ be a polymatroid (an integer‐valued non‐decreasing submodular set function with f(??) = 0). We call S ? N a base if f(S) = f(N). We consider the problem of finding a maximum number of disjoint bases; we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : Σ_iεNf_A(i) ≥ kf_A(N),?A ? N} where f_A(S) = f(A ∪ S) ‐ f(A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k*. For polymatroids, we prove that m* ≥ (1 ? o(1))k*/lnf(N) and give a randomized polynomial time algorithm to find (1 ? o(1))k*/lnf(N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 ? ε)k*/lnf(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/lnf(N). Moreover it is known that unless NP ? DTIME(n^{log log n}), for any ε > 0, there is no polynomial time algorithm to obtain a (1 + ε)/lnf(N)‐approximation to m*. Our result generalizes and unifies two results in the literature. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Holomorphic Dependence of the Heins Map

Let D be a bounded convex domain and Hol _c (D,D) the set of holomorphic maps from D to C ⁿ with image relatively compact in D. Consider Hol _c (D,D) as a open set in the complex Banach space H ^∞ _n (D) of bounded holomorphic maps from D to C ⁿ . We show that the map τ: Hol _c (D,D) → D (called the Heins map for D equals to the unit disc of C) which associates to ? ∈ Hol _c (D,D) its unique fixed point τ? ∈ D is holomorphic and its differential is given by dτ_?(v) = (Id-df_τ(?))^?1 v(τ(?)) for v ∈ H ^∞ _n (D).     

The emergence of a giant component in random subgraphs of pseudo‐random graphs

Let G be a d‐regular graph G on n vertices. Suppose that the adjacency matrix of G is such that the eigenvalue λ which is second largest in absolute value satisfies λ = o(d). Let G_p with p = α/d be obtained from G by including each edge of G independently with probability p. We show that if α < 1, then whp the maximum component size of G_p is O(log n) and if α > 1, then G_p contains a unique giant component of size Ω(n), with all other components of size O(log n). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Estimating the distance to a monotone function

In standard property testing, the task is to distinguish between objects that have a property 𝒫 and those that are ε‐far from 𝒫, for some ε > 0. In this setting, it is perfectly acceptable for the tester to provide a negative answer for every input object that does not satisfy 𝒫. This implies that property testing in and of itself cannot be expected to yield any information whatsoever about the distance from the object to the property. We address this problem in this paper, restricting our attention to monotonicity testing. A function f : {1,…,n} ↦ R is at distance ε_f from being monotone if it can (and must) be modified at ε_fn places to become monotone. For any fixed δ > 0, we compute, with probability at least 2/3, an interval [(1/2 − δ)ε,ε] that encloses ε_f. The running time of our algorithm is O(ε_f⁻¹ log log ε_f^{− 1} log n), which is optimal within a factor of loglog ε_f⁻¹ and represents a substantial improvement over previous work. We give a second algorithm with an expected running time of O(ε_f⁻¹ log nlog log log n). Finally, we extend our results to multivariate functions. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Averaging of a 3D primitive equations with oscillating external forces

In this article, we consider a non-autonomous three-dimensional primitive equations of the ocean with a singularly oscillating external force g ^ε?=?g ₀(t)?+?ε^?ρ g ₁(t/ε) depending on a small parameter ε?>?0 and ρ?∈?[0,?1) together with the averaged system with the external force g ₀(t), formally corresponding to the case ε?=?0. Under suitable assumptions on the external force, we prove as in [V.V. Chepyzhov, V. Pata, and M.M.I. Vishik, Averaging of 2D Navier–Stokes equations with singularly oscillating forces, Nonlinearity, 22 (2009), pp. 351–370] the boundness of the uniform global attractor 𝒜^ε as well as the convergence of the attractors 𝒜^ε of the singular systems to the attractor 𝒜⁰ of the averaged system as ε?→?0⁺. When the external force is small enough and the viscosity is large enough, the convergence rate is controlled by Kε^(1?ρ). Let us note that the main difference between this work and that of Chepyzhov et al. (2009) is that the non-linearity involved in the three-dimensional primitive equation is stronger than the one in the two-dimensional Navier–Stokes equations considered in Chepyzhov et al. (2009), which makes the analysis of the problem studied in this article more involved.