On (ε,k)‐min‐wise independent permutations

A family of permutations of [n] = {1,2,…,n} is (ε,k)‐min‐wise independent if for every nonempty subset X of at most k elements of [n], and for any x ∈ X, the probability that in a random element π of , π(x) is the minimum element of π(X), deviates from 1/∣X∣ by at most ε/∣X∣. This notion can be defined for the uniform case, when the elements of are picked according to a uniform distribution, or for the more general, biased case, in which the elements of are chosen according to a given distribution D. It is known that this notion is a useful tool for indexing replicated documents on the web. We show that even in the more general, biased case, for all admissible k and ε and all large n, the size of must satisfy as well as This improves the best known previous estimates even for the uniform case. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On the Harnack principle for strongly elliptic systems with nonsmooth coefficients

In this paper we prove the following theorem (for notation and definitions, see the paragraphs below): “Let Ω ⊆ ℝⁿ be a domain, m ∈ ℕ, and λ, q > 0. Then, there exists r (= r(λ, q)) > 1 such that for every 0 < p < q, whenever are weak solutions of a strongly elliptic system with m equations of ellipticity λ satisfying ∈ 𝒫_r a.e. and Ω′ ⊆ Ω subdomain, the following inequalities hold: where C (= C(n,m,λ,q,p,Ω,Ω′)) is a positive constant.” © 1999 John Wiley & Sons, Inc.     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Globally sparse vertex-ramsey graphs

For graphs G and F we write F → (G)¹_r if every r-coloring of the vertices of F results in a monochromatic copy of G. The global density m(F) of F is the maximum ratio of the number of edges to the number of vertices taken over all subgraphs of F. Let We show that The lower bound is achieved by complete graphs, whereas, for all r ≥ 2 and ? > 0, m_cr(S_k, r) > r - ? for sufficiently large k, where S_k is the star with k arms. In particular, we prove that      

Necessary and Sufficient Conditions for the Oscillation of a Second Order Linear Differential Equation

In this paper we give a necessary and sufficient condition for the oscillation of the second order linear differential equation where p is a locally integrable function and either or where We give some applications which show how these results unify and imply some classical results in oscillation theory.     

Analytic aspects of the Toda system: I. A Moser‐Trudinger inequality

In this paper, we analyze solutions of the open Toda system and establish an optimal Moser‐Trudinger type inequality for this system. Let Σ be a closed surface with area 1 and K = (a_ij)_{N × N} the Cartan matrix for SU(N + 1), i.e., We show that has a lower bound in (H¹(Σ))^N if and only if This inequality is optimal. As a direct consequence, if M_j < for 4π for j = 1, 2, …, N, Φ_M has a minimizer u that satisfies © 2001 John Wiley & Sons, Inc.     

Nontrivial periodic solutions of a nonlinear beam equation

We consider the existence of a nontrivial solution of the following equation: where g is a nondecreasing function defined on R¹, satisfies g(O) = O, and some other additional conditions. Our results and methods are quite similar to those associated with recent work on the nonlinear wave equation [1]-[8]: .     

Tauberian theorem for m‐spherical transforms on the Heisenberg group

In this paper we prove a Tauberian type theorem for the space L ( H _n ). This theorem gives sufficient conditions for a L ( H _n ) submodule J ? L ( H _n ) to make up all of L ( H _n ). As a consequence of this theorem, we are able to improve previous results on the Pompeiu problem with moments on the Heisenberg group for the space L^∞( H _n ). In connection with the Pompeiu problem, given the vanishing of integrals ∫ z ^m L _g f ( z , 0) dσ ( z ) = 0 for all g ∈ H _n and i = 1, 2 for appropriate radii r₁ and r₂, we now have the (improved) conclusion f ≡ 0, where = · · · and form the standard basis for T^(0,1)( H _n ). (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A topological degree counting for some Liouville systems of mean field type

Let A = (a_ij)_{n × n} be an invertible matrix and A⁻¹ = (a^ij)_{n × n} be the inverse of A. In this paper, we consider the generalized Liouville system (0.1) where 0 < h_j ∈ C¹(M) and \input amssym $\rho_j \in \Bbb R^+$ , and prove that, under the assumptions of (H₁) and (H₂) (see Introduction), the Leray‐Schauder degree of (0.1) is equal to if ρ = (ρ₁, …, ρ_n) satisfies Equation (0.1) is a natural generalization of the classic Liouville equation and is the Euler‐Lagrangian equation of the nonlinear function Φ_ρ: The Liouville system (0.1) has arisen in many different research areas in mathematics and physics. Our counting formulas are the first result in degree theory for Liouville systems. © 2010 Wiley Periodicals, Inc.     

Strengths and Weaknesses of LH Arithmetic

In this paper we provide a new arithmetic characterization of the levels of the og‐time hierarchy (LH). We define arithmetic classes and that correspond to ‐LOGTIME and ‐LOGTIME, respectively. We break and into natural hierarchies of subclasses and . We then define bounded arithmetic deduction systems ′ whose ‐definable functions are precisely B( ‐LOGTIME). We show these theories are quite strong in that (1) LIOpen proves for any fixed m that , (2) TAC, a theory that is slightly stronger than ′ whose (LH)‐definable functions are LH, proves LH is not equal to ‐TIME(s) for any m> 0, where 2^s ∈L, s(n) ∈ ω(log n), and (3) TAC proves LH ≠ for all k and m. We then show that the theory TAC cannot prove the collapse of the polynomial hierarchy. Thus any such proof, if it exists, must be argued in a stronger systems than ours.     

Nonlinear Eigenvalue Problem for p-Laplacian in IRN

The nonlinear eigenvalue problem for p-Laplacian is considered. We assume that 1 < p < N and that the function f is of subcritical growth with respect to the variable u. The existence and C^1,α-regularity of the weak solution is proved.     

Nodes of large degree in random trees and forests

We study the asymptotic behavior of the number N_k,n of nodes of given degree k in unlabeled random trees, when the tree size n and the node degree k both tend to infinity. It is shown that N_k,n is asymptotically normal if and asymptotically Poisson distributed if . If , then the distribution degenerates. The same holds for rooted, unlabeled trees and forests. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Distortion Properties of Holomorphic Functions of Several Complex Variables

Let Q(D) be a class of functions q, q(0) = 0, |q(z)| < 1 holomorphic in the Reinhardt domain D ? C ⁿ, a and b — arbitrary fixed numbers satisfying the condition — 1 ≤ b < a ≤ 1. ??(a, b; D) — the class of functions p such that p ? ??(a, b; D) iff for some q ? Q(D) and every z ? D. S*(a, b; D) — the class of functions f such that f ? S*(a, g; D) iff S^c(a, b; D) — the class of functions q such that q ? S^c(a, b; D) iff , where p ε ??(a, b; D) and K is an operator of the form for z=z₁,z₂,…z_n. The author obtains sharp bounds on |p(z)|, f(z)| g(z)| as well as sharp coefficient inequalities for functions in ??(a, b; D), S*(a, b; D) and S^c(a, b; D).     

Ryser's embedding problem for Hadamard matrices

What is the minimum order of a Hadamard matrix that contains an a by b submatrix of all 1's? Newman showed that where c^? denotes the smallest order greater than or equal to c for which a Hadamard matrix exists. It follows that if 4 divides both a and b, and if the Hadamard conjecture is true, then . We establish the improved bounds for min {a,b} ≥ 2. The Hadamard conjecture therefore implies that if 4 divides both 2ab and ?a/2? ?b/2?, then (a, b) = 2 · max {?a/2?b, ?b/2?a}. Our lower bound comes from a counting argument, while our upper bound follows from a sub‐multiplicative property of : Improvements in our upper bound occur when suitable conference matrices or Bush‐type Hadamard matrices exist. We conjecture that any (1,?1)‐matrix of size a by b occurs as a submatrix of some Hadamard matrix of order at most . © 2005 Wiley Periodicals, Inc. J Combin Designs     

The phase transition in random graphs: A simple proof

The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around \begin{align*}p=\frac{1}{n}\end{align*} – for any ε > 0 and \begin{align*}p=\frac{1-\epsilon}{n}\end{align*}, all connected components of G(n,p) are typically of size O_ε(log n), while for \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Inversion of the Radon transform with incomplete data

The Radon transform R(p, θ), θ∈S^n?1, p∈?¹, of a compactly supported function f(x) with support in a ball B_a of radius a centred at the origin is given for all $ \theta \in \mathop {S^{n - 1} }\limits^\tilde $, where $ \mathop {S^{n - 1} }\limits^\tilde $ is an open set on S^n?1, and all p∈(? ∞, ∞), n≥2. An approximate formula is given to calculate f(x) from the given data.     

Local solvability of a nonstationary leakage problem for an ideal incompressible fluid, 3

In this paper we prove the existence and uniqueness of solutions of the leakage problem for the Euler equations in bounded domain Ω C R³ with corners π/n, n = 2, 3… We consider the case where the tangent components of the vorticity vector are given on the part S₁ of the boundary where the fluid enters the domain. We prove the existence of an unique solution in the Sobolev space W_p^l(Ω), for arbitrary natural l and p > 1. The proof is divided on three parts: (1) the existence of solutions of the elliptic problem in the domain with corners where v – velocity vector, ω – vorticity vector and n is an unit outward vector normal to the boundary, (2) the existence of solutions of the following evolution problem for given velocity vector (3) the method of successive approximations, using solvability of problems (1) and (2).     

A Γ‐convergence result for the two‐gradient theory of phase transitions

The generalization to gradient vector fields of the classical double‐well, singularly perturbed functionals, where W(ξ) = 0 if and only if ξ = A or ξ = B, and A ? B is a rank‐1 matrix, is considered. Under suitable constitutive and growth hypotheses on W, it is shown that I_ε Γ‐converge to where K^* is the (constant) interfacial energy per unit area. © 2002 Wiley Periodicals, Inc.     

A randomized on–line algorithm for the k–server problem on a line

The k–server problem is one of the most important and well‐studied problems in the area of on–line computation. Its importance stems from the fact that it models many practical problems like multi‐level memory paging encountered in operating systems, weighted caching used in the management of web caches, head motion planning of multi‐headed disks, and robot motion planning. In this paper, we investigate its randomized version for which Θ(log k)–competitiveness is conjectured and yet hardly any <k competitive algorithms are known, even for the simplest of metric spaces of O(k) size. We present a –competitive randomized k–server algorithm against an oblivious adversary when the underlying metric space is given by n equally spaced points on a line . This algorithm is <k competitive for . Thus, it provides a super–linear bound for n with o(k)–competitiveness for the first time and improves the best results known so far for the range on . © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006