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: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: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: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:S. Carrozza; A. Tanasa Pages: 108 - 120 Abstract: Publication date: February 2018 Source:Advances in Applied Mathematics, Volume 93 Author(s): S. Carrozza, A. Tanasa After recalling the definition of Grassmann algebra and elements of Grassmann–Berezin calculus, we use the expression of Pfaffians as Grassmann integrals to generalize a series of formulas relating generating functions of paths in digraphs to Pfaffians. We start with the celebrated Lindström–Gessel–Viennot formula, which we derive in the general case of a graph with cycles. We then make further use of Grassmann algebraic tools to prove a generalization of the results of Stembridge [13]. Our results, which are applicable to graphs with cycles, are formulated in terms of systems of nonintersecting paths and nonintersecting cycles in digraphs.

Authors:Bing Gao; Qiyu Sun; Yang Wang; Zhiqiang Xu Pages: 121 - 141 Abstract: Publication date: February 2018 Source:Advances in Applied Mathematics, Volume 93 Author(s): Bing Gao, Qiyu Sun, Yang Wang, Zhiqiang Xu In this paper, we consider the affine phase retrieval problem in which one aims to recover a signal from the magnitudes of affine measurements. Let { a j } j = 1 m ⊂ H d and b = ( b 1 , … , b m ) ⊤ ∈ H m , where H = R or C . We say { a j } j = 1 m and b are affine phase retrievable for H d if any x ∈ H d can be recovered from the magnitudes of the affine measurements { 〈 a j , x 〉 + b j , 1 ≤ j ≤ m } . We develop general framework for affine phase retrieval and prove necessary and sufficient conditions for { a j } j = 1 m and b to be affine phase retrievable. We establish results on minimal measurements and generic measurements for affine phase retrieval as well as on sparse affine phase retrieval. In particular, we also highlight some notable differences between affine phase retrieval and the standard phase retrieval in which one aims to recover a signal x from the magnitudes of its linear measurements. In standard phase retrieval, one can only recover x up to a unimodular constant, while affine phase retrieval removes this ambiguity. We prove that unlike standard phase retrieval, the affine phase retrievable measurements { a j } j = 1 m and b do not form an open set in H m × d × H m . Also in the complex setting, the standard phase retrieval requires 4 d − O ( log 2 d ) measurements, while the affine phase retrieval only needs m = 3 d measurements.

Authors:Alice L.L. Gao; Matthew H.Y. Xie; Arthur L.B. Yang Pages: 1 - 16 Abstract: Publication date: January 2018 Source:Advances in Applied Mathematics, Volume 92 Author(s): Alice L.L. Gao, Matthew H.Y. Xie, Arthur L.B. Yang In the study of determinant formulas for Schur functions, Hamel and Goulden introduced a class of Giambelli-type matrices with respect to outside decompositions of partition diagrams, which unify the Jacobi–Trudi matrices, the Giambelli matrices and the Lascoux–Pragacz matrices. Stanley determined the Smith normal form of a specialized Jacobi–Trudi matrix. Motivated by Stanley's work, we obtain the Smith normal form of a specialized Giambelli matrix and a specialized Lascoux–Pragacz matrix. Furthermore, we show that, for a given partition, the Smith normal form of any specialized Giambelli-type matrix can be obtained from that of the corresponding specialization of the classical Giambelli matrix by a sequence of stabilization operations.

Authors:Stephen DeSalvo Pages: 17 - 50 Abstract: Publication date: January 2018 Source:Advances in Applied Mathematics, Volume 92 Author(s): Stephen DeSalvo We present a probabilistic divide-and-conquer (PDC) method for exact sampling of conditional distributions of the form L ( X X ∈ E ) , where X is a random variable on X , a complete, separable metric space, and event E with P ( E ) ≥ 0 is assumed to have sufficient regularity such that the conditional distribution exists and is unique up to almost sure equivalence. The PDC approach is to define a decomposition of X via sets A and B such that X = A × B , and sample from each separately. The deterministic second half approach is to select the sets A and B such that for each element a ∈ A , there is only one element b a ∈ B for which ( a , b a ) ∈ E . We show how this simple approach provides non-trivial improvements to several conventional random sampling algorithms in combinatorics, and we demonstrate its versatility with applications to sampling from sufficiently regular conditional distributions.

Authors:Larry X.W. Wang; Gary Y.B. Xie; Andy Q. Zhang Pages: 51 - 72 Abstract: Publication date: January 2018 Source:Advances in Applied Mathematics, Volume 92 Author(s): Larry X.W. Wang, Gary Y.B. Xie, Andy Q. Zhang Let p ( n ) denote the integer partition function. Good conjectured that Δ r p ( n ) alternates in sign up to a certain value n = n ( r ) , and then it stays positive. Gupta showed that for any given r and sufficiently large n, Δ r p ( n ) > 0 . Odlyzko proved this conjecture and gave an asymptotic formula for n ( r ) . Then, Almkvist, Knessel and Keller gave many contributions for the exact value of n ( r ) . For the finite difference of log p ( n ) , DeSalvo and Pak proved that 0 ≤ − △ 2 log p ( n − 1 ) ≤ log ( 1 + 1 n ) and conjectured a sharper upper bound for − △ 2 log p ( n ) . Chen, Wang and Xie proved this conjecture and showed the positivity of ( − 1 ) r − 1 △ r log p ( n ) , and further gave an upper bound for ( − 1 ) r − 1 △ r log p ( n ) . As for the overpartition function p ‾ ( n ) , Engel recently proved that p ‾ ( n ) is log-concave for n ≥ 2 , that is, − △ 2 log p ‾ ( n ) ≥ 0 for n ≥ 2 . Motivated by these results, in this paper we will prove the positivity of finite differences of the overpartition function and give an upper bound for △ r p ‾ ( n ) . Then we show that for any given r ≥ 1 , there exists a positive number n ( r ) such that ( − 1 ) r − 1 △ r log p ‾ ( n ) PubDate: 2017-07-23T04:06:40Z DOI: 10.1016/j.aam.2017.06.001 Issue No:Vol. 92 (2017)

Authors:Dario De Stavola Pages: 73 - 98 Abstract: Publication date: January 2018 Source:Advances in Applied Mathematics, Volume 92 Author(s): Dario De Stavola In recent years increasing attention has been paid on the area of supercharacter theories, especially to those of the upper unitriangular group. A particular supercharacter theory, in which supercharacters are indexed by set partitions, has several interesting properties, which make it object of further study. We define a natural generalization of the Plancherel measure, called superplancherel measure, and prove a limit shape result for a random set partition according to this distribution. We also give a description of the asymptotical behavior of two set partition statistics related to the supercharacters. The study of these statistics when the set partitions are uniformly distributed has been done by Chern, Diaconis, Kane and Rhoades.

Authors:Van Hoang Nguyen Pages: 99 - 121 Abstract: Publication date: January 2018 Source:Advances in Applied Mathematics, Volume 92 Author(s): Van Hoang Nguyen We extend the definition of the centroid body operator to an Orlicz–Lorentz centroid body operator on the star bodies in R n , and establish the sharp affine isoperimetric inequality that bounds (from below) the volume of the Orlicz–Lorentz centroid body of any convex body containing the origin in its interior by the volume of this convex body.

Authors:Caprice Stanley; Tobias Windisch Pages: 122 - 143 Abstract: Publication date: January 2018 Source:Advances in Applied Mathematics, Volume 92 Author(s): Caprice Stanley, Tobias Windisch Graphs on lattice points are studied whose edges come from a finite set of allowed moves of arbitrary length. We show that the diameter of these graphs on fibers of a fixed integer matrix can be bounded from above by a constant. We then study the mixing behaviour of heat-bath random walks, a generalization of the Glauber dynamics, on these graphs. We also state explicit conditions on the set of moves so that the heat-bath random walk mixes rapidly in fixed dimension.

Authors:Samuel Johnson; Marni Mishna; Karen Yeats Pages: 144 - 163 Abstract: Publication date: January 2018 Source:Advances in Applied Mathematics, Volume 92 Author(s): Samuel Johnson, Marni Mishna, Karen Yeats We provide a combinatorial derivation of the exponential growth constant for counting sequences of lattice path models restricted to the quarter plane. The values arise as bounds from analysis of related half planes models. We give explicit formulas, and the bounds are provably tight. The strategy is easily generalizable to cones in higher dimensions, and has implications for random generation.

Authors:Winfried Bruns; Aldo Conca Pages: 1 - 23 Abstract: Publication date: October 2017 Source:Advances in Applied Mathematics, Volume 91 Author(s): Winfried Bruns, Aldo Conca We study a large family of products of Borel fixed ideals of maximal minors. We compute their initial ideals and primary decompositions, and show that they have linear free resolutions. The main tools are an extension of straightening law and a very uniform primary decomposition formula. We study also the homological properties of associated multi-Rees algebra which are shown to be Cohen–Macaulay, Koszul and defined by a Gröbner basis of quadrics.

Authors:Bogdan Ichim; Julio José Moyano-Fernández Pages: 24 - 43 Abstract: Publication date: October 2017 Source:Advances in Applied Mathematics, Volume 91 Author(s): Bogdan Ichim, Julio José Moyano-Fernández The set of (ordered) score sheets of a round-robin football tournament played between n teams together with the pointwise addition has the structure of an affine monoid. In this paper we study (using both theoretical and computational methods) the most important invariants of this monoid, namely the Hilbert basis, the multiplicity, the Hilbert series and the Hilbert function.

Authors:Anne Marie Svane; Eva B. Vedel Jensen Pages: 44 - 75 Abstract: Publication date: October 2017 Source:Advances in Applied Mathematics, Volume 91 Author(s): Anne Marie Svane, Eva B. Vedel Jensen Motivated by applications in local stereology, a new rotational Crofton formula is derived for Minkowski tensors. For sets of positive reach, the formula shows how rotational averages of intrinsically defined Minkowski tensors on sections passing through the origin are related to the geometry of the sectioned set. In particular, for Minkowski tensors of order j − 1 on j-dimensional linear subspaces, we derive an explicit formula for the rotational average involving hypergeometric functions. Sectioning with lines and hyperplanes through the origin is considered in detail. We also study the case where the sections are not restricted to pass through the origin. For sets of positive reach, we here obtain a Crofton formula for the integral mean of intrinsically defined Minkowski tensors on j-dimensional affine subspaces.

Authors:Ai-Jun Li; Qingzhong Huang; Dongmeng Xi Pages: 76 - 97 Abstract: Publication date: October 2017 Source:Advances in Applied Mathematics, Volume 91 Author(s): Ai-Jun Li, Qingzhong Huang, Dongmeng Xi Let 1 ≤ k ≤ n . Sharp volume inequalities for k-dimensional sections of Wulff shapes and dual inequalities for projections are established. As their applications, several special Wulff shapes are investigated.

Authors:Jason P. Smith Pages: 98 - 114 Abstract: Publication date: October 2017 Source:Advances in Applied Mathematics, Volume 91 Author(s): Jason P. Smith We present a two term formula for the Möbius function of intervals in the poset of all permutations, ordered by pattern containment. The first term in this formula is the number of so called normal occurrences of one permutation in another. Our definition of normal occurrences is similar to those that have appeared in several variations in the literature on the Möbius function of this and other posets, but simpler than most of them. The second term in the formula is complicated, but we conjecture that it equals zero for a significant proportion of intervals. We present some cases where the second term vanishes and others where it is nonzero. Computing the Möbius function recursively from its definition has exponential complexity, whereas the computation of the first term in our formula is polynomial and the exponential part is isolated to the second term, which seems to often vanish. We also present a result on the Möbius function of posets connected by a poset fibration.

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:Servet Abstract: Publication date: October 2017 Source:Advances in Applied Mathematics, Volume 91 Author(s): Servet Martínez We study the discrete-time evolution of a recombination transformation in population genetics. The transformation acts on a product probability space, and its evolution can be described by a Markov chain on a set of partitions that converges to the finest partition. We describe the geometric decay rate to this limit and the quasi-stationary behavior of the Markov chain when conditioned on the event that the chain does not hit the limit.

Authors:Jean Lasserre Abstract: Publication date: October 2017 Source:Advances in Applied Mathematics, Volume 91 Author(s): Jean B. Lasserre We provide a numerical scheme to approximate as closely as desired the Gaussian or exponential measure μ ( Ω ) of (not necessarily compact) basic semi-algebraic sets Ω ⊂ R n . We obtain two monotone (non-increasing and non-decreasing) sequences of upper and lower bounds ( ω ‾ d ) , ( ω _ d ) , d ∈ N , each converging to μ ( Ω ) as d → ∞ . For each d, computing ω ‾ d or ω _ d reduces to solving a semidefinite program whose size increases with d. Some preliminary (small dimension) computational experiments are encouraging and illustrate the potential of the method. The method also works for any measure whose moments are known and which satisfies Carleman's condition.

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.