Abstract: Publication date: January 2020Source: Advances in Applied Mathematics, Volume 112Author(s): Sarah Ayman Goldrup, Kaitlyn Phillipson Neural 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 Rosenfeld Consider 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 Zwegers In 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 Knopfmacher We 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 Averkov In 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 Lenz The 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. Allouche What 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 Willigenburg In 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 Laihonen Location 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. Villarreal Motivated 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: October 2019Source: Advances in Applied Mathematics, Volume 111Author(s): Barbara Costa, Rodrigo Gondim We study the generic Jordan type of standard graded Artinian Gorenstein algebras, it is a finer invariant than whether the algebra satisfies some of the Lefschetz properties. We prove that their Jordan types are determined by the ranks of certain Mixed Hessians. We determine the possible Jordan types for algebras of low socle degree and codimension.

Abstract: Publication date: October 2019Source: Advances in Applied Mathematics, Volume 111Author(s): R. Amzi Jeffs A sunflower is a collection of sets {U1,…,Un} such that the pairwise intersection Ui∩Uj is the same for all choices of distinct i and j. We study sunflowers of convex open sets in Rd, and provide a Helly-type theorem describing a certain “rigidity” that they possess. In particular we show that if {U1,…,Ud+1} is a sunflower in Rd, then any hyperplane that intersects all Ui must also intersect ⋂i=1d+1Ui. We use our results to describe a combinatorial code Cn for all n≥2 which is on the one hand minimally non-convex, and on the other hand has no local obstructions. Along the way we further develop the theory of morphisms of codes, and establish results on the covering relation in the poset PCode.

Abstract: Publication date: October 2019Source: Advances in Applied Mathematics, Volume 111Author(s): Martin Kochol A regular chain group N is the set of integral vectors orthogonal with rows of a matrix representing a regular matroid M, i.e., a totally unimodular matrix. N correspond to the set of flows and tensions if M is a graphic and cographic matroid, respectively. We evaluate the Tutte polynomial of M as number of pairs of specified elements of N.

Abstract: Publication date: October 2019Source: Advances in Applied Mathematics, Volume 111Author(s): Gabriele Bianchi, Károly J. Böröczky, Andrea Colesanti Given a function f on the unit sphere Sn−1, the Lp Minkowski problem asks for a convex body K whose Lp surface area measure has density f with respect to the standard (n−1)-Hausdorff measure on Sn−1. In this paper we deal with the generalization of this problem which arises in the Orlicz-Brunn-Minkowski theory when an Orlicz function φ substitutes the Lp norm and p is in the range (−n,0). This problem is equivalent to solve the Monge-Ampere equationφ(h)det(∇2h+hI)=f on Sn−1, where h is the support function of the convex body K.

Abstract: Publication date: October 2019Source: Advances in Applied Mathematics, Volume 111Author(s): Peter L. Guo, Sophie C.C. Sun Gustafson and Milne proved an identity which can be used to express a Schur function sμ(x1,x2,…,xn) with μ=(μ1,μ2,…,μk) in terms of the Schur function sλ(x1,x2,…,xn), where λ=(λ1,λ2,…,λk) is a partition such that λi=μi+n−k for 1≤i≤k. On the other hand, Fehér, Némethi and Rimányi found an identity which relates sμ(x1,x2,…,xn) to the Schur function sλ(x1,x2,…,xℓ), where λ=(λ1,λ2,…,λℓ) is a partition obtained from μ by removing some of the largest parts of μ. Fehér, Némethi and Rimányi gave a geometric explanation of their identity, and they raised the question of finding a combinatorial proof. In this paper, we establish a Gustafson-Milne type identity as well as a Fehér-Némethi-Rimányi type identity for factorial Grothendieck polynomials. Specializing a factorial Grothendieck polynomial to a Schur function, we obtain a combinatorial proof of the Fehér-Némethi-Rimányi identity.

Abstract: Publication date: October 2019Source: Advances in Applied Mathematics, Volume 111Author(s): Niufa Fang, Wenxue Xu, Jiazu Zhou, Baocheng Zhu We obtain a sharp convex mixed Lorentz-Sobolev inequality, which is the functional version of an Lp Minkowski inequality. The new sharp convex mixed Lorentz-Sobolev inequality implies the sharp convex Lorentz-Sobolev inequality of Ludwig, Xiao and Zhang.

Abstract: Publication date: October 2019Source: Advances in Applied Mathematics, Volume 111Author(s): Florian Aigner This article introduces and investigates a refinement of alternating sign trapezoids by means of Catalan objects and Motzkin paths. Alternating sign trapezoids are a generalisation of alternating sign triangles, which were recently introduced by Ayyer, Behrend and Fischer. We show that the number of alternating sign trapezoids associated with a Catalan object (resp. a Motzkin path) is a polynomial function in the length of the shorter base of the trapezoid. We also study the rational roots of these polynomials and formulate several conjectures and derive some partial results. Lastly, we deduce a constant term identity for the refined counting of alternating sign trapezoids.

Abstract: Publication date: October 2019Source: Advances in Applied Mathematics, Volume 111Author(s): Hosam M. Mahmoud We investigate node degrees in a network grown from a seed by hooking self-similar components under two models of randomness: a uniform attachment model and a model based on preferential attachment. We study two degree profiles: a local profile tracking the evolution of the degree of a particular node over time, and a global profile concerned about counts of the number of nodes of a particular degree.For the local profile, under uniform attachment growth, we have the exact mean, variance and probability distribution in terms of standard combinatorial numbers like generalized harmonic numbers and Stirling numbers of the first kind. Asymptotically, we observe phases: The early nodes have an asymptotically normal distribution, intermediate nodes have a Poisson distribution and the late nodes have a degenerate distribution. In contrast, under preferential attachment, the moments of the degree of a node contain Stirling numbers of the second kind and (under appropriate scaling) the profile has a gamma-type limit law.As for the global profile, we use Pólya urns to derive strong laws. Four regimes arise according to the structure of the seed. Within these regimes, we identify a few degenerate cases. Barring these degenerate cases, we uncover an asymptotically normal joint multivariate distribution for nodes of very small degrees.

Abstract: Publication date: October 2019Source: Advances in Applied Mathematics, Volume 111Author(s): Niels Bonneux, Zachary Hamaker, John Stembridge, Marco Stevens We study Wronskians of Appell polynomials indexed by integer partitions. These families of polynomials appear in rational solutions of certain Painlevé equations and in the study of exceptional orthogonal polynomials. We determine their derivatives, their average and variance with respect to Plancherel measure, and introduce several recurrence relations. In addition, we prove an integrality conjecture for Wronskian Hermite polynomials previously made by the first and last authors. Our proofs all exploit strong connections with the theory of symmetric functions.

Abstract: Publication date: Available online 11 July 2019Source: Advances in Applied MathematicsAuthor(s): Irene Pivotto, Gordon Royle In 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 Graham We 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. Yang The 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. Noble Vf-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. Noble In [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.