Abstract: Publication date: June 2019Source: Advances in Applied Mathematics, Volume 107Author(s): Rui Duarte, António Guedes de Oliveira Let 1≤r≤n and suppose that, when the Depth-first Search Algorithm is applied to a given rooted labeled tree on n+1 vertices, exactly r vertices are visited before backtracking. Let R be the set of trees with this property. We count the number of elements of R.For this purpose, we first consider a bijection, due to Perkinson, Yang and Yu, that maps R onto the set of parking function with center (defined by the authors in a previous article) of size r. A second bijection maps this set onto the set of parking functions with run r, a property that we introduce here. We then prove that the number of length n parking functions with a given run is the number of length n rook words (defined by Leven, Rhoades and Wilson) with the same run. This is done by counting related lattice paths in a ladder-shaped region. We finally count the number of length n rook words with run r, which is the answer to our initial question.

Abstract: Publication date: Available online 14 March 2019Source: Advances in Applied MathematicsAuthor(s): Servet Martínez In the paper ‘A probabilistic analysis of a discrete-time evolution in recombination’ [4] the evolution of the recombination transformation Ξ=∑δρδ⨂J∈δμJ was described by a Markov chain (Yn) on a set of partitions, which converges to the finest partition. Our main results were the description of the geometric decay rate to the limit and the quasi-stationary behavior of the Markov chain when conditioned on the event that the chain does not hit the limit. All these results continue to be true, but the Markov chain (Yn) that was claimed to satisfy Ξn=E(⨂J∈YnμJ) required to be modified. This is done in this Corrigendum.

Abstract: Publication date: June 2019Source: Advances in Applied Mathematics, Volume 107Author(s): Hassane Kone Optimal transport theory is used to give a short proof of the Orlicz-Sobolev inequality.

Abstract: Publication date: June 2019Source: Advances in Applied Mathematics, Volume 107Author(s): Lisa Mathew, Nobin Thomas, Somnath Bera, K.G. Subramanian Consequent to the introduction of the concept of Parikh matrix of a word which is based on the notion of subwords of a word, there has been an extensive research and study based on subwords. Parikh word representable graph is one such notion which has been introduced in the recent times. On the other hand connections of partitions of a number with counts of certain subword in a binary word are known. In this paper we introduce the notion of dual of a word and investigate its relationship with conjugate partition. As a result of this study, an expression for the number of nonisomorphic Parikh word representable graphs with a given number of edges, is obtained. Several other properties of Parikh word representable graphs are also derived.

Abstract: Publication date: June 2019Source: Advances in Applied Mathematics, Volume 107Author(s): AmirHosein Sadeghimanesh, Elisenda Feliu In this work we consider the computation of Gröbner bases of the steady state ideal of reaction networks equipped with mass-action kinetics. Specifically, we focus on the role of intermediate species and the relation between the extended network (with intermediate species) and the core network (without intermediate species).We show that a Gröbner basis of the steady state ideal of the core network always lifts to a Gröbner basis of the steady state ideal of the extended network by means of linear algebra, with a suitable choice of monomial order. As illustrated with examples, this contributes to a substantial reduction of the computation time, due mainly to the reduction in the number of variables and polynomials. We further show that if the steady state ideal of the core network is binomial, then so is the case for the extended network, as long as an extra condition is fulfilled. For standard networks, this extra condition can be visually explored from the network structure alone.

Abstract: Publication date: June 2019Source: Advances in Applied Mathematics, Volume 107Author(s): Michael Cuntz, Paul Mücksch Simplicial arrangements are classical objects in discrete geometry. Their classification remains an open problem but there is a list conjectured to be complete at least for rank three. A further important class in the theory of hyperplane arrangements with particularly nice geometric, algebraic, topological, and combinatorial properties are the supersolvable arrangements. In this paper we give a complete classification of supersolvable simplicial arrangements (in all ranks). For each fixed rank, our classification already includes almost all known simplicial arrangements. Surprisingly, for irreducible simplicial arrangements of rank greater than three, our result shows that supersolvability imposes a strong integrality property; such an arrangement is called crystallographic. Furthermore we introduce Coxeter graphs for simplicial arrangements which serve as our main tool of investigation.

Abstract: Publication date: June 2019Source: Advances in Applied Mathematics, Volume 107Author(s): Olga Parshina, Luca Q. Zamboni Given a finite non-empty set A, let A+ denote the free semigroup generated by A consisting of all finite words u1u2⋯un with ui∈A. A word u∈A+ is said to be closed if either u∈A or if u is a complete first return to some factor v∈A+, meaning u contains precisely two occurrences of v, one as a prefix and one as a suffix. We study the function fxc:N→N which counts the number of closed factors of each length in an infinite word x. We derive an explicit formula for fxc in case x is an Arnoux-Rauzy word. As a consequence we prove that lim infn→∞fxc(n)=+∞.

Abstract: Publication date: June 2019Source: Advances in Applied Mathematics, Volume 107Author(s): Sami Assaf We study the graph on reduced words with edges given by the Coxeter relations for the symmetric group. We define a statistic on reduced words for a given permutation, analogous to Coxeter length for permutations, for which the graph becomes ranked with unique maximal element. We show this statistic extends naturally to balanced labellings, and use it to recover enumerative results of Edelman and Greene and of Reiner and Roichman.

Abstract: Publication date: May 2019Source: Advances in Applied Mathematics, Volume 106Author(s): Włodzimierz Bryc, Yizao Wang It is known that after scaling a random Motzkin path converges in distribution to a Brownian excursion. We prove that the fluctuations of the counting processes of the ascent steps, the descent steps and the level steps converge jointly to linear combinations of two independent processes: a Brownian motion and a Brownian excursion. The proofs rely on the Laplace transforms and an integral representation based on an identity connecting non-crossing pair partitions and joint moments of an explicit non-homogeneous Markov process.

Abstract: Publication date: May 2019Source: Advances in Applied Mathematics, Volume 106Author(s): Shishuo Fu, Dazhao Tang, Bin Han, Jiang Zeng The aim of this paper is two-fold. We first prove several new interpretations of a kind of (q,t)-Catalan numbers along with their corresponding γ-expansions using pattern avoiding permutations. Secondly, we give a complete characterization of certain (−1)-phenomenon for each subset of permutations avoiding a single pattern of length three, and discuss their q-analogues utilizing the newly obtained q-γ-expansions, as well as the continued fraction of a quint-variate generating function due to Shin and the fourth author. Moreover, we enumerate the alternating permutations avoiding simultaneously two patterns, namely (2413,3142) and (1342,2431), of length four, and consider such (−1)-phenomenon for these two subsets as well.

Abstract: Publication date: May 2019Source: Advances in Applied Mathematics, Volume 106Author(s): Armando Cerminara, Rodrigo Gondim, Giovanna Ilardi, Fulvio Maddaloni We study a generalization of Nagata idealization for level algebras. These algebras are standard graded Artinian algebras whose Macaulay dual generator is given explicitly as a bigraded polynomial of bidegree (1,d). We consider the algebra associated to polynomials of the same type of bidegree (d1,d2). We prove that the geometry of the Nagata hypersurface of order e is very similar to the geometry of the original hypersurface. We study the Lefschetz properties for Nagata idealizations of order d1, proving that WLP holds if d1≥d2. We give a complete description of the associated algebra in the monomial square free case.

Abstract: Publication date: May 2019Source: Advances in Applied Mathematics, Volume 106Author(s): Thierry E. Huillet Take a complete (sub-)critical Galton–Watson branching tree with finitely many leaves almost surely. Picking two distinct leaves at random, we ask for the height (as measured from the root) of their latest common ancestor. Upon conditioning on the first branching event we compute the distribution of this height, with calculations explicit in the case of a binary tree.

Abstract: Publication date: May 2019Source: Advances in Applied Mathematics, Volume 106Author(s): Alexander E. Patkowski We offer some further applications of some Bailey pairs related to some mock theta functions which were established in a recent study. We discuss and offer some double-sum q-series, with new relationships among mock theta functions. We also offer a new relationship between the Bailey pair of Bringmann and Kane with that of Andrews.

Abstract: Publication date: May 2019Source: Advances in Applied Mathematics, Volume 106Author(s): Zhousheng Mei, Suijie Wang In this paper, we study pattern avoidances of generalized permutations and show that the number of all generalized permutations avoiding π is independent of the choice of π∈S3, which extends the classic results on permutations avoiding π∈S3. Extending both Dyck path and Riordan path, we introduce the Catalan–Riordan path which turns out to be a combinatorial interpretation of the difference array of Catalan numbers. As applications, we interpret both Motzkin and Riordan numbers in two ways, via semistandard Young tableaux of two rows and generalized permutations avoiding π∈S3. Analogous to Lewis's method, we establish a bijection from generalized permutations to rectangular semistandard Young tableaux which will recover several known results in the literature.