Abstract: Publication date: January 2019Source: Advances in Applied Mathematics, Volume 102Author(s): István Miklós, Heather Smith We study the complexity of computing the partition function of medians for binary strings with Hamming distance using various weight functions. When the weight function is the factorial function, this partition function has application in bioinformatics, counting the most parsimonious scenarios on a star tree under the Single Cut-or-Join model for genome rearrangement. Although this model is computationally simple, we show that it is #P-complete to compute the partition function. Our results are also extended to binary trees as we show that it is #P-complete to calculate the most parsimonious scenarios on an arbitrary binary tree under the Single Cut-or-Join model. These results also apply to substitution models for many biological sequences.

Abstract: Publication date: January 2019Source: Advances in Applied Mathematics, Volume 102Author(s): Noah A. Rosenberg In mathematical phylogenetics, given a rooted binary leaf-labeled gene tree topology G and a rooted binary leaf-labeled species tree topology S with the same leaf labels, a coalescent history represents a possible mapping of the list of gene tree coalescences to the associated branches of the species tree on which those coalescences take place. For certain families of ordered pairs (G,S), the number of coalescent histories increases exponentially or even faster than exponentially with the number of leaves n. Other pairs have only a single coalescent history. We term a pair (G,S)lonely if it has only one coalescent history. Here, we characterize the set of all lonely pairs (G,S). Further, we characterize the set of pairs of rooted binary unlabeled tree shapes at least one of the labelings of which is lonely. We provide formulas for counting lonely pairs and pairs of unlabeled tree shapes with at least one lonely labeling. The lonely pairs provide a set of examples of pairs (G,S) for which the number of compact coalescent histories—which condense coalescent histories into a set of equivalence classes—is equal to the number of coalescent histories. Application of the condition that characterizes lonely pairs can also be used to reduce computation time for the enumeration of coalescent histories.

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Yves Martinez-Maure In this paper, we will try to argue and to show through fundamental examples that (a very huge class of) marginally trapped surfaces arise naturally from a ‘lightlike co-contact structure’, exactly in the same way as Legendrian fronts arise from a contact one (by projection of a Legendrian submanifold to the base of a Legendrian fibration), and that there is an adjunction relationship between both notions. We especially focus our interest on marginally trapped hedgehogs and study their relationships with Laguerre geometry and Brunn–Minkowski theory.

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Paola Bonizzoni, Clelia De Felice, Rocco Zaccagnino, Rosalba Zizza Motivated by applications to string processing, we introduce variants of the Lyndon factorization called inverse Lyndon factorizations. Their factors, named inverse Lyndon words, are in a class that strictly contains anti-Lyndon words, that is Lyndon words with respect to the inverse lexicographic order. The Lyndon factorization of a nonempty word w is unique but w may have several inverse Lyndon factorizations. We prove that any nonempty word w admits a canonical inverse Lyndon factorization, named ICFL(w), that maintains the main properties of the Lyndon factorization of w: it can be computed in linear time, it is uniquely determined, and it preserves a compatibility property for sorting suffixes. In particular, the compatibility property of ICFL(w) is a consequence of another result: any factor in ICFL(w) is a concatenation of consecutive factors of the Lyndon factorization of w with respect to the inverse lexicographic order.

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Károly Bezdek, Márton Naszódi The contact graph of a packing of translates of a convex body in Euclidean d-space Ed is the simple graph whose vertices are the members of the packing, and whose two vertices are connected by an edge if the two members touch each other. A packing of translates of a convex body is called totally separable, if any two members can be separated by a hyperplane in Ed disjoint from the interior of every packing element.We give upper bounds on the maximum degree (called separable Hadwiger number) and the maximum number of edges (called separable contact number) of the contact graph of a totally separable packing of n translates of an arbitrary smooth convex body in Ed with d=2,3,4. In the proofs, linear algebraic and convexity methods are combined with volumetric and packing density estimates based on the underlying isoperimetric (resp., reverse isoperimetric) inequality.

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): C. Krattenthaler, D. Yaqubi We evaluate Hankel determinants of matrices in which the entries are generating functions for paths consisting of up-steps, down-steps and level steps with a fixed starting point but variable end point. By specialisation, these determinant evaluations have numerous corollaries. In particular, one consequence is that the Hankel determinant of Motzkin prefix numbers equals 1, regardless of the size of the Hankel matrix.

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Mahir Bilen Can We show that the poset of SL(n)-orbit closures in the product of two partial flag varieties is a lattice if the action of SL(n) is spherical.

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Sun Yijing We establish the existence and uniqueness of positive solutions for some planar Orlicz Minkowski problems involving 0

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Francesco Brenti, Mario Marietti We characterize the classical complex reflection groups for which a recent symmetric group equidistribution result studied by Diaconis, Evans, and Graham holds. This leads to some refinements of the original result, which seem to be new even in the symmetric group case.

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Carolyn Chun, James Oxley Let M be a 3-connected binary matroid; M is called internally 4-connected if one side of every 3-separation is a triangle or a triad, and M is internally 4-connected if one side of every 3-separation is a triangle, a triad, or a 4-element fan. Assume M is internally 4-connected and that neither M nor its dual is a cubic Möbius or planar ladder or a certain coextension thereof. Let N be an internally 4-connected proper minor of M. Our aim is to show that M has a proper internally 4-connected minor with an N-minor that can be obtained from M either by removing at most four elements, or by removing elements in an easily described way from a special substructure of M. When this aim cannot be met, the earlier papers in this series showed that, up to duality, M has a good bowtie, that is, a pair, {x1,x2,x3} and {x4,x5,x6}, of disjoint triangles and a cocircuit, {x2,x3,x4,x5}, where M\x3 has an N-minor and is internally 4-connected. We also showed that, when M has a good bowtie, either M\x3,x6 has an N-minor; or M\x3/x2 has an N-minor and is internally 4-connected. In this paper, we show that, when M\x3,x6 has an N-minor but is not internally 4-connected, M has an internally 4-connected proper minor with an N-minor that can be obtained from M by removing at most three elements, or by removing elements in a well-described way from one of several special substructures of M. This is a significant step towards obtaining a splitter theorem for the class of internally 4-connected binary matroids.

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Vít Jelínek, Stanislav Kučera We study the structure of 01-matrices avoiding a pattern P as an interval minor. We focus on critical P-avoiders, i.e., on the P-avoiding matrices in which changing a 0-entry to a 1-entry always creates a copy of P as an interval minor.Let Q be the 3×3 permutation matrix corresponding to the permutation 231. As our main result, we show that for every pattern P that has no rotated copy of Q as interval minor, there is a constant cP such that any row and any column in any critical P-avoiding matrix can be partitioned into at most cP intervals, each consisting entirely of 0-entries or entirely of 1-entries. In contrast, for any pattern P that contains a rotated copy of Q, we construct critical P-avoiding matrices of arbitrary size n×n having a row with Ω(n) alternating intervals of 0-entries and 1-entries.

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Cesar Cuenca We study the interpolation Macdonald functions, remarkable inhomogeneous generalizations of Macdonald functions, and a sequence A1,A2,… of commuting operators whose common eigenfunctions are the interpolation Macdonald functions. Such a sequence of operators arises in the projective limit of finite families of commuting q-difference operators studied by Okounkov, Knop and Sahi. The main theorem is an explicit formula for the operators Ak. Our formula involves the family of Hall–Littlewood functions and a new family of inhomogeneous Hall–Littlewood functions, for which we give an explicit construction and identify as a degeneration of the interpolation Macdonald functions when q→0. This article is inspired by the recent papers of Nazarov–Sklyanin on Macdonald and Sekiguchi–Debiard operators, and our main theorem is an extension of their results.

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Toufik Mansour In this paper, we study the generating function for the number of set partitions of [n] represented as bargraphs according to the number of interior vertices. In particular, we find an explicit formula for the total number of interior vertices over set partitions of [n].

Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Sinan G. Aksoy, Fan Chung, Michael Tait, Josh Tobin We show the minimum spectral gap of the normalized Laplacian over all simple, connected graphs on n vertices is (1+o(1))54n3. This minimum is achieved asymptotically by a double kite graph. Consequently, this leads to sharp upper bounds for the maximum relaxation time of a random walk, settling a conjecture of Aldous and Fill. We also improve an eigenvalue–diameter inequality by giving a new lower bound for the spectral gap of the normalized Laplacian. This eigenvalue lower bound is asymptotically best possible.