Abstract: Publication date: June 2020Source: Advances in Applied Mathematics, Volume 117Author(s): Antonio Jiménez-Pastor, Veronika Pillwein, Michael F. Singer

Abstract: Publication date: June 2020Source: Advances in Applied Mathematics, Volume 117Author(s): Mourad E.H. Ismail, Plamen SimeonovAbstractWe derive the connection relations between three q-Taylor polynomial bases. We also derive the connection relations between two of these bases and the continuous q-Hermite polynomials, as well as several new generating functions for the continuous q-Hermite polynomials. Our results also lead to some new integral evaluations. Using one of these connection relations, we give a new proof of a general addition theorem of Suslov for the q-exponential function Eq of Ismail and Zhang.

Abstract: Publication date: June 2020Source: Advances in Applied Mathematics, Volume 117Author(s): Thieu N. Vo, Yi ZhangAbstractWe propose an algebraic geometric approach for studying rational solutions of first-order algebraic ordinary difference equations (AOΔEs). For an autonomous first-order AOΔE, we give an upper bound for the degrees of its rational solutions, and thus derive a complete algorithm for computing corresponding rational solutions.

Abstract: Publication date: Available online 10 January 2020Source: Advances in Applied MathematicsAuthor(s): Dillon Mayhew, Mike Newman, Geoff WhittleAbstractA minor-closed class of matroids is (strongly) fractal if the number of n-element matroids in the class is dominated by the number of n-element excluded minors. We conjecture that when K is an infinite field, the class of K-representable matroids is strongly fractal. We prove that the class of sparse paving matroids with at most k circuit-hyperplanes is a strongly fractal class when k is at least three. The minor-closure of the class of spikes with at most k circuit-hyperplanes (with k≥5) satisfies a strictly weaker condition: the number of 2t-element matroids in the class is dominated by the number of 2t-element excluded minors. However, there are only finitely many excluded minors with ground sets of odd size.

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: 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: 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.