1‐Factorizations of pseudorandom graphs

A 1‐factorization of a graph G is a collection of edge‐disjoint perfect matchings whose union is E(G). In this paper, we prove that for any ?>0, an (n,d,λ)‐graph G admits a 1‐factorization provided that n is even, C₀ ≤ d ≤ n?1 (where C₀=C₀(?) is a constant depending only on ?), and λ ≤ d^1??. In particular, since (as is well known) a typical random d‐regular graph G_n,d is such a graph, we obtain the existence of a 1‐factorization in a typical G_n,d for all C₀ ≤ d ≤ n?1, thereby extending to all possible values of d results obtained by Janson, and independently by Molloy, Robalewska, Robinson, and Wormald for fixed d. Moreover, we also obtain a lower bound for the number of distinct 1‐factorizations of such graphs G, which is better by a factor of 2^nd/2 than the previously best known lower bounds, even in the simplest case where G is the complete graph.     

A query efficient non‐adaptive long code test with perfect completeness

Long Code testing is a fundamental problem in the area of property testing and hardness of approximation. In this paper, we study how small the soundness s of the Long Code test with perfect completeness can be by using non‐adaptive q queries. We show that s = (2q + 3)/2^q is possible, where q is of the form for any integer k > 2. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 386–406, 2015     

On the existence of solutions to the Navier–Stokes equations of a two‐dimensional compressible flow

We consider the Navier–Stokes equations for compressible, barotropic flow in two space dimensions. We introduce useful tools from the theory of Orlicz spaces. Then we prove the existence of globally defined finite energy weak solutions for the pressure satisfying p(?) = a?log^d(?) for large ?. Here d>1 and a > 0. Copyright © 2003 John Wiley & Sons, Ltd.     

An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

We prove lower bounds of the form exp(n^{ε d}), ε_d > 0, on the length of proofs of an explicit sequence of tautologies, based on the Pigeonhole Principle, in proof systems using formulas of depth d, for any constant d. This is the largest lower bound for the strongest proof system, for which any superpolynomial lower bounds are known.     

A Note on the Embedding of Subspaces of Lp into ℓNr, 0 < r < 1, r ≦ p < 2

In this paper we extend a result by Bourgain-Lindenstrauss-Milman (see [1]). We prove: Let 0 < ? < 1/2, 0< r < 1, r< p < 2. There exists a constant C = C(r,p,?) such that if X is any n-dimensional subspace of L_p(0, l), then there exists Y ? ?^N_r with d(X, Y) ≦ 1 + ?, whenever N > Cn. As an application, we obtain the following partial result: Let 0 < r < 1. There exist constants C = C(r) and C' = C' (r) such that if X is any n-dimensional subspace of L_r(0,1), then there exists Y ? ^N_r with d(X, Y) ≦ C (logn)^l/^r, whenever N ≧ C'n.     

The chromatic number of random Borsuk graphs

We study a model of random graph where vertices are n i.i.d. uniform random points on the unit sphere S^d in , and a pair of vertices is connected if the Euclidean distance between them is at least 2??. We are interested in the chromatic number of this graph as n tends to infinity. It is not too hard to see that if ?>0 is small and fixed, then the chromatic number is d+2 with high probability. We show that this holds even if ?→0 slowly enough. We quantify the rate at which ? can tend to zero and still have the same chromatic number. The proof depends on combining topological methods (namely the Lyusternik–Schnirelman–Borsuk theorem) with geometric probability arguments. The rate we obtain is best possible, up to a constant factor—if ?→0 faster than this, we show that the graph is (d+1)‐colorable with high probability.25     

Multiple Phase Transitions in Long‐Range First‐Passage Percolation on Square Lattices

We consider a model of long‐range first‐passage percolation on the d‐dimensional square lattice ?d in which any two distinct vertices x,y ? ?^d are connected by an edge having exponentially distributed passage time with mean ‖ x – y ‖^α+o(1), where α > 0 is a fixed parameter and ‖·‖ is the l¹–norm on ?^d. We analyze the asymptotic growth rate of the set ß_t, which consists of all x ? ?^d such that the first‐passage time between the origin 0 and x is at most t as t → ∞. We show that depending on the values of α there are four growth regimes: (i) instantaneous growth for α < ^d, (ii) stretched exponential growth for α ? d,2d), (iii) superlinear growth for α ? (2d,2d + 1), and finally (iv) linear growth for α > 2d + 1 like the nearest‐neighbor first‐passage percolation model corresponding to α=∞. © 2015 Wiley Periodicals, Inc.     

A numerical method for computing radially symmetric solutions of a dissipative nonlinear modified Klein‐Gordon equation

In this article we develop a finite‐difference scheme to approximate radially symmetric solutions of a dissipative nonlinear modified Klein‐Gordon equation subject to smooth initial conditions ? and ψ in an open sphere D around the origin, with constant internal and external damping coefficients—β and γ, respectively—, and nonlinear term of the form G′(w) = w^p, with p > 1 an odd number. The functions ? and ψ are radially symmetric in D, and ?, ψ, r?, and rψ are assumed to be small at infinity. We prove that our scheme is consistent order ??(Δt²) + ??(Δr²) for G′ identically equal to zero and provide a necessary condition for it to be stable order n. Part of our study will be devoted to compare the physical effects of β and γ. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

Let ∑ = (V,E) be a finite, d‐regular bipartite graph. For any λ > 0 let π_λ be the probability measure on the independent sets of ∑ in which the set I is chosen with probability proportional to λ^|I| (π_λ is the hard‐core measure with activity λ on ∑). We study the Glauber dynamics, or single‐site update Markov chain, whose stationary distribution is π_λ. We show that when λ is large enough (as a function of d and the expansion of subsets of single‐parity of V) then the convergence to stationarity is exponentially slow in |V(∑)|. In particular, if ∑ is the d‐dimensional hypercube {0,1}^d we show that for values of λ tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The effect of a penalty term involving higher order derivatives on the distribution of phases in an elastic medium with a two‐well elastic potential

We consider the problem of minimizing 0<p<1, h∈?, σ>0, among functions u:?^d?Ω→?^d, u_∣?Ω=0, and measurable characteristic functions χ:Ω→?. Here ?⁺_h, ?^?, denote quadratic potentials defined on the space of all symmetric d×d matrices, h is the minimum energy of ?⁺_h and ε(u) denotes the symmetric gradient of the displacement field. An equilibrium state û, χ?, of I [·,·,h, σ] is termed one‐phase if χ?≡0 or χ?≡1, two‐phase otherwise. We investigate the way in which the distribution of phases is affected by the choice of the parameters h and σ. Copyright 2002 John Wiley & Sons, Ltd.     

Randomness-optimal oblivious sampling

We present the first efficient oblivious sampler that uses an optimal number of random bits, up to an arbitrary constant factor bigger than 1. Specifically, for any α>0, it uses (1+α)(m+log γ⁻¹) random bits to output d=poly(ϵ⁻¹, log γ⁻¹, m) sample points z₁,…,z_d∈{0, 1}^m such that for any function f: {0, 1}^m→[0, 1], Pr [|(1/d)∑_i=1^df(z_i)− E f|≤ϵ]≥1−γ. Our proof is based on an improved extractor construction. An extractor is a procedure which takes as input the output of a defective random source and a small number of truly random bits, and outputs a nearly random string. We present the first optimal extractor, up to constant factors, for defective random sources with constant entropy rate. We give applications to constructive leader election and reducing randomness in interactive proofs. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 345–367 (1997)     

Defective choosability of graphs with no edge‐plus‐independent‐set minor

It is proved that, if s ≥ 2, a graph that does not have K₂ + K _s = K₁ + K_{1, s} as a minor is (s, 1)*‐choosable. This completes the proof that such a graph is (s + 1 ? d,d)*‐choosable whenever 0 ≤ d ≤ s ?1 © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 51–56, 2004     

The Semilinear Wave Equation on Asymptotically Euclidean Manifolds

We consider the quadratically semilinear wave equation on (? ^d , 𝔤), d ≥ 3. The metric 𝔤 is non-trapping and approaches the Euclidean metric like ?x?^?ρ. Using Mourre estimates and the Kato theory of smoothness, we obtain, for ρ > 0, a Keel–Smith–Sogge type inequality for the linear equation. Thanks to this estimate, we prove long time existence for the nonlinear problem with small initial data for ρ ≥ 1. Long time existence means that, for all n > 0, the life time of the solution is a least δ^?n , where δ is the size of the initial data in some appropriate Sobolev space. Moreover, for d ≥ 4 and ρ > 1, we obtain global existence for small data.     

On Φ-Derivation in Banach Algebras

Using Bre?ar and ?emrl approach, we give a proof of the extended Jacobson density theorem for Φ-derivations. Further, some applications on Banach algebras will be given. Precisely, for d being a continuous Φ-derivation on a given Banach algebra ?, we show that: d(?) ? rad (?) ? [b,[a, d(a)]] ∈ rad (?) for all a, b ∈ ? and d leaves invariant all maximal ideals of codimension one?for every a ∈ ? there exists a positive integer n such that (d(a)) ⁿ is quasi-nilpotent ? [d, Φ](?) ? rad (?) and d ²(a) ∈ rad (?) for all a ∈ ?. Finally, we characterize all pairs d, δ of continuous Φ-derivations such that dδ(a) is quasi-nilpotent for all a ∈ ? and [d, δ](?), [d, Φ](?), [δ,Φ](?) are subsets of rad (?).     

A New Approach to the Creation and Propagation of Exponential Moments in the Boltzmann Equation

We study the creation and propagation of exponential moments of solutions to the spatially homogeneous d-dimensional Boltzmann equation. In particular, when the collision kernel is of the form |v ? v _*|^β b(cos (θ)) for β ∈ (0, 2] with cos (θ) = |v ? v _*|^?1(v ? v _*)·σ and σ ∈ 𝕊 ^d?1, and assuming the classical cut-off condition b(cos (θ)) integrable in 𝕊 ^d?1, we prove that there exists a > 0 such that moments with weight exp (amin {t, 1}|v|^β) are finite for t > 0, where a only depends on the collision kernel and the initial mass and energy. We propose a novel method of proof based on a single differential inequality for the exponential moment with time-dependent coefficients.     

The minimal complementation property above 0′

Let us say that any (Turing) degree d > 0 satisfies the minimal complementation property (MCP) if for every degree 0 < a < d there exists a minimal degree b < d such that a ∨ b = d (and therefore a ∧ b = 0 ). We show that every degree d ≥ 0 ′ satisfies MCP. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the domain dependence of solutions to the Navier–Stokes equations of a two‐dimensional compressible flow

We consider the Navier–Stokes equations for compressible, barotropic flow in two space dimensions, with pressure satisfying p(?)=a?log^d(?) for large ?, here d>1 and a>0. After introducing useful tools from the theory of Orlicz spaces, we prove a compactness result for the solution set of the equations with respect to the variation of the underlying bounded spatial domain. Especially, we get a general existence theorem for the system in question with no restrictions on smoothness of the bounded spatial domain. Copyright © 2009 John Wiley & Sons, Ltd.     

A probably fast,provably optimal algorithm for rectilinear Steiner trees

We use the technique of divide-and-conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well-known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all ? > 0, there exists b > 0 such that Prob[T(n) > 2^{b√n log n]>1–?, for n log n} > 1 – ?, for n sites uniformly distributed on a rectangle. The key fact in the run-time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low-degree polynomial time for any given set of sites. © 1994 John Wiley & Sons, Inc.     

Extinction of solutions for some nonlinear parabolic equations

We are dealing with the first vanishing time for solutions of the Cauchy–Neumann problem for the semilinear parabolic equation ∂ _t u − Δu + a(x)u ^q = 0, where a(x) \geqslant d₀exp( - \fracw( | x | )| x |² ) a(x) \geqslant {d_0}\exp \left( { - \frac{{\omega \left( {\left| x \right|} \right)}}{{{{\left| x \right|}^2}}}} \right) , d ₀ > 0, 1 > q > 0, and ω is a positive continuous radial function. We give a Dini-like condition on the function ω which implies that any solution of the above equation vanishes in finite time. The proof is derived from semi-classical limits of some Schr¨odinger operators.     

An extension of a theorem of G. Tallini

A Tallini set in a projective space P is a set Q of points of P such that each line not contained in Q intersects Q in at most two points. We prove that if P is a finite projective space with odd order q > 3 and dimension d > 2 and if |Q| > q^{d ? 1} + 2q^{d ? 3} + q^{d ? 4} + … + 1, then Q is essentially an orthogonal quadric. The proof of this theorem is based on a characterization of the orthogonal quadrics in every finite dimensional projective space (with possibly infinite order).