On the set of limit points of the partial sums of series rearranged by a given divergent permutation

We give a new characterization of divergent permutations. We prove that for any divergent permutation p, any closed interval I of (the 2-point compactification of ) and any real number sI, there exists a series ∑a_n of real terms convergent to s such that I=σa_p(n) (where σa_p(n) denotes the set of limit points of the partial sums of the series ∑a_p(n)). We determine permutations p of for which there exists a conditionally convergent series ∑a_n such that ∑a_p(n)=+∞. If the permutation p of possesses the last property then we prove that for any and there exists a series ∑a_n convergent to α and such that σa_p(n)=[β,+∞]. We show that for any countable family P of divergent permutations there exist conditionally convergent series ∑a_n and ∑b_n such that any series of the form ∑a_p(n) with pP is convergent to the sum of ∑a_n, while for every pP.     

Partial regularity for solutions of a nonlinear elliptic equation with singular nonlinearity

We consider the following nonlinear elliptic equation with singular nonlinearity:

where α>β>1, a>0, and Ω is an open subset of , n2. Let uH¹(Ω) with and be a nonnegative stationary solution. If we denote the zero set of u by

we shall prove that the Hausdorff dimension of Σ is less than or equal to .     

On periodicity and low complexity of infinite permutations

We define an infinite permutation as a sequence of reals taken up to value, or, equivalently, as a linear ordering of or of . We introduce and characterize periodic permutations; surprisingly, for each period t there is an infinite number of distinct t-periodic permutations. At last, we study a complexity notion for permutations analogous to subword complexity for words, and consider the problem of minimal complexity of non-periodic permutations. Its answer is not analogous to that for words and is different for the right infinite and the bi-infinite case.     

Erdős–Ko–Rado theorems for permutations and set partitions

Let Sym([n]) denote the collection of all permutations of [n]={1,…,n}. Suppose is a family of permutations such that any two of its elements (when written in its cycle decomposition) have at least t cycles in common. We prove that for sufficiently large n, with equality if and only if is the stabilizer of t fixed points. Similarly, let denote the collection of all set partitions of [n] and suppose is a family of set partitions such that any two of its elements have at least t blocks in common. It is proved that, for sufficiently large n, with equality if and only if consists of all set partitions with t fixed singletons, where B_n is the nth Bell number.     

Patterns of simple gene assembly in ciliates

The intramolecular model for gene assembly in ciliates considers three operations, , , and that can assemble any gene pattern through folding and recombination: the molecule is folded so that two occurrences of a pointer (short nucleotide sequence) get aligned and then the sequence is rearranged through recombination of pointers. In general, the sequence rearranged by one operation can be arbitrarily long and consist of many coding and noncoding blocks. We consider in this paper simple variants of the three operations, where only one coding block is rearranged at a time. We characterize in this paper the gene patterns that can be assembled through these variants. Our characterization is in terms of signed permutations and dependency graphs. Interestingly, we show that simple assemblies possess rather involved properties: a gene pattern may have both successful and unsuccessful assemblies and also more than one successful assembling strategy.     

The maximal-inversion statistic and pattern-avoiding permutations

We define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number M(n,k) of permutations in S_n with k maximal-inversions is the signless Stirling number c(n,n−k) of the first kind. A permutation π in S_n is uniquely determined by its maximal-inversion set . We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns.     

Norms of some operators on the Bergman and the Hardy space in the unit polydisk and the unit ball

Let H(X) be the class of all holomorphic functions on the set and uH(X). We calculate operator norms of the multiplication operators M_u(f)=uf, on the weighted Bergman space , as well as on the Hardy space H^p(X), where X is the unit polydisk or the unit ball in . We also calculate the norm of the weighted composition operator from the weighted Bergman space , and the Hardy space , to a weighted-type space on the unit polydisk.     

Labeled partitions with colored permutations

In this paper, we extend the notion of labeled partitions with ordinary permutations to colored permutations. We use this structure to derive the generating function of the indices of colored permutations. We further give a combinatorial treatment of a relation on the q-derangement numbers with respect to colored permutations. Based on labeled partitions, we provide an involution that implies the generating function formula due to Gessel and Simon for signed q-counting of the major indices. This involution can be extended to signed permutations. This gives a combinatorial interpretation of a formula of Adin, Gessel and Roichman.     

Local lagrange interpolation with cubic splines on tetrahedral partitions

We describe an algorithm for constructing a Lagrange interpolation pair based on C¹ cubic splines defined on tetrahedral partitions. In particular, given a set of points , we construct a set P containing and a spline space based on a tetrahedral partition whose set of vertices include such that interpolation at the points of P is well-defined and unique. Earlier results are extended in two ways: (1) here we allow arbitrary sets , and (2) the method provides optimal approximation order of smooth functions.     

A note on the total number of cycles of even and odd permutations

We prove bijectively that the total number of cycles of all even permutations of [n]={1,2,…,n} and the total number of cycles of all odd permutations of [n] differ by (−1)ⁿ(n−2)!, which was stated as an open problem by Miklós Bóna. We also prove bijectively the following more general identity:

     

Finitely additive representation of spaces

Let be any atomless and countably additive probability measure on the product space with the usual σ-algebra. Then there is a purely finitely additive probability measure λ on the power set of a countable subset such that can be isometrically isomorphically embedded as a closed subspace of L^p(λ). The embedding is strict. It is also ‘canonical,’ in the sense that it maps simple and continuous functions on to their restrictions to T.     

Widths and shape-preserving widths of Sobolev-type classes of s-monotone functions

Let I be a finite interval, , and 1p∞. Given a set M, of functions defined on I, denote by the subset of all functions yM such that the s-difference is nonnegative on I, τ>0. Further, denote by the Sobolev class of functions x on I with the seminorm x^(r)_Lp1. We obtain the exact orders of the Kolmogorov and the linear widths, and of the shape-preserving widths of the classes in L_q for s>r+1 and (r,p,q)≠(1,1,∞). We show that while the widths of the classes depend in an essential way on the parameter s, which characterizes the shape of functions, the shape-preserving widths of these classes remain asymptotically ≈n^-2.     

The maximal range problem for a bounded domain

Let be a bounded domain such that 0Ω. Denote by , the set of all complex polynomials of degree at most n. Let

where . We relate the maximal polynomial range

to the geometry of Ω.     

Polynomial-time approximation schemes for piercing and covering with applications in wireless networks

Let be a set of disks of arbitrary radii in the plane, and let be a set of points. We study the following three problems: (i) Assuming contains the set of center points of disks in , find a minimum-cardinality subset of (if exists), such that each disk in is pierced by at least h points of , where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming is such that for each there exists a point in whose distance from D's center is at most αr(D), where r(D) is D's radius and 0α<1 is a given constant, find a minimum-cardinality subset of , such that each disk in is pierced by at least one point of . We call this problem minimum discrete piercing with cores. (iii) Assuming is the set of center points of disks in , and that each covers at most l points of , where l is a constant, find a minimum-cardinality subset of , such that each point of is covered by at least one disk of . We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+ε)-approximation for minimum discrete piercing (i.e., for arbitrary ).     

Reconstruction of permutations distorted by reversal errors

The problem of reconstructing permutations on n elements from their erroneous patterns which are distorted by reversal errors is considered in this paper. Reversals are the operations reversing the order of a substring of a permutation. To solve this problem, it is essential to investigate structural and combinatorial properties of a corresponding Cayley graph on the symmetric group Sym_n generated by reversals. It is shown that for any n?3 an arbitrary permutation π is uniquely reconstructible from four distinct permutations at reversal distance at most one from π where the reversal distance is defined as the least number of reversals needed to transform one permutation into the other. It is also proved that an arbitrary permutation is reconstructible from three permutations with a probability p₃→1 and from two permutations with a probability as n→∞. A reconstruction algorithm is presented. In the case of at most two reversal errors it is shown that at least erroneous patterns are required in order to reconstruct an arbitrary permutation.     

On the sampling and recovery of bandlimited functions via scattered translates of the Gaussian

Let λ be a positive number, and let be a fixed Riesz-basis sequence, namely, (x_j) is strictly increasing, and the set of functions is a Riesz basis (i.e., unconditional basis) for L₂[−π,π]. Given a function whose Fourier transform is zero almost everywhere outside the interval [−π,π], there is a unique sequence in , depending on λ and f, such that the function

is continuous and square integrable on (−∞,∞), and satisfies the interpolatory conditions I_λ(f)(x_j)=f(x_j), . It is shown that I_λ(f)converges to f in , and also uniformly on , as λ→0⁺. In addition, the fundamental functions for the univariate interpolation process are defined, and some of their basic properties, including their exponential decay for large argument, are established. It is further shown that the associated interpolation operators are bounded on for every p[1,∞].     

On fully operator Lipschitz functions

Let be the disc algebra of all continuous complex-valued functions on the unit disc holomorphic in its interior. Functions from act on the set of all contraction operators (A1) on Hilbert spaces. It is proved that the following classes of functions from coincide: (1) the class of operator Lipschitz functions on the unit circle ; (2) the class of operator Lipschitz functions on ; and (3) the class of operator Lipschitz functions on all contraction operators. A similar result is obtained for the class of operator C₂-Lipschitz functions from .     

Inverse eigenproblem for -symmetric matrices and their approximation

Let be a nontrivial involution, i.e., R=R⁻¹≠±I_n. We say that is R-symmetric if RGR=G. The set of all -symmetric matrices is denoted by . In this paper, we first give the solvability condition for the following inverse eigenproblem (IEP): given a set of vectors in and a set of complex numbers , find a matrix such that and are, respectively, the eigenvalues and eigenvectors of A. We then consider the following approximation problem: Given an n×n matrix , find such that , where is the solution set of IEP and is the Frobenius norm. We provide an explicit formula for the best approximation solution by means of the canonical correlation decomposition.     

On realistic terrains

We study worst-case complexities of visibility and distance structures on terrains under realistic assumptions on edge length ratios and the angles of the triangles, and a more general low-density assumption. We show that the visibility map of a point for a realistic terrain with n triangles has complexity . We also prove that the shortest path between two points p and q on a realistic terrain passes through triangles, and that the bisector of p and q has complexity . We use these results to show that the shortest path map for any point on a realistic terrain has complexity , and that the Voronoi diagram for any set of m points on a realistic terrain has complexity and . Our results immediately imply more efficient algorithms for computing the various structures on realistic terrains.     

Relative asymptotic of multiple orthogonal polynomials for Nikishin systems

We prove the relative asymptotic behavior for the ratio of two sequences of multiple orthogonal polynomials with respect to the Nikishin systems of measures. The first Nikishin system is such that for each k, σ_k has a constant sign on its compact support consisting of an interval , on which almost everywhere, and a discrete set without accumulation points in . If denotes the smallest interval containing , we assume that Δ_k∩Δ_k+1=0/, k=1,…,m−1. The second Nikishin system is a perturbation of the first by means of rational functions r_k, k=1,…,m, whose zeros and poles lie in .