Authors:Rachel Karpman Pages: 25 - 76 Abstract: Publication date: July 2018 Source:Advances in Applied Mathematics, Volume 98 Author(s): Rachel Karpman The stratification of the Grassmannian by positroid varieties has been the subject of extensive research. Positroid varieties are in bijection with a number of combinatorial objects, including k-Bruhat intervals and bounded affine permutations. In addition, Postnikov's boundary measurement map gives a family of parametrizations of each positroid variety; the domain of each parametrization is the space of edge weights of a weighted planar network. In this paper, we generalize the combinatorics of positroid varieties to the Lagrangian Grassmannian Λ ( 2 n ) , which is the type C analog of the ordinary, or type A, Grassmannian. The Lagrangian Grassmannian has a stratification by projected Richardson varieties, which are the type C analogs of positroid varieties. We define type C generalizations of bounded affine permutations and k-Bruhat intervals, as well as several other combinatorial posets which index positroid varieties. In addition, we generalize Postnikov's network parametrizations to projected Richardson varieties in Λ ( 2 n ) . In particular, we show that restricting the edge weights of our networks to R + yields a family of parametrizations for totally nonnegative cells in Λ ( 2 n ) . In the process, we obtain a set of linear relations among the Plücker coordinates on Gr ( n , 2 n ) which cut out the Lagrangian Grassmannian set-theoretically.

Authors:Jacques Demongeot; Sylvain Sené Pages: 77 - 99 Abstract: Publication date: July 2018 Source:Advances in Applied Mathematics, Volume 98 Author(s): Jacques Demongeot, Sylvain Sené This paper addresses the question of the impact of the boundary on the dynamical behaviour of finite Boolean automata networks on Z2. The evolution over discrete time of such networks is governed by a specific stochastic threshold non-linear transition rule derived from the classical rule of formal neural networks. More precisely, the networks considered in this paper are finite but the study is done for arbitrarily large sizes. Moreover, the boundary impact is viewed as a classical definition of a phase transition in probability theory, characterising in our context the fact that a network admits distinct asymptotic behaviours when different boundary instances are assumed. The main contribution of this paper is the highlight of a formula for a necessary condition for boundary sensitivity, whose sufficiency and necessity are entirely proven with natural constraints on interaction potentials.

Authors:Arvind Ayyer; Jérémie Bouttier; Sylvie Corteel; Svante Linusson; François Nunzi Pages: 100 - 126 Abstract: Publication date: July 2018 Source:Advances in Applied Mathematics, Volume 98 Author(s): Arvind Ayyer, Jérémie Bouttier, Sylvie Corteel, Svante Linusson, François Nunzi Building on previous work by four of us (ABCN), we consider further generalizations of Warrington's juggling Markov chains. We first introduce “multispecies” juggling, which consist in having balls of different weights: when a ball is thrown it can possibly bump into a lighter ball that is then sent to a higher position, where it can in turn bump an even lighter ball, etc. We both study the case where the number of balls of each species is conserved and the case where the juggler sends back a ball of the species of its choice. In this latter case, we actually discuss three models: add-drop, annihilation and overwriting. The first two are generalisations of models presented in (ABCN) while the third one is new and its Markov chain has the ultra fast convergence property. We finally consider the case of several jugglers exchanging balls. In all models, we give explicit product formulas for the stationary probability and closed form expressions for the normalisation factor if known.

Authors:Shishuo Fu; Jiang Zeng Pages: 127 - 154 Abstract: Publication date: July 2018 Source:Advances in Applied Mathematics, Volume 98 Author(s): Shishuo Fu, Jiang Zeng Berkovich–Uncu have recently proved a companion of the well-known Capparelli's identities as well as refinements of Savage–Sills's new little Göllnitz identities. Noticing the connection between their results and Boulet's earlier four-parameter partition generating functions, we discover a new class of partitions, called k-strict partitions, to generalize their results. By applying both horizontal and vertical dissections of Ferrers' diagrams with appropriate labellings, we provide a unified combinatorial treatment of their results and shed more lights on the intriguing conditions of their companion to Capparelli's identities.

Authors:Sen-Peng Eu; Tung-Shan Fu; Hsiang-Chun Hsu; Hsin-Chieh Liao Pages: 1 - 26 Abstract: Publication date: June 2018 Source:Advances in Applied Mathematics, Volume 97 Author(s): Sen-Peng Eu, Tung-Shan Fu, Hsiang-Chun Hsu, Hsin-Chieh Liao It is a classical result that the parity-balance of the number of weak excedances of all permutations (derangements, respectively) of length n is the Euler number E n , alternating in sign, if n is odd (even, respectively). Josuat-Vergès obtained a q-analog of the results respecting the number of crossings of a permutation. One of the goals in this paper is to extend the results to the permutations (derangements, respectively) of types B and D, on the basis of the joint distribution in statistics excedances, crossings and the number of negative entries obtained by Corteel, Josuat-Vergès and Kim. Springer numbers are analogous Euler numbers that count the alternating permutations of type B, called snakes. Josuat-Vergès derived bivariate polynomials Q n ( t , q ) and R n ( t , q ) as generalized Euler numbers via successive q-derivatives and multiplications by t on polynomials in t. The other goal in this paper is to give a combinatorial interpretation of Q n ( t , q ) and R n ( t , q ) as the enumerators of the snakes with restrictions.

Authors:Christopher O'Neill; Roberto Pelayo Pages: 27 - 35 Abstract: Publication date: June 2018 Source:Advances in Applied Mathematics, Volume 97 Author(s): Christopher O'Neill, Roberto Pelayo A numerical monoid is an additive submonoid of the non-negative integers. Given a numerical monoid S, consider the family of “shifted” monoids M n obtained by adding n to each generator of S. In this paper, we characterize the Apéry set of M n in terms of the Apéry set of the base monoid S when n is sufficiently large. We give a highly efficient algorithm for computing the Apéry set of M n in this case, and prove that several numerical monoid invariants, such as the genus and Frobenius number, are eventually quasipolynomial as a function of n.

Authors:Jin Wang; Xinrong Ma Pages: 36 - 53 Abstract: Publication date: June 2018 Source:Advances in Applied Mathematics, Volume 97 Author(s): Jin Wang, Xinrong Ma In this paper we set up a bivariate representation of partial theta functions which not only unifies some famous identities for partial theta functions due to Andrews and Warnaar but also unveils a new characteristic of such identities. As further applications, we establish a general form of Warnaar's identity and a general q-series transformation associated with Bailey pairs via the use of the power series expansion of partial theta functions.

Authors:Rosena R.X. Du; Kuo Yu Pages: 54 - 63 Abstract: Publication date: June 2018 Source:Advances in Applied Mathematics, Volume 97 Author(s): Rosena R.X. Du, Kuo Yu For integers n , m with n ≥ 1 and 0 ≤ m ≤ n , an ( n , m ) -Dyck path is a lattice path in the integer lattice Z × Z using up steps ( 0 , 1 ) and down steps ( 1 , 0 ) that goes from the origin ( 0 , 0 ) to the point ( n , n ) and contains exactly m up steps below the line y = x . The classical Chung–Feller theorem says that the total number of ( n , m ) -Dyck path is independent of m and is equal to the n-th Catalan number C n = 1 n + 1 ( 2 n n ) . For any integer k with 1 ≤ k ≤ n , let p n , m , k be the total number of ( n , m ) -Dyck paths with k peaks. Ma and Yeh proved that p n , m , k = p n , n − m , n − k for 0 ≤ m ≤ n , and p n , m , k + p n , m , n − k = p n , m + 1 , k + p n , m + 1 , n − k for 1 ≤ m ≤ n − 2 . In this paper we give bijective proofs of these two results. Using our bijections, we also get refined enumeration results on the numbers p n , m , k and p n , m , k + p n , m , n − k according to the starting and ending steps.

Authors:Jan Draisma; Florian M. Oosterhof Pages: 64 - 79 Abstract: Publication date: June 2018 Source:Advances in Applied Mathematics, Volume 97 Author(s): Jan Draisma, Florian M. Oosterhof We prove that iterated toric fibre products from a finite collection of toric varieties are defined by binomials of uniformly bounded degree. This implies that Markov random fields built up from a finite collection of finite graphs have uniformly bounded Markov degree.

Authors:Christoph Koutschan; Yi Zhang Pages: 80 - 101 Abstract: Publication date: June 2018 Source:Advances in Applied Mathematics, Volume 97 Author(s): Christoph Koutschan, Yi Zhang In this paper, we study the desingularization problem in the first q-Weyl algebra. We give an order bound for desingularized operators, and thus derive an algorithm for computing desingularized operators in the first q-Weyl algebra. Moreover, an algorithm is presented for computing a generating set of the first q-Weyl closure of a given q-difference operator. As an application, we certify that several instances of the colored Jones polynomial are Laurent polynomial sequences by computing the corresponding desingularized operator.

Authors:Richard Ehrenborg; Alex Happ Pages: 1 - 17 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Richard Ehrenborg, Alex Happ We study the sum of the rth powers of the descent set statistic and how many small prime factors occur in these numbers. Our results depend upon the base p expansion of n and r.

Authors:Guo-Niu Han; Huan Xiong Pages: 18 - 38 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Guo-Niu Han, Huan Xiong Inspired by the works of Dewar, Murty and Kotěšovec, we establish some useful theorems for asymptotic formulas. As an application, we obtain asymptotic formulas for the numbers of skew plane partitions and cylindric partitions. We prove that the order of the asymptotic formula for the number of skew plane partitions of fixed width depends only on the width of the region, not on the profile (the skew zone) itself, while this is not true for cylindric partitions.

Authors:Steven N. Evans; Daniel Lanoue Pages: 39 - 75 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Steven N. Evans, Daniel Lanoue Given an edge-weighted tree T with n leaves, sample the leaves uniformly at random without replacement and let W k , 2 ≤ k ≤ n , be the length of the subtree spanned by the first k leaves. We consider the question, “Can T be identified (up to isomorphism) by the joint probability distribution of the random vector ( W 2 , … , W n ) '” We show that if T is known a priori to belong to one of various families of edge-weighted trees, then the answer is, “Yes.” These families include the edge-weighted trees with edge-weights in general position, the ultrametric edge-weighted trees, and certain families with equal weights on all edges such as ( k + 1 ) -valent and rooted k-ary trees for k ≥ 2 and caterpillars.

Authors:Alexander Garver; Thomas McConville; Khrystyna Serhiyenko Pages: 76 - 138 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Alexander Garver, Thomas McConville, Khrystyna Serhiyenko Maximal green sequences are important objects in representation theory, cluster algebras, and string theory. It is an open problem to determine what lengths are achieved by the maximal green sequences of a quiver. We combine the combinatorics of surface triangulations and the basics of scattering diagrams to address this problem. Our main result is a formula for the length of minimal length maximal green sequences of quivers defined by triangulations of an annulus or a punctured disk.

Authors:Matt DeVos; Daryl Funk Pages: 139 - 175 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Matt DeVos, Daryl Funk Given a 3-connected biased graph Ω with a balancing vertex, and with frame matroid F ( Ω ) nongraphic and 3-connected, we determine all biased graphs Ω ′ with F ( Ω ′ ) = F ( Ω ) . As a consequence, we show that if M is a 4-connected nongraphic frame matroid represented by a biased graph Ω having a balancing vertex, then Ω essentially uniquely represents M. More precisely, all biased graphs representing M are obtained from Ω by replacing a subset of the edges incident to its unique balancing vertex with unbalanced loops.

Authors:Anton Dochtermann; Ragnar Freij-Hollanti Pages: 176 - 194 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Anton Dochtermann, Ragnar Freij-Hollanti In this paper we study a pair of numerical parameters associated to a graph G. On the one hand, we consider the (topological) connectivity of the polyhedral complex Hom ( K 2 , G ) , a space of homomorphisms from a edge K 2 into G. This approach dates back to the neighborhood complexes introduced by Lovász in his proof of the Kneser conjecture. In another direction we study the warmth ζ ( G ) of a graph G, a parameter introduced by Brightwell and Winkler based on the asymptotic behavior of d-branching walks in G and inspired by constructions in statistical physics. Both the warmth of G and the connectivity of Hom ( K 2 , G ) provide lower bounds on the chromatic number of G. Here we seek to relate these two constructions, and in particular we provide evidence for the conjecture that the warmth of a graph G is always less than three plus the connectivity of Hom ( K 2 , G ) . We succeed in establishing a first nontrivial case of the conjecture, by showing that ζ ( G ) ≤ 3 if Hom ( K 2 , G ) has an infinite first homology group. We also calculate warmth for a family of ‘twisted toroidal’ graphs that are important extremal examples in the context of Hom complexes. Finally we show that ζ ( G ) ≤ n − 1 if a graph G does not have the complete bipartite graph K a , b for a + b = n . This provides an analogue for a similar result in the context of Hom complexes.

Authors:K. Hamad; A.N.W. Hone; P.H. van der Kamp; G.R.W. Quispel Pages: 216 - 248 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): K. Hamad, A.N.W. Hone, P.H. van der Kamp, G.R.W. Quispel In recent work it was shown how recursive factorisation of certain QRT maps leads to Somos-4 and Somos-5 recurrences with periodic coefficients, and to a fifth-order recurrence with the Laurent property. Here we recursively factorise the 12-parameter symmetric QRT map, given by a second-order recurrence, to obtain a system of three coupled recurrences which possesses the Laurent property. As degenerate special cases, we first derive systems of two coupled recurrences corresponding to the 5-parameter multiplicative and additive symmetric QRT maps. In all cases, the Laurent property is established using a generalisation of a result due to Hickerson, and exact formulae for degree growth are found from ultradiscrete (tropical) analogues of the recurrences. For the general 18-parameter QRT map it is shown that the components of the iterates can be written as a ratio of quantities that satisfy the same Somos-7 recurrence.

Authors:Tri Lai; Ranjan Rohatgi Pages: 249 - 285 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Tri Lai, Ranjan Rohatgi The work of Mills, Robbins, and Rumsey on cyclically symmetric plane partitions yields a simple product formula for the number of lozenge tilings of a regular hexagon, which are invariant under rotation by 120°. In this paper we generalize this result by enumerating the cyclically symmetric lozenge tilings of a hexagon in which four triangles have been removed in the center.

Authors:Jan Hubička; Jaroslav Nešetřil Pages: 286 - 311 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Jan Hubička, Jaroslav Nešetřil A bowtie is a graph consisting of two triangles with one vertex identified. We show that the class of all (finite) graphs not containing a bowtie as a subgraph has a Ramsey lift (expansion). This solves one of the old problems in the area and it is the first Ramsey class with a non-trivial algebraic closure.

Authors:Andrew R. Conway; Anthony J. Guttmann; Paul Zinn-Justin Pages: 312 - 333 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Andrew R. Conway, Anthony J. Guttmann, Paul Zinn-Justin We give an improved algorithm for counting the number of 1324-avoiding permutations, resulting in 14 further terms of the generating function, which is now known for all lengths ≤50. We re-analyse the generating function and find additional evidence for our earlier conclusion that unlike other classical length-4 pattern-avoiding permutations, the generating function does not have a simple power-law singularity, but rather, the number of 1324-avoiding permutations of length n behaves as B ⋅ μ n ⋅ μ 1 n ⋅ n g . We estimate μ = 11.600 ± 0.003 , μ 1 = 0.0400 ± 0.0005 , g = − 1.1 ± 0.1 while the estimate of B depends sensitively on the precise value of μ, μ 1 and g. This reanalysis provides substantially more compelling arguments for the presence of the stretched exponential term μ 1 n .

Authors:Jean-Paul Bultel Pages: 334 - 359 Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Jean-Paul Bultel We show that the graded dual of the Hopf algebra of word symmetric functions contains the Faà di Bruno algebra as a Hopf subalgebra. In this context, we give the expansion of natural generators of the Faà di Bruno algebra on a natural basis of this graded dual. We also give a combinatorial interpretation for the coefficients arising in this expansion.

Authors:Thomas Krajewski; Iain Moffatt; Adrian Tanasa Pages: 271 - 330 Abstract: Publication date: April 2018 Source:Advances in Applied Mathematics, Volume 95 Author(s): Thomas Krajewski, Iain Moffatt, Adrian Tanasa By considering Tutte polynomials of Hopf algebras, we show how a Tutte polynomial can be canonically associated with combinatorial objects that have some notions of deletion and contraction. We show that several graph polynomials from the literature arise from this framework. These polynomials include the classical Tutte polynomial of graphs and matroids, Las Vergnas' Tutte polynomial of the morphism of matroids and his Tutte polynomial for embedded graphs, Bollobás and Riordan's ribbon graph polynomial, the Krushkal polynomial, and the Penrose polynomial. We show that our Tutte polynomials of Hopf algebras share common properties with the classical Tutte polynomial, including deletion-contraction definitions, universality properties, convolution formulas, and duality relations. New results for graph polynomials from the literature are then obtained as examples of the general results. Our results offer a framework for the study of the Tutte polynomial and its analogues in other settings, offering the means to determine the properties and connections between a wide class of polynomial invariants.

Authors:N. Thieu Vo; Georg Grasegger; Franz Winkler Pages: 127 - 139 Abstract: Publication date: July 2018 Source:Advances in Applied Mathematics, Volume 98 Author(s): Thieu N. Vo, Georg Grasegger, Franz Winkler In this paper, we discuss three different approaches to attack the problem of determining all rational solutions for a first-order algebraic ordinary differential equation (AODE). We first give a sufficient condition for first-order AODEs to have the property that poles of rational solutions can only occur at the zeros of the leading coefficient. A combinatorial approach is presented to determine all rational solutions, if there are any, of the family of first-order AODEs satisfying this condition. Algebraic considerations based on algebraic function theory yield another algorithm for quasi-linear first-order AODEs. And finally ideas from algebraic geometry combine these results to an algorithm for finding all rational solutions of parametrizable first-order AODEs.

Authors:Nagy Abstract: Publication date: May 2018 Source:Advances in Applied Mathematics, Volume 96 Author(s): Beáta Bényi, Gábor V. Nagy We construct a new bijection between the set of n × k 0–1 matrices with no three 1's forming a Γ configuration and the set of ( n , k ) -Callan sequences, a simple structure counted by poly-Bernoulli numbers. We give two applications of this result: We derive the generating function of Γ-free matrices, and we give a new bijective proof for an elegant result of Aval et al. that states that the number of complete non-ambiguous forests with n leaves is equal to the number of pairs of permutations of { 1 , … , n } with no common rise.

Authors:Gilles Bonnet Pages: 31 - 52 Abstract: Publication date: April 2018 Source:Advances in Applied Mathematics, Volume 95 Author(s): Gilles Bonnet Until now, little was known about properties of small cells in a Poisson hyperplane tessellation. The few existing results were either heuristic or applying only to the two dimensional case and for very specific size functionals and directional distributions. This paper fills this gap by providing a systematic study of small cells in a Poisson hyperplane tessellation of arbitrary dimension, arbitrary directional distribution φ and with respect to an arbitrary size functional Σ. More precisely, we investigate the distribution of the typical cell Z, conditioned on the event { Σ ( Z ) < a } , where a → 0 and Σ is a size functional, i.e. a functional on the set of convex bodies which is continuous, not identically zero, homogeneous of degree k > 0 , and increasing with respect to set inclusion. We focus on the number of facets and the shape of such small cells. We show in various general settings that small cells tend to minimize the number of facets and that they have a non degenerated limit shape distribution which depends on the size Σ and the directional distribution. We also exhibit a class of directional distribution for which cells with small inradius do not tend to minimize the number of facets.

Authors:Antonio Giambruno; Mikhail Zaicev Pages: 53 - 64 Abstract: Publication date: April 2018 Source:Advances in Applied Mathematics, Volume 95 Author(s): Antonio Giambruno, Mikhail Zaicev Let A be a non necessarily associative algebra over a field of characteristic zero satisfying a non-trivial polynomial identity. If A is a finite dimensional algebra or an associative algebra, it is known that the sequence c n ( A ) , n = 1 , 2 , … , of codimensions of A is exponentially bounded. If A is an infinite dimensional non associative algebra such sequence can have overexponential growth. Such phenomenon is present also in the case of Lie or Jordan algebras. In all known examples the smallest overexponential growth of c n ( A ) is ( n ! ) 1 2 . Here we construct a family of algebras whose codimension sequence grows like ( n ! ) α , for any real number α with 0 < α < 1 .

Authors:Elizabeth Gross; Nida Obatake; Nora Youngs Pages: 65 - 95 Abstract: Publication date: April 2018 Source:Advances in Applied Mathematics, Volume 95 Author(s): Elizabeth Gross, Nida Obatake, Nora Youngs A neural code C is a collection of binary vectors of a given length n that record the co-firing patterns of a set of neurons. Our focus is on neural codes arising from place cells, neurons that respond to geographic stimulus. In this setting, the stimulus space can be visualized as subset of R 2 covered by a collection U of convex sets such that the arrangement U forms an Euler diagram for C . There are some methods to determine whether such a convex realization U exists; however, these methods do not describe how to draw a realization. In this work, we look at the problem of algorithmically drawing Euler diagrams for neural codes using two polynomial ideals: the neural ideal, a pseudo-monomial ideal; and the neural toric ideal, a binomial ideal. In particular, we study how these objects are related to the theory of piercings in information visualization, and we show how minimal generating sets of the ideals reveal whether or not a code is 0, 1, or 2-inductively pierced.

Authors:Georgia Benkart; Laura Colmenarejo; Pamela E. Harris; Rosa Orellana; Greta Panova; Anne Schilling; Martha Yip Pages: 96 - 115 Abstract: Publication date: April 2018 Source:Advances in Applied Mathematics, Volume 95 Author(s): Georgia Benkart, Laura Colmenarejo, Pamela E. Harris, Rosa Orellana, Greta Panova, Anne Schilling, Martha Yip We provide a crystal structure on the set of ordered multiset partitions, which recently arose in the pursuit of the Delta Conjecture. This conjecture was stated by Haglund, Remmel and Wilson as a generalization of the Shuffle Conjecture. Various statistics on ordered multiset partitions arise in the combinatorial analysis of the Delta Conjecture, one of them being the minimaj statistic, which is a variant of the major index statistic on words. Our crystal has the property that the minimaj statistic is constant on connected components of the crystal. In particular, this yields another proof of the Schur positivity of the graded Frobenius series of the generalization R n , k due to Haglund, Rhoades and Shimozono of the coinvariant algebra R n . The crystal structure also enables us to demonstrate the equidistributivity of the minimaj statistic with the major index statistic on ordered multiset partitions.

Authors:Richard A. Brualdi; Geir Dahl Pages: 116 - 151 Abstract: Publication date: April 2018 Source:Advances in Applied Mathematics, Volume 95 Author(s): Richard A. Brualdi, Geir Dahl An alternating sign matrix, or ASM, is a ( 0 , ± 1 ) -matrix where the nonzero entries in each row and column alternate in sign. We generalize this notion to hypermatrices: an n × n × n hypermatrix A = [ a i j k ] is an alternating sign hypermatrix, or ASHM, if each of its planes, obtained by fixing one of the three indices, is an ASM. Several results concerning ASHMs are shown, such as finding the maximum number of nonzeros of an n × n × n ASHM, and properties related to Latin squares. Moreover, we investigate completion problems, in which one asks if a subhypermatrix can be completed (extended) into an ASHM. We show several theorems of this type.

Authors:P.J. Forrester; J.R. Ipsen Pages: 152 - 176 Abstract: Publication date: April 2018 Source:Advances in Applied Mathematics, Volume 95 Author(s): P.J. Forrester, J.R. Ipsen We study Muttalib–Borodin ensembles — particular eigenvalue PDFs on the half-line — with classical weights, i.e. Laguerre, Jacobi or Jacobi prime. We show how the theory of the Selberg integral, involving also Jack and Schur polynomials, naturally leads to a multi-parameter generalisation of these particular Muttalib–Borodin ensembles, and also to the explicit form of underlying biorthogonal polynomials of a single variable. A suitable generalisation of the original definition of the Muttalib–Borodin ensemble allows for negative eigenvalues. In the cases of generalised Gaussian, symmetric Jacobi and Cauchy weights, we show that the problem of computing the normalisations and the biorthogonal polynomials can be reduced down to Muttalib–Borodin ensembles with classical weights on the positive half-line.

Authors:Tathagata Basak Pages: 177 - 198 Abstract: Publication date: April 2018 Source:Advances in Applied Mathematics, Volume 95 Author(s): Tathagata Basak Let L be the unique even self-dual lattice of signature ( 25 , 1 ) . The automorphism group Aut ( L ) acts on the hyperbolic space H 25 . We study a Poincaré series E ( z , s ) defined for z in H 25 , convergent for Re ( s ) > 25 , invariant under Aut ( L ) and having singularities along the mirrors of the reflection group of L. We compute the Fourier expansion of E ( z , s ) at a “Leech cusp” and prove that it can be meromorphically continued to Re ( s ) > 25 / 2 . Analytic continuation of Kloosterman sum zeta functions imply that the individual Fourier coefficients of E ( z , s ) have meromorphic continuation to the whole s-plane.

Authors:Emanuele Delucchi; Sonja Riedel Pages: 199 - 270 Abstract: Publication date: April 2018 Source:Advances in Applied Mathematics, Volume 95 Author(s): Emanuele Delucchi, Sonja Riedel We initiate the study of group actions on (possibly infinite) semimatroids and geometric semilattices. To every such action is naturally associated an orbit-counting function, a two-variable “Tutte” polynomial and a poset which, in the representable case, coincides with the poset of connected components of intersections of the associated toric arrangement. In this structural framework we recover and strongly generalize many enumerative results about arithmetic matroids, arithmetic Tutte polynomials and toric arrangements by finding new combinatorial interpretations beyond the representable case. In particular, we thus find a class of natural examples of nonrepresentable arithmetic matroids. Moreover, we discuss actions that give rise to matroids over Z with natural combinatorial interpretations. As a stepping stone toward our results we also prove an extension of the cryptomorphism between semimatroids and geometric semilattices to the infinite case.

Authors:Clark Butler Pages: 3 - 22 Abstract: Publication date: March 2018 Source:Advances in Applied Mathematics, Volume 94 Author(s): Clark Butler We introduce a generalization of the Krushkal polynomial to nonorientable surfaces, and prove that this polynomial has a natural quasi-tree expansion. This generalized Krushkal polynomial contains the Bollobás–Riordan polynomial of a (possibly nonorientable) ribbon graph as a specialization. The quasi-tree expansion proven here then extends the recent quasi-tree expansions of the Bollobás–Riordan polynomial deduced in the oriented case by A. Champanerkar et al. and in the more general unoriented case by E. Dewey and F. Vignes-Tourneret. The generalized Krushkal polynomial also contains the Las Vergnas polynomial of a cellulation of a surface as a specialization; we use this fact to deduce a quasi-tree expansion for the Las Vergnas polynomial.

Authors:Kolja Knauer; Leonardo Martínez-Sandoval; Jorge Luis Ramírez Alfonsín Pages: 23 - 38 Abstract: Publication date: March 2018 Source:Advances in Applied Mathematics, Volume 94 Author(s): Kolja Knauer, Leonardo Martínez-Sandoval, Jorge Luis Ramírez Alfonsín Let M be a matroid without loops or coloops and let T ( M ; x , y ) be its Tutte polynomial. In 1999 Merino and Welsh conjectured that max ( T ( M ; 2 , 0 ) , T ( M ; 0 , 2 ) ) ≥ T ( M ; 1 , 1 ) holds for graphic matroids. Ten years later, Conde and Merino proposed a multiplicative version of the conjecture which implies the original one. In this paper we prove the multiplicative conjecture for the family of lattice path matroids (generalizing earlier results on uniform and Catalan matroids). In order to do this, we introduce and study particular lattice path matroids, called snakes, used as building bricks to indeed establish a strengthening of the multiplicative conjecture as well as a complete characterization of the cases in which equality holds.

Authors:Joseph E. Bonin; Joseph P.S. Kung Pages: 39 - 70 Abstract: Publication date: March 2018 Source:Advances in Applied Mathematics, Volume 94 Author(s): Joseph E. Bonin, Joseph P.S. Kung The catenary data of a matroid M of rank r on n elements is the vector ( ν ( M ; a 0 , a 1 , … , a r ) ) , indexed by compositions ( a 0 , a 1 , … , a r ) , where a 0 ≥ 0 , a i > 0 for i ≥ 1 , and a 0 + a 1 + ⋯ + a r = n , with the coordinate ν ( M ; a 0 , a 1 , … , a r ) equal to the number of maximal chains or flags ( X 0 , X 1 , … , X r ) of flats or closed sets such that X i has rank i, X 0 = a 0 , and X i − X i − 1 = a i . We show that the catenary data of M contains the same information about M as its G -invariant, which was defined by H. Derksen (2009) [9]. The Tutte polynomial is a specialization of the G -invariant. We show that many known results for the Tutte polynomial have analogs for the G -invariant. In particular, we show that for many matroid constructions, the G -invariant of the construction can be calculated from the G -invariants of the constituents and that the G -invariant of a matroid can be calculated from its size, the isomorphism class of the lattice of cyclic flats with lattice elements labeled by the rank and size of the underlying set. We also show that the number of flats and cyclic flats of a given rank and size can be derived from the G -invariant, that the G -invariant of M is reconstructible from the deck of G -invariants of restrictions of M to its copoints, and that, apart from free extensions and coextensions, one can detect whether a matroid is a free product from its G -invariant.

Authors:A. Goodall; M. Hermann; T. Kotek; J.A. Makowsky; S.D. Noble Pages: 71 - 102 Abstract: Publication date: March 2018 Source:Advances in Applied Mathematics, Volume 94 Author(s): A. Goodall, M. Hermann, T. Kotek, J.A. Makowsky, S.D. Noble J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for harmonious colorings, convex colorings, m c c t -colorings, and rainbow colorings, and many more. N. Linial (1986) showed that the chromatic polynomial χ ( G ; X ) is # P -hard to evaluate for all but three values X = 0 , 1 , 2 , where evaluation is in P. This dichotomy includes evaluation at real or complex values, and has the further property that the set of points for which evaluation is in P is finite. We investigate how the complexity of evaluating univariate graph polynomials that arise from CP-colorings varies for different evaluation points. We show that for some CP-colorings (harmonious, convex) the complexity of evaluation follows a similar pattern to the chromatic polynomial. However, in other cases (proper edge colorings, m c c t -colorings, H-free colorings) we could only obtain a dichotomy for evaluations at non-negative integer points. We also discuss some CP-colorings where we only have very partial results.

Authors:Spencer Backman Pages: 103 - 119 Abstract: Publication date: March 2018 Source:Advances in Applied Mathematics, Volume 94 Author(s): Spencer Backman Gessel and Sagan investigated the Tutte polynomial, T G ( x , y ) using depth-first search, and applied their techniques to show that the number of acyclic partial orientations of a graph is 2 m − n + 1 T G ( 3 , 1 / 2 ) . We provide a short deletion-contraction proof of this result and demonstrate that dually, the number of strongly connected partial orientations is 2 n − 1 T G ( 1 / 2 , 3 ) . We then prove that the number of partial orientations modulo cycle reversals is 2 g T G ( 3 , 1 ) and the number of partial orientations modulo cut reversals is 2 n − 1 T G ( 1 , 3 ) . To prove these results, we introduce cut and cycle-minimal partial orientations which provide distinguished representatives for partial orientations modulo cut and cycle reversals, extending known representatives for full orientations introduced by Greene and Zaslavksy. We then introduce distinguished partial orientations representing a given indegree sequence. We utilize these partial orientations to derive the Ehrhart polynomial of the win vector polytope, and give a combinatorial interpretation of its volume, thus answering a question of Bartels, Mount, and Welsh. We conclude with edge chromatic generalizations of the quantities presented, which allow for a new interpretation of the reliability polynomial for all probabilities p with 0 < p < 1 / 2 .

Authors:Octavio Arizmendi Pages: 1 - 68 Abstract: Publication date: February 2018 Source:Advances in Applied Mathematics, Volume 93 Author(s): Octavio Arizmendi We introduce and study the notion of k-divisible elements in a non-commutative probability space. A k-divisible element is a (non-commutative) random variable whose n-th moment vanishes whenever n is not divisible by k. First, we consider the combinatorial convolution ⁎ in the lattices NC of non-crossing partitions and N C k of k-divisible non-crossing partitions and show that convolving k times with the zeta function in NC is equivalent to convolving once with the zeta function in N C k . Furthermore, when x is k-divisible, we derive a formula for the free cumulants of x k in terms of the free cumulants of x, involving k-divisible non-crossing partitions. Second, we prove that if a and s are free and s is k-divisible then sps and a are free, where p is any polynomial (on a and s) of degree k − 2 on s. Moreover, we define a notion of R-diagonal k-tuples and prove similar results. Next, we show that free multiplicative convolution between a measure concentrated in the positive real line and a probability measure with k-symmetry is well defined. Analytic tools to calculate this convolution are developed. Finally, we concentrate on free additive powers of k-symmetric distributions and prove that μ ⊞ t is a well defined k-symmetric probability measure, for all t > 1 . We derive central limit theorems and Poisson type ones. More generally, we consider freely infinitely divisible measures and prove that free infinite divisibility is maintained under the mapping μ → μ k . We conclude by focusing on (k-symmetric) free stable distributions, for which we prove a reproducing property generalizing the ones known for one sided and real symmetric free stable laws.

Authors:John Machacek Pages: 69 - 92 Abstract: Publication date: February 2018 Source:Advances in Applied Mathematics, Volume 93 Author(s): John Machacek Franco, Galloni, Penante, and Wen have proposed a boundary measurement map for a graph on any closed orientable surface with boundary. We consider this boundary measurement map which takes as input an edge weighted directed graph embedded on a surface and produces on element of a Grassmannian. Computing the boundary measurement requires a choice of fundamental domain. Here the boundary measurement map is shown to be independent of the choice of fundamental domain Also, a formula for the Plücker coordinates of the element of the Grassmannian in the image of the boundary measurement map is given. The formula expresses the Plücker coordinates as a rational function which can be combinatorially described in terms of paths and cycles in the directed graph.

Authors:Andrew Francis; Charles Semple; Mike Steel Pages: 93 - 107 Abstract: Publication date: February 2018 Source:Advances in Applied Mathematics, Volume 93 Author(s): Andrew Francis, Charles Semple, Mike Steel Phylogenetic networks are a type of directed acyclic graph that represent how a set X of present-day species are descended from a common ancestor by processes of speciation and reticulate evolution. In the absence of reticulate evolution, such networks are simply phylogenetic (evolutionary) trees. Moreover, phylogenetic networks that are not trees can sometimes be represented as phylogenetic trees with additional directed edges placed between their edges. Such networks are called tree-based, and the class of phylogenetic networks that are tree-based has recently been characterised. In this paper, we establish a number of new characterisations of tree-based networks in terms of path partitions and antichains (in the spirit of Dilworth's theorem), as well as via matchings in a bipartite graph. We also show that a temporal network is tree-based if and only if it satisfies an antichain-to-leaf condition. In the second part of the paper, we define three indices that measure the extent to which an arbitrary phylogenetic network deviates from being tree-based. We describe how these three indices can be computed efficiently using classical results concerning maximum-sized matchings in bipartite graphs.

Authors:Joanna A. Ellis Monaghan; Joseph P.S. Kung; Iain Moffatt Abstract: Publication date: Available online 6 October 2017 Source:Advances in Applied Mathematics Author(s): Joanna A. Ellis Monaghan, Joseph P.S. Kung, Iain Moffatt

Authors:Robert Brijder Abstract: Publication date: Available online 22 July 2017 Source:Advances in Applied Mathematics Author(s): Robert Brijder Multimatroids generalize matroids, delta-matroids, and isotropic systems, and transition polynomials of multimatroids subsume various polynomials for these latter combinatorial structures, such as the interlace polynomial and the Tutte–Martin polynomial. We prove evaluations of the Tutte–Martin polynomial of isotropic systems from Bouchet directly and more efficiently in the context of transition polynomials of multimatroids. Moreover, we generalize some related evaluations of the transition polynomial of 4-regular graphs from Jaeger to multimatroids. These evaluations are obtained in a uniform and matroid-theoretic way. We also translate the evaluations in terms of the interlace polynomial of graphs. Finally, we give an excluded-minor theorem for the class of binary tight 3-matroids (a subclass of multimatroids) based on the excluded-minor theorem for the class of binary delta-matroids from Bouchet.