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)     

The isoperimetric constant of the random graph process

The isoperimetric constant of a graph G on n vertices, i(G), is the minimum of , taken over all nonempty subsets S ⊂ V (G) of size at most n/2, where ∂S denotes the set of edges with precisely one end in S. A random graph process on n vertices, , is a sequence of graphs, where is the edgeless graph on n vertices, and is the result of adding an edge to , uniformly distributed over all the missing edges. The authors show that in almost every graph process equals the minimal degree of as long as the minimal degree is o(log n). Furthermore, it is shown that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically Θ(log n), the ratio between the isoperimetric constant and the minimum degree falls from 1 to , its final value. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Law of large numbers for increasing subsequences of random permutations

Let the random variable Z_n,k denote the number of increasing subsequences of length k in a random permutation from S_n, the symmetric group of permutations of {1,…,n}. We show that Var(Z) = o((EZ)²) as n → ∞ if and only if . In particular then, the weak law of large numbers holds for Z if ; that is, We also show the following approximation result for the uniform measure U_n on S_n. Define the probability measure μ on S_n by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x₁,x₂,…,x}. Then the weak law of large numbers holds for Z if and only if where ∣∣˙∣∣ denotes the total variation norm. In particular then, (*) holds if . In order to evaluate the asymptotic behavior of the second moment, we need to analyze occupation times of certain conditioned two‐dimensional random walks. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Between ends and fibers

Let Γ be an infinite, locally finite, connected graph with distance function δ. Given a ray P in Γ and a constant C ≥ 1, a vertex‐sequence is said to be regulated by C if, for all n??, never precedes x_n on P, each vertex of P appears at most C times in the sequence, and . R. Halin (Math. Ann., 157, 3 , 125–137) defined two rays to be end‐equivalent if they are joined by infinitely many pairwise‐disjoint paths; the resulting equivalence classes are called ends. More recently H. A. Jung (Graph Structure Theory, Contemporary Mathematics, 147, 6 , 477–484) defined rays P and Q to be b‐equivalent if there exist sequences and VQ regulated by some constant C ≥ 1 such that for all n??; he named the resulting equivalence classes b‐fibers. Let denote the set of nondecreasing functions from into the set of positive real numbers. The relation (called f‐equivalence) generalizes Jung's condition to . As f runs through , uncountably many equivalence relations are produced on the set of rays that are no finer than b‐equivalence while, under specified conditions, are no coarser than end‐equivalence. Indeed, for every Γ there exists an “end‐defining function” that is unbounded and sublinear and such that implies that P and Q are end‐equivalent. Say if there exists a sublinear function such that . The equivalence classes with respect to are called bundles. We pursue the notion of “initially metric” rays in relation to bundles, and show that in any bundle either all or none of its rays are initially metric. Furthermore, initially metric rays in the same bundle are end‐equivalent. In the case that Γ contains translatable rays we give some sufficient conditions for every f‐equivalence class to contain uncountably many g‐equivalence classes (where ). We conclude with a variety of applications to infinite planar graphs. Among these, it is shown that two rays whose union is the boundary of an infinite face of an almost‐transitive planar map are never bundle‐ equivalent. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 125–153, 2007     

A generalization of the Oberwolfach problem

Let n > 1 be an integer and let a₂,a₃,…,a_n be nonnegative integers such that . Then can be factored into ‐factors, ‐factors,…, ‐factors, plus a 1‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 151–161, 2002     

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     

A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree

Let X_n be the number of cuts needed to isolate the root in a random recursive tree with n vertices. We provide a weak convergence result for X_n. The basic observation for its proof is that the probability distributions of are recursively defined by , where D_n is a discrete random variable with ? , which is independent of . This distributional recursion was not studied previously in the sense of weak convergence. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Two‐factors each component of which contains a specified vertex

It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v₁,v₂,…,v_k} ? V(G), there is a 2‐factor of G with precisely k cycles {C₁,C₂,…,C_k} such that v_i ∈ V(C_i) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003     

The largest connected component in a random mapping

A random mapping (T; q) of a finite set V = {1, 2,…,n} into itself assigns independently to each i ? V its unique image j = TT(i)E V with probability q for i = j and with probability $ \frac{{1 - q}}{{n - 1}} $ for j ≠ i. The purpose of the article is to determine the asymptotic behaviour of the size of the largest connected component of the random digraph G_T(q) representing thes mapping as n–x, regarding all possible values of the parameter q = q(n). © 1994 John Wiley & Sons, Inc.     

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 Range of Two Convolution Operators

Let _(ω)(ℝ) denote the non–quasianalytic class of Beurling type on ℝ. For μ, ν ∈ ′_(ω)(ℝ) we give necessary conditions for the inclusion T_ν( _(ω)(ℝ)) ⊂ T_μ( _(ω)(ℝ)), thus extending previous work of Malgrange and Ehrenpreis .     

The generalized Randić index of trees

The generalized Randi?; index of a tree T is the sum over the edges of T of where is the degree of the vertex x in T. For all , we find the minimal constant such that for all trees on at least 3 vertices, , where is the number of vertices of T. For example, when . This bound is sharp up to the additive constant—for infinitely many n we give examples of trees T on n vertices with . More generally, fix and define , where is the number of leaves of T. We determine the best constant such that for all trees on at least 3 vertices, . Using these results one can determine (up to terms) the maximal Randi?; index of a tree with a specified number of vertices and leaves. Our methods also yield bounds when the maximum degree of the tree is restricted. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 270–286, 2007     

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.     

Infinite games in the Cantor space and subsystems of second order arithmetic

In this paper we study the determinacy strength of infinite games in the Cantor space and compare them with their counterparts in the Baire space. We show the following theorems: 1. RCA₀ ? ‐Det* ? ‐Det* ? WKL₀. 2. RCA₀ ? ( )2‐Det* ? ACA₀. 3. RCA₀ ? ‐Det* ? ‐Det* ? ‐Det ? ‐Det ? ATR₀. 4. For 1 < k < ω, RCA₀ ? ( )_k ‐Det* ? ( )_{k –1}‐Det. 5. RCA₀ ? ‐Det* ? ‐Det. Here, Det* (respectively Det) stands for the determinacy of infinite games in the Cantor space (respectively the Baire space), and ( )_k is the collection of formulas built from formulas by applying the difference operator k – 1 times. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Data Based Regularization Matrices for the Tikhonov-Phillips Regularization

In Tikhonov-Phillips regularization of general form the given ill-posed linear system is replaced by a Least Squares problem including a minimization of the solution vector x, relative to a seminorm with some regularization matrix L. Based on the finite difference matrix L_k, given by a discretization of the first or second derivative, we introduce the seminorm where the diagonal matrix and is the best available approximate solution to x. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On an online random k‐SAT model

Given n Boolean variables x₁,…,x_n, a k‐clause is a disjunction of k literals, where a literal is a variable or its negation. Suppose random k‐clauses are generated one at a time and an online algorithm accepts or rejects each clause as it is generated. Our goal is to accept as many randomly generated k‐clauses as possible with the condition that it must be possible to satisfy every clause that is accepted. When cn random k‐clauses on n variables are given, a natural online algorithm known as Online‐Lazy accepts an expected (1 ? )cn + a_kn clauses for some constant a_k. If these clauses are given offline, it is possible to do much better, (1 ? )cn + Ω( )n can be accepted whp . The question of closing the gap between a_k and Ω( ) for the online version remained open. This article shows that for any k ≥ 1, any online algorithm will accept less than (1 ? )cn + (ln 2)n k‐clauses whp , closing the gap between the constant and Ω( ). Furthermore we show that this bound is asymptotically tight as k → ∞. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Total relative displacement of vertex permutations of K

Let α denote a permutation of the n vertices of a connected graph G. Define δ_α(G) to be the number , where the sum is over all the unordered pairs of distinct vertices of G. The number δ_α(G) is called the total relative displacement of α (in G). So, permutation α is an automorphism of G if and only if δ_α(G) = 0. Let π(G) denote the smallest positive value of δ_α(G) among the n! permutations α of the vertices of G. A permutation α for which π(G) = δ_α(G) has been called a near‐automorphism of G [ 2 ]. We determine π(K) and describe permutations α of K for which π(K) = δ_α(K). This is done by transforming the problem into the combinatorial optimization problem of maximizing the sums of the squares of the entries in certain t by t matrices with non–negative integer entries in which the sum of the entries in the ith row and the sum of the entries in the ith column each equal to n_i,1≤i≤t. We prove that for positive integers, n₁≤n₂≤…≤n_t, where t≥2 and n_t≥2, where k₀ is the smallest index for which n = n+1. As a special case, we correct the value of π(K_m,n), for all m and n at least 2, given by Chartrand, Gavlas, and VanderJagt [ 2 ]. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 85–100, 2002     

On asymmetric coverings and covering numbers

An asymmetric covering is a collection of special subsets S of an n‐set such that every subset T of the n‐set is contained in at least one special S with . In this paper we compute the smallest size of any for We also investigate “continuous” and “banded” versions of the problem. The latter involves the classical covering numbers , and we determine the following new values: , , , , and . We also find the number of non‐isomorphic minimal covering designs in several cases. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 218–228, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10022     

Minors in lifts of graphs

We study here lifts and random lifts of graphs, as defined by Amit and Linial (Combinatorica 22 (2002), 1–18). We consider the Hadwiger number η and the Hajós number σ of ?‐lifts of Kⁿ and analyze their extremal as well as their typical values (that is, for random lifts). When ? = 2, we show that , and random lifts achieve the lower bound (as n → ∞). For bigger values of ?, we show . We do not know how tight these bounds are, and in fact, the most interesting question that remains open is whether it is possible for η to be o(n). When ? < O(log n), almost every ?‐lift of Kⁿ satisfies η = Θ(n) and for , almost surely . For bigger values of ?, almost always. The Hajós number satisfies , and random lifts achieve the lower bound for bounded ? and approach the upper bound when ? grows. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Semilinear wave equation with time dependent potential

We consider the following semilinear wave equation: (1) for (t,x) ∈ ?_t × ?. We prove that if the potential V(t,x) is a measurable function that satisfies the following decay assumption: ∣V(t,x)∣?C(1+t)(1+∣x∣) for a.e. (t,x) ∈ ?_t × ? where C, σ₀>0 are real constants, then for any real number λ that satisfies there exists a real number ρ(f,g,λ)>0 such that the equation has a global solution provided that 0<ρ?ρ(f,g,λ). Copyright © 2004 John Wiley & Sons, Ltd.