Abstract: Publication date: February 2020Source: Advances in Applied Mathematics, Volume 113Author(s): Christian Gaetz, Yibo GaoAbstractWe define the notion of a separable element in a finite Weyl group, generalizing the well-studied class of separable permutations. We prove that the upper and lower order ideals in weak Bruhat order generated by a separable element are rank-symmetric and rank-unimodal, and that the product of their rank generating functions gives that of the whole group, answering an open problem of Fan Wei. We also prove that separable elements are characterized by pattern avoidance in the sense of Billey and Postnikov.

Abstract: Publication date: February 2020Source: Advances in Applied Mathematics, Volume 113Author(s): Sherry H.F. Yan, Yao Yu, Hao ZhouAbstractSimultaneous core partitions have been widely studied since Anderson's work on the enumeration of (s,t)-core partitions. Amdeberhan and Leven showed that the number of (s,s+1,…,s+k)-core partitions is equal to the number of (s,k)-Dyck paths. In this paper, we prove that self-conjugate (s,s+1,…,s+k)-core partitions are equinumerous with symmetric (s,k)-Dyck paths, confirming a conjecture posed by Cho, Huh and Sohn.

Abstract: Publication date: February 2020Source: Advances in Applied Mathematics, Volume 113Author(s): Sara C. Billey, Matjaž Konvalinka, Joshua P. SwansonAbstractWe consider the distribution of the major index on standard tableaux of arbitrary straight shape and certain skew shapes. We use cumulants to classify all possible limit laws for any sequence of such shapes in terms of a simple auxiliary statistic, aft, generalizing earlier results of Canfield–Janson–Zeilberger, Chen–Wang–Wang, and others. These results can be interpreted as giving a very precise description of the distribution of irreducible representations in different degrees of coinvariant algebras of certain complex reflection groups. We conclude with some conjectures concerning unimodality, log-concavity, and local limit theorems.

Abstract: Publication date: February 2020Source: Advances in Applied Mathematics, Volume 113Author(s): Duff Baker-Jarvis, Bruce E. SaganAbstractDefine a permutation to be any sequence of distinct positive integers. Given two permutations π and σ on disjoint underlying sets, we denote by π⧢σ the set of shuffles of π and σ (the set of all permutations obtained by interleaving the two permutations). A permutation statistic is a function St whose domain is the set of permutations such that St(π) only depends on the relative order of the elements of π. A permutation statistic is shuffle compatible if the distribution of St on π⧢σ depends only on St(π) and St(σ) and their lengths rather than on the individual permutations themselves. This notion is implicit in the work of Stanley in his theory of P-partitions. The definition was explicitly given by Gessel and Zhuang who proved that various permutation statistics were shuffle compatible using mainly algebraic means. This work was continued by Grinberg. The purpose of the present article is to use bijective techniques to give demonstrations of shuffle compatibility. In particular, we show how a large number of permutation statistics can be shown to be shuffle compatible using a few simple bijections. Our approach also leads to a method for constructing such bijective proofs rather than having to treat each one in an ad hoc manner. Finally, we are able to prove a conjecture of Gessel and Zhuang about the shuffle compatibility of a particular statistic.

Abstract: Publication date: February 2020Source: Advances in Applied Mathematics, Volume 113Author(s): Qingzhong Huang, Ai-Jun LiAbstractIn the paper, the Lp version of Gagliardo-Nirenberg-Zhang inequality for isotropic measures is established. This inequality is the analytic analogue of the Lp Loomis-Whitney inequality and implies the classical Lp Sobolev inequality (without the best constant).

Abstract: Publication date: February 2020Source: Advances in Applied Mathematics, Volume 113Author(s): Olya MandelshtamAbstractThe inhomogeneous two-species TASEP on a ring is an exclusion process that describes particles of different species hopping clockwise on a ring with inhomogeneous rates given by parameters. We introduce a new object that we call toric rhombic alternative tableaux, which are certain fillings of tableaux on a triangular lattice tiled with rhombi, and are in bijection with the well-studied multiline queues of Ferrari and Martin. Using the tableaux, we obtain a formula for the stationary probabilities of the inhomogeneous two-species TASEP, which specializes to results of Ayyer and Linusson. We obtain, in addition, an explicit determinantal formula for these probabilities, and define a Markov chain on the tableaux that projects to the two-species TASEP on a ring.

Abstract: Publication date: Available online 6 November 2019Source: Advances in Applied MathematicsAuthor(s): Fan ChungAbstractFor a graph G with a positive clustering coefficient C, it is proved that for any positive constant ϵ, the vertex set of G can be partitioned into finitely many parts, say S1,S2,…,Sm, such that all but an ϵ fraction of the triangles in G are contained in the projections of tripartite subgraphs induced by (Si,Sj,Sk) which are ϵ-Δ-regular, where the size m of the partition depends only on ϵ and C. The notion of ϵ-Δ-regular, which is a variation of ϵ-regular for the original regularity lemma, concerns triangle density instead of edge density. Several generalizations and variations of the regularity lemma for clustering graphs are derived.

Abstract: Publication date: February 2020Source: Advances in Applied Mathematics, Volume 113Author(s): Zoe M. Himwich, Noah A. RosenbergAbstractGiven a gene tree topology and a species tree topology, a coalescent history represents a possible mapping of the list of gene tree coalescences to associated branches of a species tree on which those coalescences take place. Enumerative properties of coalescent histories have been of interest in the analysis of relationships between gene trees and species trees. The simplest enumerative result identifies a bijection between coalescent histories for a matching caterpillar gene tree and species tree with monotonic paths that do not cross the diagonal of a square lattice, establishing that the associated number of coalescent histories for n-taxon matching caterpillar trees (n⩾2) is the Catalan number Cn−1=1n(2n−2n−1). Here, we show that a similar bijection applies for non-matching caterpillars, connecting coalescent histories for a non-matching caterpillar gene tree and species tree to a class of roadblocked monotonic paths. The result provides a simplified algorithm for enumerating coalescent histories in the non-matching caterpillar case. It enables a rapid proof of a known result that given a caterpillar species tree, no non-matching caterpillar gene tree has a number of coalescent histories exceeding that of the matching gene tree. Additional results on coalescent histories can be obtained by a bijection between permissible roadblocked monotonic paths and Dyck paths. We study the number of coalescent histories for non-matching caterpillar gene trees that differ from the species tree by nearest-neighbor-interchange and subtree-prune-and-regraft moves, characterizing the non-matching caterpillar with the largest number of coalescent histories. We discuss the implications of the results for the study of the combinatorics of gene trees and species trees.

Abstract: Publication date: February 2020Source: Advances in Applied Mathematics, Volume 113Author(s): K.T. Huber, G.E. ScholzAbstractPhylogenetic networks are becoming of increasing interest to evolutionary biologists due to their ability to capture complex non-treelike evolutionary processes. From a combinatorial point of view, such networks are certain types of rooted directed acyclic graphs whose leaves are labelled by, for example, species. A number of mathematically interesting classes of phylogenetic networks are known. These include the biologically relevant class of stable phylogenetic networks whose members are defined via certain “fold-up” and “un-fold” operations that link them with concepts arising within the theory of, for example, graph fibrations. Despite this exciting link, the structural complexity of stable phylogenetic networks is still relatively poorly understood. Employing the popular tree-based, reticulation-visible, and tree-child properties which allow one to gauge this complexity in one way or another, we provide novel characterizations for when a stable phylogenetic network satisfies either one of these three properties.

Abstract: Publication date: February 2020Source: Advances in Applied Mathematics, Volume 113Author(s): J. Fernando Barbero G., Jesús Salas, Eduardo J.S. VillaseñorAbstractWe introduce a new representation for the rescaled Appell polynomials and use it to obtain asymptotic expansions to arbitrary order. This representation consists of a finite sum and an integral over a universal contour (i.e. independent of the particular polynomials considered within the Appell family). We illustrate our method by studying the zero attractors for rescaled Appell polynomials. We also discuss the asymptotics to arbitrary order of the rescaled Bernoulli polynomials.

Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Hsien-Kuei Hwang, Hua-Huai Chern, Guan-Huei DuhAbstractWe study linear recurrences of Eulerian type of the formPn(v)=(α(v)n+γ(v))Pn−1(v)+β(v)(1−v)Pn−1′(v)(n⩾1), with P0(v) given, where α(v),β(v) and γ(v) are in most cases polynomials of low degrees. We characterize the various limit laws of the coefficients of Pn(v) for large n using the method of moments and analytic combinatorial tools under varying α(v),β(v) and γ(v), and apply our results to more than two hundred of concrete examples when β(v)≠0 and more than three hundred when β(v)=0 that we gathered from the literature and from Sloane's OEIS database. The limit laws and the convergence rates we worked out are almost all new and include normal, half-normal, Rayleigh, beta, Poisson, negative binomial, Mittag-Leffler, Bernoulli, etc., showing the surprising richness and diversity of such a simple framework, as well as the power of the approaches used.

Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Sarah Ayman Goldrup, Kaitlyn PhillipsonAbstractNeural codes, represented as collections of binary strings, encode neural activity and show relationships among stimuli. Certain neurons, called place cells, have been shown experimentally to fire in convex regions in space. A natural question to ask is: Which neural codes can arise as intersection patterns of convex sets' While past research has established several criteria, complete conditions for convexity are not yet known for codes with more than four neurons. We classify all neural codes with five neurons as convex/non-convex codes. Furthermore, we investigate which of these codes can be represented by open versus closed convex sets. Interestingly, we find a code which is an open but not closed convex code and demonstrate a minimal example for this phenomenon.

Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Marie Lejeune, Michel Rigo, Matthieu RosenfeldAbstractConsider k-binomial equivalence: two finite words are equivalent if they share the same subwords of length at most k with the same multiplicities. With this relation, the k-binomial complexity of an infinite word x maps the integer n to the number of pairwise non-equivalent factors of length n occurring in x. In this paper based on the notion of template introduced by Currie et al., we show that, for all k≥2, the k-binomial complexity of the Tribonacci word coincides with its usual factor complexity p(n)=2n+1. A similar result was already known for Sturmian words, but the proof relies on completely different techniques that seemingly could not be applied for Tribonacci.

Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Kathrin Bringmann, Jonas Kaszian, Antun Milas, Sander ZwegersAbstractIn this paper, we study a family of rank two false theta series associated to the root lattice of type A2. We show that these functions appear as Fourier coefficients of a meromorphic Jacobi form of negative definite matrix index. Hypergeometric q-series identities are also obtained.

Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Aubrey Blecher, Charlotte Brennan, Arnold KnopfmacherAbstractWe define the notion of capacity, the ability to contain water, for Dyck paths of semi-length n. Initially the Dyck paths attain a maximum height h and by summing over h the capacity generating function for all Dyck paths is obtained. Thereafter, we obtain the average Dyck path capacity generating function and finally an asymptotic expression for this as the semi-length increases to infinity. The proofs make use of analytic techniques such as Mellin transforms, singularity analysis and formal residue calculus.

Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Gennadiy AverkovAbstractIn 1982, Zaks, Perles and Wills discovered a d-dimensional lattice simplex Sd,k with k interior lattice points, whose volume is linear in k and doubly exponential in the dimension d. It is conjectured that, for all d≥3 and k≥1, the simplex Sd,k is a volume maximizer in the family Pd(k) of all d-dimensional lattice polytopes with k interior lattice points. The simplex Sd,k has a facet with only one lattice point in the relative interior. We show that Sd,k is a volume maximizer in the family of simplices S∈Sd(k) that have a facet with one lattice point in its relative interior. We also show that, in the above family, the volume maximizer is unique up to unimodular transformations.

Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Matthias LenzAbstractThe first problem we investigate is the following: given k∈R≥0 and a vector v of Plücker coordinates of a point in the real Grassmannian, is the vector obtained by taking the kth power of each entry of v again a vector of Plücker coordinates' For k≠1, this is true if and only if the corresponding matroid is regular. Similar results hold over other fields. We also describe the subvariety of the Grassmannian that consists of all the points that define a regular matroid.The second topic is a related problem for arithmetic matroids. Let A=(E,rk,m) be an arithmetic matroid and let k≠1 be a non-negative integer. We prove that if A is representable and the underlying matroid is non-regular, then Ak:=(E,rk,mk) is not representable. This provides a large class of examples of arithmetic matroids that are not representable. On the other hand, if the underlying matroid is regular and an additional condition is satisfied, then Ak is representable. Bajo–Burdick–Chmutov have recently discovered that arithmetic matroids of type A2 arise naturally in the study of colourings and flows on CW complexes. In the last section, we prove a family of necessary conditions for representability of arithmetic matroids.

Abstract: Publication date: Available online 30 September 2019Source: Advances in Applied MathematicsAuthor(s): J.-P. AlloucheAbstractWhat is the product of all odious integers, i.e., of all integers whose binary expansion contains an odd number of 1's' Or more precisely, how to define a product of these integers which is not infinite, but still has a “reasonable” definition' We will answer this question by proving that this product is equal to π1/42φe−γ, where γ and φ are respectively the Euler-Mascheroni and the Flajolet-Martin constants.

Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Samantha Dahlberg, Stephanie van WilligenburgAbstractIn 1995 Stanley introduced a generalization of the chromatic polynomial of a graph G, called the chromatic symmetric function, XG, which was generalized to noncommuting variables, YG, by Gebhard-Sagan in 2001. Recently there has been a renaissance in the study of XG, in particular in classifying when XG is a positive linear combination of elementary symmetric or Schur functions.We extend this study from XG to YG, including establishing the multiplicativity of YG, and showing YG satisfies the k-deletion property. Moreover, we completely classify when YG is a positive linear combination of elementary symmetric functions in noncommuting variables, and similarly for Schur functions in noncommuting variables, in the sense of Bergeron-Hohlweg-Rosas-Zabrocki. We further establish the natural multiplicative generalization of the fundamental theorem of symmetric functions, now in noncommuting variables, and obtain numerous new bases for this algebra whose generators are chromatic symmetric functions in noncommuting variables. Finally, we show that of all known symmetric functions in noncommuting variables, only all elementary and specified Schur ones can be realized as YG for some G.

Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Ville Junnila, Tero LaihonenAbstractLocation detection in sensor networks can be handled with so called identifying codes. For an identifying code to work properly, it is required that no sensors are malfunctioning. Previously, malfunctioning sensors have been typically coped with robust identifying codes. However, they are rather large and, hence, imply high signal interference and energy consumption. To overcome these issues, collections of disjoint identifying codes have been proposed for coping with malfunctioning sensors. However, these collections have some problems regarding detection of malfunctioning sensors and, moreover, it seems unnecessary to restrict oneself to disjoint codes. In this paper, we discuss a certain type of identifying codes, for which the detection of malfunctioning sensors is easy, and based on these codes we design a collection of codes tolerant against malfunctions. We present some results on general graphs as well as optimal constructions in rook's graphs and binary Hamming spaces.

Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Susan M. Cooper, Alexandra Seceleanu, Ştefan O. Tohăneanu, Maria Vaz Pinto, Rafael H. VillarrealAbstractMotivated by notions from coding theory, we study the generalized minimum distance (GMD) function δI(d,r) of a graded ideal I in a polynomial ring over an arbitrary field using commutative algebraic methods. It is shown that δI is non-decreasing as a function of r and non-increasing as a function of d. For vanishing ideals over finite fields, we show that δI is strictly decreasing as a function of d until it stabilizes. We also study algebraic invariants of Geramita ideals. Those ideals are graded, unmixed, 1-dimensional and their associated primes are generated by linear forms. We also examine GMD functions of complete intersections and show some special cases of two conjectures of Tohăneanu–Van Tuyl and Eisenbud-Green-Harris.

Abstract: Publication date: Available online 11 July 2019Source: Advances in Applied MathematicsAuthor(s): Irene Pivotto, Gordon RoyleAbstractIn three influential papers in the 1980s and early 1990s, Joe Kung laid the foundations for extremal matroid theory which he envisaged as finding the growth rate of certain classes of matroids along with a characterisation of the extremal matroids in each such class. At the time, he was particularly interested in the minor-closed classes of binary matroids obtained by excluding the cycle matroids of the Kuratowski graphs K3,3 and/or K5. While he obtained strong bounds on the growth rate of these classes, it seems difficult to give the exact growth rate without a complete characterisation of the matroids in each class, which at the time seemed hopelessly complicated. Many years later, Mayhew, Royle and Whittle gave a characterisation of the internally 4-connected binary matroids with no M(K3,3)-minor, from which the answers to Kung's questions follow immediately. In this characterisation, two thin families of binary matroids play an unexpectedly important role as the only non-cographic infinite families of internally 4-connected binary matroids with no M(K3,3)-minor. As the matroids are closely related to the cubic and quartic Möbius ladders, they were called the triangular Möbius matroids and the triadic Möbius matroids. Preliminary investigations of the class of binary matroids with no M(K5)-minor suggest that, once again, the triangular Möbius matroids will be the extremal internally 4-connected matroids in this class. Here we undertake a systematic study of these two families of binary matroids collecting in one place fundamental information about them, including their representations, connectivity properties, minor structure, automorphism groups and their chromatic polynomials. Along the way, we highlight the different ways in which these matroids have arisen naturally in a number of results and problems (both open and settled) in structural and extremal matroid theory.

Abstract: Publication date: Available online 29 May 2019Source: Advances in Applied MathematicsAuthor(s): Fan Chung, Persi Diaconis, Ron GrahamAbstractWe introduce techniques for deriving closed form generating functions for enumerating permutations with restricted positions keeping track of various statistics. The method involves evaluating permanents with variables as entries. These are applied to determine the sample size required for a novel sequential importance sampling algorithm for generating random perfect matchings in classes of bipartite graphs.

Abstract: Publication date: Available online 17 May 2019Source: Advances in Applied MathematicsAuthor(s): William Y.C. Chen, Harold R.L. YangAbstractThe polynomials ψk(r,x) were introduced by Ramanujan. Berndt, Evans and Wilson obtained a recurrence relation for ψk(r,x). Shor introduced polynomials related to improper edges of a rooted tree, leading to a refinement of Cayley's formula. Zeng realized that the polynomials of Ramanujan coincide with the polynomials of Shor, and that the recurrence relation of Shor coincides with the recurrence relation of Berndt, Evans and Wilson. These polynomials also arise in the work of Wang and Zhou on the orbifold Euler characteristics of the moduli spaces of stable curves. Dumont and Ramamonjisoa found a context-free grammar G to generate the number of rooted trees on n vertices with k improper edges. Based on the grammar G, we find a grammar H for the Ramanujan-Shor polynomials. This leads to a formal calculus for these polynomials. In particular, we obtain a grammatical derivation of the Berndt-Evans-Wilson-Shor recursion. We also provide a grammatical approach to the Abel identities and a grammatical explanation of the Lacasse identity.

Abstract: Publication date: Available online 2 May 2019Source: Advances in Applied MathematicsAuthor(s): Joseph E. Bonin, Carolyn Chun, Steven D. NobleAbstractVf-safe delta-matroids have the desirable property of behaving well under certain duality operations. Several important classes of delta-matroids are known to be vf-safe, including the class of ribbon-graphic delta-matroids, which is related to the class of ribbon graphs or embedded graphs in the same way that graphic matroids correspond to graphs. In this paper, we characterize vf-safe delta-matroids and ribbon-graphic delta-matroids by finding the minimal obstructions, called excluded 3-minors, to membership in the class. We find the unique (up to twisted duality) excluded 3-minor within the class of set systems for the class of vf-safe delta-matroids. In the literature, binary delta-matroids appear in many different guises, with appropriate notions of minor operations equivalent to that of 3-minors, perhaps most notably as graphs with vertex minors. We give a direct explanation of this equivalence and show that some well-known results may be expressed in terms of 3-minors.

Abstract: Publication date: Available online 30 April 2019Source: Advances in Applied MathematicsAuthor(s): Joseph E. Bonin, Carolyn Chun, Steven D. NobleAbstractIn [30], Tardos studied special delta-matroids obtained from sequences of Higgs lifts; these are the full Higgs lift delta-matroids that we treat and around which all of our results revolve. We give an excluded-minor characterization of the class of full Higgs lift delta-matroids within the class of all delta-matroids, and we give similar characterizations of two other minor-closed classes of delta-matroids that we define using Higgs lifts. We introduce a minor-closed, dual-closed class of Higgs lift delta-matroids that arise from lattice paths. It follows from results of Bouchet that all delta-matroids can be obtained from full Higgs lift delta-matroids by removing certain feasible sets; to address which feasible sets can be removed, we give an excluded-minor characterization of delta-matroids within the more general structure of set systems. Many of these excluded minors occur again when we characterize the delta-matroids in which the collection of feasible sets is the union of the collections of bases of matroids of different ranks, and yet again when we require those matroids to have special properties, such as being paving.