Imbalance in Random Digital Trees

The imbalance factor of the nodes containing keys in a trie (a sort of digital trees) is investigated. Accurate asymptotics for the mean are derived for a randomly chosen key in the trie via poissonization and the Mellin transform, and the inverse of the two operations. It is also shown from an analysis of the moving poles of the Mellin transform of the poissonized moment generating function that the imbalance factor (under appropriate centering and scaling) follows a Gaussian limit law.      

Finite time singularities for a class of generalized surface quasi-geostrophic equations

We propose and study a class of generalized surface quasi-geostrophic equations. We show that in the inviscid case certain radial solutions develop gradient blow-up in finite time. In the critical dissipative case, the equations are globally well-posed with arbitrary initial data.

     

On a restricted cross-intersection problem

Suppose A and B are families of subsets of an n-element set and L is a set of s numbers. We say that the pair (A,B) is L-cross-intersecting if |A∩B|∈L for every A∈A and B∈B. Among such pairs (A,B) we write PL(n) for the maximum possible value of |A||B|. In this paper we find an exact bound for PL(n) when n is sufficiently large, improving earlier work of Sgall. We also determine P{2}(n) and P{1,2}(n) exactly, which respectively confirm special cases of a conjecture of Ahlswede, Cai and Zhang and a conjecture of Sgall.     

Random walks on graphs with a strong isoperimetric property

A random walk on a graph is a Markov chain whose state space consists of the vertices of the graph and where transitions are only allowed along the edges. We study (strongly) reversible random walks and characterize the class of graphs where then-step transition probabilities tend to zero exponentially fast (geometric ergodicity). These characterizations deal with an isoperimetric property, norm inequalities for certain associated operators, and eigenvalues of the Laplace operator. There is some (strong) similarity with the theory of (non)amenable groups.     

Analysis of orthogonal multi-matching pursuit under restricted isometry property

Orthogonal multi-matching pursuit(OMMP)is a natural extension of orthogonal matching pursuit(OMP)in the sense that N(N≥1)indices are selected per iteration instead of 1.In this paper,the theoretical performance of OMMP under the restricted isometry property(RIP)is presented.We demonstrate that OMMP can exactly recover any K-sparse signal from fewer observations y=φx,provided that the sampling matrixφsatisfiesδKN-N+1+(K/N)~(1/2)θKN-N+1,N1.Moreover,the performance of OMMP for support recovery from noisy observations is also discussed.It is shown that,for l_2 bounded and l_∞bounded noisy cases,OMMP can recover the true support of any K-sparse signal under conditions on the restricted isometry property of the sampling matrixφand the minimum magnitude of the nonzero components of the signal.     

Robustness of orthogonal matching pursuit under restricted isometry property

Orthogonal matching pursuit(OMP)algorithm is an efcient method for the recovery of a sparse signal in compressed sensing,due to its ease implementation and low complexity.In this paper,the robustness of the OMP algorithm under the restricted isometry property(RIP) is presented.It is shown that δK+√KθK,11is sufcient for the OMP algorithm to recover exactly the support of arbitrary K-sparse signal if its nonzero components are large enough for both l2bounded and l∞bounded noises.     

Dunkl transforms and Dunkl convolutions on functions and distributions with restricted growth

In this paper we investigate Dunkl transforms and Dunkl convolutions on R in some spaces of functions and distributions with exponential growth introduced by Hasumi [12] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the restricted connectivity and superconnectivity in graphs with given girth

The restricted connectivity κ^′(G) of a connected graph G is defined as the minimum cardinality of a vertex-cut over all vertex-cuts X such that no vertex u has all its neighbors in X; the superconnectivity κ₁(G) is defined similarly, this time considering only vertices u in G-X, hence κ₁(G)?κ^′(G). The minimum edge-degree of G is ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, d(u) standing for the degree of a vertex u. In this paper, several sufficient conditions yielding κ₁(G)?ξ(G) are given, improving a previous related result by Fiol et al. [Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17-31] and guaranteeing κ₁(G)=κ^′(G)=ξ(G) under some additional constraints.     

On the edge-connectivity and restricted edge-connectivity of a product of graphs

The product graph G_m*G_p of two given graphs G_m and G_p was defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32-48]. For this kind of graphs we provide bounds for two connectivity parameters (λ and λ^′, edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs G_m, G_p of minimum degrees δ(G_m), δ(G_p), respectively, we show that λ(G_m*G_p) is lower bounded by both δ(G_m)+λ(G_p) and δ(G_p)+λ(G_m), an improvement of what is known for the edge-connectivity of G_m×G_p.     

The pricing of vulnerable options with double Mellin transforms

Many options traded in the over-the-counter markets are subject to default risks resulting from the probability that the option writer could not honor its contractual obligations. There have been growing concerns about financial derivatives subject to default risks, in particular, since the Global Financial Crisis and Eurozone crisis. This paper uses double Mellin transforms to study European vulnerable options under constant as well as stochastic (the Hull–White) interest rates. We obtain explicitly an analytic closed form pricing formula in each interest rate case so that the pricing of the options can be computed both accurately and efficiently.     

On the equivalence of the BLUEs under a general linear model and its restricted and stochastically restricted models

Necessary and sufficient conditions are derived for the equalities of the best linear unbiased estimators (BLUEs) of parametric functions under a general linear model and its restricted and stochastically restricted models to hold.     

Limit laws in the generalized random graphs with random vertex weights

In this note we investigate the number of edges and the vertex degree in the generalized random graphs with vertex weights, which are independent and identically distributed random variables.     

Toughness,binding number and restricted matching extension in a graph

A connected graph $G$ with at least $2m+2n+2$ vertices is said to satisfy the property $E(m,n)$ if $G$ contains a perfect matching and for any two sets of independent edges $M$ and $N$ with $\left|M\right|=m$ and $\left|N\right|=n$ with $M\cap N=?$, there is a perfect matching $F$ in $G$ such that $M?F$ and $N\cap F=?$. In particular, if $G$ is $E(m,0)$, we say that $G$ is $m$-extendable. One of the authors has proved that every $m$-tough graph of even order at least $2m+2$ is $m$-extendable (Plummer, 1988). Chen (1995) and Robertshaw and Woodall (2002) gave sufficient conditions on binding number for $m$-extendability. In this paper, we extend these results and give lower bounds on toughness and binding number which guarantee $E(m,n)$.     

The degree of a typical vertex in generalized random intersection graph models

In this paper we consider the degree of a typical vertex in two models of random intersection graphs introduced in [E. Godehardt, J. Jaworski, Two models of random intersection graphs for classification, in: M. Schwaiger, O. Opitz (Eds.), Exploratory Data Analysis in Empirical Research, Proceedings of the 25th Annual Conference of the Gesellschaft für Klassifikation e.V., University of Munich, March 14-16, 2001, Springer, Berlin, Heidelberg, New York, 2002, pp. 67-81], the active and passive models. The active models are those for which vertices are assigned a random subset of a list of objects and two vertices are made adjacent when their subsets intersect. We prove sufficient conditions for vertex degree to be asymptotically Poisson as well as closely related necessary conditions. We also consider the passive model of intersection graphs, in which objects are vertices and two objects are made adjacent if there is at least one vertex in the corresponding active model “containing” both objects. We prove a necessary condition for vertex degree to be asymptotically Poisson for passive intersection graphs.     

Uniform boundary Harnack principle and generalized triangle property

Let D be a bounded open subset in R^d, d?2, and let G denote the Green function for D with respect to (-Δ)^α/2, 0<α?2, α<d. If α<2, assume that D satisfies the interior corkscrew condition; if α=2, i.e., if G is the classical Green function on D, assume—more restrictively—that D is a uniform domain. Let g=G(·,y₀)∧1 for some y₀∈D. Based on the uniform boundary Harnack principle, it is shown that G has the generalized triangle property which states that when d(z,x)?d(z,y). An intermediate step is the approximation G(x,y)≈|x-y|^α-dg(x)g(y)/g(A)², where A is an arbitrary point in a certain set B(x,y).This is discussed in a general setting where D is a dense open subset of a compact metric space satisfying the interior corkscrew condition and G is a quasi-symmetric positive numerical function on D×D which has locally polynomial decay and satisfies Harnack's inequality. Under these assumptions, the uniform boundary Harnack principle, the approximation for G, and the generalized triangle property turn out to be equivalent.     

Index transforms with the squares of Bessel functions

New index transforms, involving the squares of Bessel functions of the first kind as the kernel, are considered. Mapping properties such as the boundedness and invertibility are investigated for these operators in the Lebesgue spaces. Inversion theorems are proved. As an interesting application, a solution to the initial value problem for the third-order partial differential equation, involving the Laplacian, is obtained.