Perfect packings with complete graphs minus an edge

Let denote the graph obtained from K_r by deleting one edge. We show that for every integer r≥4 there exists an integer n₀=n₀(r) such that every graph G whose order n≥n₀ is divisible by r and whose minimum degree is at least contains a perfect -packing, i.e. a collection of disjoint copies of which covers all vertices of G. Here is the critical chromatic number of . The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large n.     

Enumeration of rational plane curves tangent to a smooth cubic

We compute the number of rational degree d plane curves having prescribed fixed and moving contacts to a smooth plane cubic E. We use twisted stable maps to the stack for r large, where is the rth root of along E. We prove that certain Gromov–Witten invariants of this stack are enumerative, and establish recursive formulas for these numbers.     

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.     

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

Additive maps preserving the ascent and descent of operators

Let and be the algebras of all bounded linear operators on infinite dimensional complex Banach spaces X and Y, respectively. We characterize additive maps from onto preserving different quantities such as the nullity, the defect, the ascent, and the descent of operators.     

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 .     

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.     

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.     

Ore-type and Dirac-type theorems for matroids

Let M be a connected binary matroid having no -minor. Let be a collection of cocircuits of M. We prove there is a circuit intersecting all cocircuits of if either one of two things hold:

(i) For any two disjoint cocircuits and in it holds that .

(ii) For any two disjoint cocircuits and in it holds that .

Part (ii) implies Ore's Theorem, a well-known theorem giving sufficient conditions for the existence of a hamilton cycle in a graph. As an application of part (i), it is shown that if M is a k-connected regular matroid and has cocircumference c^*2k, then there is a circuit which intersects each cocircuit of size c^*−k+2 or greater.We also extend a theorem of Dirac for graphs by showing that for any k-connected binary matroid M having no -minor, it holds that for any k cocircuits of M there is a circuit which intersects them.     

There's something about the diameter

We study diameter preserving linear bijections from onto where X, Y are compact Hausdorff spaces and V, Z are Banach spaces. For instance, we obtain that if X has at least four points, Z is linearly isometric to V and either Z is a space or Z^* is strictly convex or smooth, then there is a diameter preserving linear bijection from onto if and only if X is homeomorphic to Y. We also consider the case when X and Y are not compact but locally compact spaces.     

On the best constants in noncommutative Khintchine-type inequalities

We obtain new proofs with improved constants of the Khintchine-type inequality with matrix coefficients in two cases. The first case is the Pisier and Lust-Piquard noncommutative Khintchine inequality for p=1, where we obtain the sharp lower bound of in the complex Gaussian case and for the sequence of functions . The second case is Junge's recent Khintchine-type inequality for subspaces of the operator space RC, which he used to construct a cb-embedding of the operator Hilbert space OH into the predual of a hyperfinite factor. Also in this case, we obtain a sharp lower bound of . As a consequence, it follows that any subspace of a quotient of (RC)^* is cb-isomorphic to a subspace of the predual of the hyperfinite factor of type III₁, with cb-isomorphism constant. In particular, the operator Hilbert space OH has this property.     

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 .     

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 .     

On Jordan ideals and matrix rings

For A, a commutative ring, and results by Costa and Keller characterize certain -normalized subgroups of the symplectic group, via structures utilizing Jordan ideals and the notion of radices. The following work creates a Jordan ideal structure theorem for -graded rings, A₀A₁, and a -graded matrix algebra. The major theorem is a generalization of Costa and Keller’s previous work on matrix algebras over commutative rings.     

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 .     

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.     

Approximation of Sobolev classes by polynomials and ridge functions

Let be the usual Sobolev class of functions on the unit ball in , and be the subclass of all radial functions in . We show that for the classes and , the orders of best approximation by polynomials in coincide. We also obtain exact orders of best approximation in of the classes by ridge functions and, as an immediate consequence, we obtain the same orders in for the usual Sobolev classes .     

Density results for Gabor systems associated with periodic subsets of the real line

The well-known density theorem for one-dimensional Gabor systems of the form , where , states that a necessary and sufficient condition for the existence of such a system whose linear span is dense in , or which forms a frame for , is that the density condition is satisfied. The main goal of this paper is to study the analogous problem for Gabor systems for which the window function g vanishes outside a periodic set which is -shift invariant. We obtain measure-theoretic conditions that are necessary and sufficient for the existence of a window g such that the linear span of the corresponding Gabor system is dense in L²(S). Moreover, we show that if this density condition holds, there exists, in fact, a measurable set with the property that the Gabor system associated with the same parameters a,b and the window g=χ_E, forms a tight frame for L²(S).     

The maximum edit distance from hereditary graph properties

For a graph property , the edit distance of a graph G from , denoted , is the minimum number of edge modifications (additions or deletions) one needs to apply to G in order to turn it into a graph satisfying . What is the largest possible edit distance of a graph on n vertices from ? Denote this distance by .A graph property is hereditary if it is closed under removal of vertices. In a previous work, the authors show that for any hereditary property, a random graph essentially achieves the maximal distance from , proving: with high probability. The proof implicitly asserts the existence of such , but it does not supply a general tool for determining its value or the edit distance.In this paper, we determine the values of and for some subfamilies of hereditary properties including sparse hereditary properties, complement invariant properties, (r,s)-colorability and more. We provide methods for analyzing the maximum edit distance from the graph properties of being induced H-free for some graphs H, and use it to show that in some natural cases G(n,1/2) is not the furthest graph. Throughout the paper, the various tools let us deduce the asymptotic maximum edit distance from some well studied hereditary graph properties, such as being Perfect, Chordal, Interval, Permutation, Claw-Free, Cograph and more. We also determine the edit distance of G(n,1/2) from any hereditary property, and investigate the behavior of as a function of p.The proofs combine several tools in Extremal Graph Theory, including strengthened versions of the Szemerédi Regularity Lemma, Ramsey Theory and properties of random graphs.