Möbius Polynomials of Face Posets of Convex Polytopes

The Möbius polynomial is an invariant of ranked posets, closely related to the Möbius function. In this paper, we study the Möbius polynomial of face posets of convex polytopes. We present formulas for computing the Möbius polynomial of the face poset of a pyramid or a prism over an existing polytope, or of the gluing of two or more polytopes in terms of the Möbius polynomials of the original polytopes. We also present general formulas for calculating Möbius polynomials of face posets of simplicial polytopes and of Eulerian posets in terms of their f-vectors and some additional constraints.     

Asymmetry of Convex Polytopes and Vertex Index of Symmetric Convex Bodies

In (Gluskin, Litvak in Geom. Dedicate 90:45–48, [2002]) it was shown that a polytope with few vertices is far from being symmetric in the Banach–Mazur distance. More precisely, it was shown that Banach–Mazur distance between such a polytope and any symmetric convex body is large. In this note we introduce a new, averaging-type parameter to measure the asymmetry of polytopes. It turns out that, surprisingly, this new parameter is still very large, in fact it satisfies the same lower bound as the Banach–Mazur distance. In a sense it shows the following phenomenon: if a convex polytope with small number of vertices is as close to a symmetric body as it can be, then most of its vertices are as bad as the worst one. We apply our results to provide a lower estimate on the vertex index of a symmetric convex body, which was recently introduced in (Bezdek, Litvak in Adv. Math. 215:626–641, [2007]). Furthermore, we give the affirmative answer to a conjecture by Bezdek (Period. Math. Hung. 53:59–69, [2006]) on the quantitative illumination problem.     

Higher-Order Three-Term Recurrences and Asymptotics of Multiple Orthogonal Polynomials

The asymptotic theory is developed for polynomial sequences that are generated by the three-term higher-order recurrence

Uniform Spacing of Zeros of Orthogonal Polynomials

It is shown that for doubling weights, the zeros of the associated orthogonal polynomials are uniformly spaced in the sense that if cos θ _m,k , θ _m,k ∈[0,π] are the zeros of the m-th orthogonal polynomial associated with w, then θ _m,k −θ _m,k+1∼1/m. It is also shown that for doubling weights, neighboring Cotes numbers are of the same order. Finally, it is proved that these two properties are actually equivalent to the doubling property of the weight function.     

On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.     

The Analysis and the Representation of Balanced Complex Polytopes in 2D

In this paper, we deepen the theoretical study of the geometric structure of a balanced complex polytope (b.c.p.), which is the generalization of a real centrally symmetric polytope to the complex space. We also propose a constructive algorithm for the representation of its facets in terms of their associated linear functionals. The b.c.p.s are used, for example, as a tool for the computation of the joint spectral radius of families of matrices. For the representation of real polytopes, there exist well-known algorithms such as, for example, the Beneath–Beyond method. Our purpose is to modify and adapt this method to the complex case by exploiting the geometric features of the b.c.p. However, due to the significant increase in the difficulty of the problem when passing from the real to the complex case, in this paper, we confine ourselves to examine the two-dimensional case. We also propose an algorithm for the computation of the norm the unit ball of which is a b.c.p. This work was supported by INdAM-GNCS.     

Sobolev Spaces with Respect to Measures in Curves and Zeros of Sobolev Orthogonal Polynomials

In this paper we obtain some practical criteria to bound the multiplication operator in Sobolev spaces with respect to measures in curves. As a consequence of these results, we characterize the weighted Sobolev spaces with bounded multiplication operator, for a large class of weights. To have bounded multiplication operator has important consequences in Approximation Theory: it implies the uniform bound of the zeros of the corresponding Sobolev orthogonal polynomials, and this fact allows to obtain the asymptotic behavior of Sobolev orthogonal polynomials. We also obtain some non-trivial results about these Sobolev spaces with respect to measures; in particular, we prove a main result in the theory: they are Banach spaces. J.M. Rodriguez supported in part by three grants from M.E.C. (MTM 2006-13000-C03-02, MTM 2006-11976 and MTM 2007-30904-E), Spain, and by a grant from U.C.III M./C.A.M. (CCG07-UC3M/ESP-3339), Spain. J.M. Sigarreta supported in part by a grant from M.E.C. (MTM 2006-13000-C03-02), Spain, and by a grant from U.C.III M./C.A.M. (CCG07-UC3M/ESP-3339), Spain.     

Ehrhart h ?-Vectors of Hypersimplices

We consider the Ehrhart h ^?-vector for the hypersimplex. It is well-known that the sum of the $h_{i}^{*}$ is the normalized volume which equals the Eulerian numbers. The main result is a proof of a conjecture by R.?Stanley which gives an interpretation of the $h^{*}_{i}$ coefficients in terms of descents and exceedances. Our proof is geometric using a careful book-keeping of a shelling of a unimodular triangulation. We generalize this result to other closely related polytopes.     

Mixed Type Multiple Orthogonal Polynomials for Two Nikishin Systems

We study the logarithmic and ratio asymptotics of linear forms constructed from a Nikishin system which satisfy orthogonality conditions with respect to a system of measures generated by a second Nikishin system. This construction combines type I and type II multiple orthogonal polynomials. The logarithmic asymptotics of the linear forms is expressed in terms of the extremal solution of an associated vector valued equilibrium problem for the logarithmic potential. The ratio asymptotics is described by means of a conformal representation of an appropriate Riemann surface of genus zero onto the extended complex plane.     

Weighted Poisson Cells as Models for Random Convex Polytopes

We introduce a parametric family for random convex polytopes in ? ^d which allows for an easy generation of samples for further use, e.g., as random particles in materials modelling and simulation. The basic idea consists in weighting the Poisson cell, which is the typical cell of the stationary and isotropic Poisson hyperplane tessellation, by suitable geometric characteristics. Since this approach results in an exponential family, parameters can be efficiently estimated by maximum likelihood. This work has been motivated by the desire for a flexible model for random convex particles as can be found in many composite materials such as concrete or refractory castables.     

Hölder Continuity of Roots of Complex and p-adic Polynomials

Let f be a polynomial with coefficients in an algebraically closed, valued field. We show a refinement of the principle of continuity of roots, namely, that each root α of f is locally Hölder continuous of order 1/μ as a function of the coefficients of f, where μ is the root multiplicity of α. This is derived as a consequence of a principle that could be called continuity of factors, namely, that if f = gh is a factorisation with (g, h) = 1, then the coefficients of g and h are locally Lipschitz continuous as functions of the coefficients of f. The proofs are elementary and of an algebraic nature.     

On the Local Time of Random Walks Associated with Gegenbauer Polynomials

The local time of random walks associated with Gegenbauer polynomials \(P_{n}^{(\alpha)}(x)\), x∈[?1,1], is studied in the recurrent case: \(\alpha\in [-\frac{1}{2},0]\). When α is nonzero, the limit distribution is given in terms of a Mittag-Leffler distribution. The proof is based on a local limit theorem for the random walk associated with Gegenbauer polynomials. As a by-product, we derive the limit distribution of the local time of some particular birth-and-death Markov chains on ?.     

Primitive Roots and Linearized Polynomials

Let f(x) = sum from t=0 to n α_ix~i∈GF(p)[x],we associate it with a ploynomial f~*(x)=sum from i=0 to n α_ix~(p~i),f(x) and f~*(x)are called p-associates of each other. f~*(x) is called a p-ploynomial,customary to speak of linearized polynomial. Let f(x)=x~m- 1/g(x), m = m_1~r, q = p~m, g(x)∈GF(p)[x],r be the order of g(x). Cohen and the author observed that if m_1≥2, there alwaysexsists a primitive roots ζ∈GF(q) suck that f~*(ζ) = f~*(c), here f~*(c)≠0. In fact     

Denjoy–Carleman Differentiable Perturbation of Polynomials and Unbounded Operators

Let \({t\mapsto A(t)}\) for \({t\in T}\) be a C ^M -mapping with values unbounded operators with compact resolvents and common domain of definition which are self-adjoint or normal. Here C ^M stands for C ^ω (real analytic), a quasianalytic or non-quasianalytic Denjoy–Carleman class, C ^∞, or a Hölder continuity class C ^0,α . The parameter domain T is either \({\mathbb R}\) or \({\mathbb R^n}\) or an infinite dimensional convenient vector space. We prove and review results on C ^M -dependence on t of the eigenvalues and eigenvectors of A(t).     

Approximation Properties of Julia Polynomials

Let G be a finite simply connected domain in the complex plane C, bounded by a rectifiable Jordan curve L, and let w = φ0 （z） be the Riemann conformal mapping of G onto D （0, r0） ：= {E-mail： ： ｜｜ 〈 r0}, normalized by the conditions φ0 （z0） = 0, φ＇0 （z0） = 1. In this work, the rate of approximation of φ0 by the polynomials, defined with the help of the solutions of some extremal problem, in a closed domain G is studied. This rate depends on the geometric properties of the boundary L.     

Random Sampling of Sparse Trigonometric Polynomials, II. Orthogonal Matching Pursuit versus Basis Pursuit

We investigate the problem of reconstructing sparse multivariate trigonometric polynomials from few randomly taken samples by Basis Pursuit and greedy algorithms such as Orthogonal Matching Pursuit (OMP) and Thresholding. While recovery by Basis Pursuit has recently been studied by several authors, we provide theoretical results on the success probability of reconstruction via Thresholding and OMP for both a continuous and a discrete probability model for the sampling points. We present numerical experiments, which indicate that usually Basis Pursuit is significantly slower than greedy algorithms, while the recovery rates are very similar.