Limits of small functors

For a small category enriched over a suitable monoidal category , the free completion of under colimits is the presheaf category . If is large, its free completion under colimits is the -category of small presheaves on , where a presheaf is small if it is a left Kan extension of some presheaf with small domain. We study the existence of limits and of monoidal closed structures on .     

Decomposing complete edge-chromatic graphs and hypergraphs. Revisited

A d-graph is a complete graph whose edges are colored by d colors, that is, partitioned into d subsets some of which might be empty. We say that a d-graph is complementary connected (CC) if the complement to each chromatic component of is connected on V. We prove that every such d-graph contains a sub-d-graph Π or , where Π has four vertices and two non-empty chromatic components each of which is a P₄, while is a three-colored triangle. This statement implies that each Π- and -free d-graph is uniquely decomposable in accordance with a tree whose leaves are the vertices of V and the interior vertices of T are labeled by the colors 1,…d. Such a tree is naturally interpreted as a positional game form (with perfect information and without moves of chance) of d players I={1,…,d} and n outcomes V={v₁,…,v_n}. Thus, we get a one-to-one correspondence between these game forms and Π- and -free d-graphs. As a corollary, we obtain a characterization of the normal forms of positional games with perfect information and, in case d=2, several characterizations of the read-once Boolean functions. These results are not new; in fact, they are 30 and, in case d=2, even 40 years old. Yet, some important proofs did not appear in English.Gyárfás and Simonyi recently proved a similar decomposition theorem for the -free d-graphs. They showed that each -free d-graph can be obtained from the d-graphs with only two non-empty chromatic components by successive substitutions. This theorem is based on results by Gallai, Lovász, Cameron and Edmonds. We obtain some new applications of these results.     

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 ).     

Inheritance of hyper-duality in imprimitive Bose–Mesner algebras

We prove the following result concerning the inheritance of hyper-duality by block and quotient Bose–Mesner algebras associated with a hyper-dual pair of imprimitive Bose–Mesner algebras. Let and denote Bose–Mesner algebras. Suppose there is a hyper-duality ψ from the subconstituent algebra of with respect to p to the subconstituent algebra of with respect to . Also suppose that is imprimitive with respect to a subset of Hadamard idempotents, so is dual imprimitive with respect to the subset of primitive idempotents, where is the formal duality associated with ψ. Let denote the block Bose–Mesner algebra of on the block containing p, and let denote the quotient Bose–Mesner algebra of with respect to . Then there is a hyper-duality from the subconstituent algebra of with respect to p to the subconstituent algebra of with respect to .     

A generalization of Fibonacci and Lucas matrices

We define the matrix of type s, whose elements are defined by the general second-order non-degenerated sequence and introduce the notion of the generalized Fibonacci matrix , whose nonzero elements are generalized Fibonacci numbers. We observe two regular cases of these matrices (s=0 and s=1). Generalized Fibonacci matrices in certain cases give the usual Fibonacci matrix and the Lucas matrix. Inverse of the matrix is derived. In partial case we get the inverse of the generalized Fibonacci matrix and later known results from [Gwang-Yeon Lee, Jin-Soo Kim, Sang-Gu Lee, Factorizations and eigenvalues of Fibonaci and symmetric Fibonaci matrices, Fibonacci Quart. 40 (2002) 203–211; P. Staˇnicaˇ, Cholesky factorizations of matrices associated with r-order recurrent sequences, Electron. J. Combin. Number Theory 5 (2) (2005) #A16] and [Z. Zhang, Y. Zhang, The Lucas matrix and some combinatorial identities, Indian J. Pure Appl. Math. (in press)]. Correlations between the matrices , and the generalized Pascal matrices are considered. In the case a=0,b=1 we get known result for Fibonacci matrices [Gwang-Yeon Lee, Jin-Soo Kim, Seong-Hoon Cho, Some combinatorial identities via Fibonacci numbers, Discrete Appl. Math. 130 (2003) 527–534]. Analogous result for Lucas matrices, originated in [Z. Zhang, Y. Zhang, The Lucas matrix and some combinatorial identities, Indian J. Pure Appl. Math. (in press)], can be derived in the partial case a=2,b=1. Some combinatorial identities involving generalized Fibonacci numbers are derived.     

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 .     

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.     

Lattices generated by orbits of subspaces under finite singular pseudo-symplectic groups I

Let be the (2ν+1+l)-dimensional vector space over the finite field . In the paper we assume that is a finite field of characteristic 2, and the singular pseudo-symplectic groups of degree 2ν+1+l over . Let be any orbit of subspaces under . Denote by the set of subspaces which are intersections of subspaces in and the intersection of the empty set of subspaces of is assumed to be . By ordering by ordinary or reverse inclusion, two lattices are obtained. This paper studies the inclusion relations between different lattices, a characterization of subspaces contained in a given lattice , and the characteristic polynomial of .     

Poincaré's theorem for the modular group of real Riemann surfaces

Let Mod_g denote the modular group of (closed and orientable) surfaces S of genus g. Each element [h]Mod_g induces a symplectic automorphism H([h]) of . Poincaré showed that is an epimorphism. A real Riemann surface is a Riemann surface S together with an anticonformal involution σ. Let (S,σ) be a real Riemann surface, be the group of orientation preserving homeomorphisms of S such that h○σ=σ○h and be the subgroup of consisting of those isotopic to the identity by an isotopy in . The group plays the role of the modular group in the theory of real Riemann surfaces. In this work we describe the image by H of . Such image depends on the topological type of the involution σ.     

On partial sums of certain meromophic -valent functions

In this paper, we study the ratio of meromorphic p-valent functions in the punctured disk U^*={z:0<|z|<1} of the form to its sequence of partial sums of the form . Also, we determine sharp lower bounds for and .     

A pseudo-Boolean consensus approach to nonlinear 0–1 optimization

It is proved that any pseudo-Boolean function f can be represented as , where z is the minimum of f and φ is a polynomial with positive coefficients in the original variables x_i and in their complements . A non-constructive proof and a constructive one are given. The latter, which is based on a generalization to pseudo-Boolean functions of the well-known Boolean-theoretical operation of consensus, provides a new algorithm for the minimization of pseudo-Boolean functions.     

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.     

Levels of multi-continued fraction expansion of multi-formal Laurent series

The multi-continued fraction expansion of a multi-formal Laurent series is a sequence pair consisting of an index sequence and a multi-polynomial sequence . We denote the set of the different indices appearing infinitely many times in by H_∞, the set of the different indices appearing in by H₊, and call |H_∞| and |H₊| the first and second levels of , respectively. In this paper, it is shown how the dimension and basis of the linear space over F(z) (F) spanned by the components of are determined by H_∞ (H₊), and how the components are linearly dependent on the mentioned basis.     

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,∞].     

Schurian vector space categories, hereditary algebras and Roiter's norm

We associate a positive real number to any vector space K-category over a field K. Generalizing a result of Nazarova and Roiter, we show that a schurian vector space K-category is representation-finite if and only if is finite and . Such vector space categories are quasilinear, i.e. its indecomposables are simple modules over their endomorphism ring. Recently, Nazarova and Roiter introduced the concept of -faithful poset in order to clarify the structure of critical posets. Their conjecture on the precise form of -faithful posets was established by Zeldich. We generalize these results and characterize -faithful quasilinear vector space K-categories in terms of a class of hereditary algebras H_ρ(D) parametrized by a skew-field D and a rational number ρ1.     

Additive maps preserving Jordan zero-products on nest algebras

Let and be nest algebras associated with the nests and on Banach Spaces. Assume that and are complemented whenever N_-=N and M_-=M. Let be a unital additive surjection. It is shown that Φ preserves Jordan zero-products in both directions, that is Φ(A)Φ(B)+Φ(B)Φ(A)=0AB+BA=0, if and only if Φ is either a ring isomorphism or a ring anti-isomorphism. Particularly, all unital additive surjective maps between Hilbert space nest algebras which preserves Jordan zero-products are characterized completely.     

The jump operator on the -enumeration degrees

The jump operator on the ω-enumeration degrees was introduced in [I.N. Soskov, The ω-enumeration degrees, J. Logic Computat. 17 (2007) 1193–1214]. In the present paper we prove a jump inversion theorem which allows us to show that the enumeration degrees are first order definable in the structure of the ω-enumeration degrees augmented by the jump operator. Further on we show that the groups of the automorphisms of and of the enumeration degrees are isomorphic.In the second part of the paper we study the jumps of the ω-enumeration degrees below . We define the ideal of the almost zero degrees and obtain a natural characterization of the class H of the ω-enumeration degrees below which are high n for some n and of the class L of the ω-enumeration degrees below which are low n for some n.     

Boundedness of generalized higher commutators of Marcinkiewicz integrals

Let (b) ＝ (b1,…,bm) be a finite family of locally integrable functions. Then,we introduce generalized higher commutator of Marcinkiwicz integral as follows:μ(b)Ω=(∫∞o|F(b)Ω,t(f)(x)|2et/t)1/2,whereF(b)Ω(f)(x)＝1/t∫|x-y|≤tΩ(x-y)/|x-y|n-1m∏j=1(bj(x)-bj(y))f(y)dy.When bj ∈(A)βj, 1≤j≤m, 0＜βj＜1,m∑j=1βj =β＜n, and Ω is homogeneous of degree zero and satisfies the cancelation condition, we prove that μ(b)Ω is bounded from Lp(Rn)to Ls(Rn), where 1 ＜ p ＜ n/β and 1/s = 1/p -β/n. Moreover, if Ω also satisfies some Lq-Dini condition, then μ(b)Ω is bounded from Lp(Rn) to (F)β,∞p(Rn) and on certain Hardy spaces. The article extends some known results.     

Zeros of Bernoulli-type functions and best approximations

The zero sets of (D+a)ⁿg(t) with in the (t,a)-plane are investigated for and .The results are used to determine entire interpolations to functions , which give representations for the best approximation and best one-sided approximation from the class of functions of exponential type η>0 to .