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:Markus Kuba; Hosam M. Mahmoud Pages: 1 - 26 Abstract: Publication date: September 2017 Source:Advances in Applied Mathematics, Volume 90 Author(s): Markus Kuba, Hosam M. Mahmoud We study a class of balanced urn schemes on balls of two colors (say white and black). At each drawing, a sample of size m ≥ 1 is taken out from the urn, and ball addition rules are applied. We consider these multiple drawings under sampling with or without replacement. We further classify ball addition matrices according to the structure of the expected value into affine and nonaffine classes. We give a necessary and sufficient condition for a scheme to be in the affine subclass, for which we get explicit results for the expected value and second moment of the number of white balls after n steps and an asymptotic expansion of the variance. Moreover, we uncover a martingale structure. This unifies several earlier works focused on special cases of urn models with multiple drawings [5,6,17,19,20,22] as well as the special case of sample size m = 1 . The class is parametrized by Λ, specified by the ratio of the two eigenvalues of a “reduced” ball replacement matrix and the sample size. We categorize the class into small-index urns ( Λ < 1 2 ), critical-index urns ( Λ = 1 2 ), and large-index urns ( Λ > 1 2 ), and triangular urns. We obtain central limit theorems for small- and critical-index urns and prove almost-sure convergence for triangular and large-index urns. Moreover, we discuss the moment structure of large-index urns and triangular urns.

Authors:Alessandro De Luca; Gabriele Fici; Luca Q. Zamboni Pages: 27 - 45 Abstract: Publication date: September 2017 Source:Advances in Applied Mathematics, Volume 90 Author(s): Alessandro De Luca, Gabriele Fici, Luca Q. Zamboni A finite word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We are interested in the oc-sequence of a word, which is the binary sequence whose n-th element is 0 if the prefix of length n of the word is open, or 1 if it is closed. We exhibit results showing that this sequence is deeply related to the combinatorial and periodic structure of a word. In the case of Sturmian words, we show that these are uniquely determined (up to renaming letters) by their oc-sequence. Moreover, we prove that the class of finite Sturmian words is a maximal element with this property in the class of binary factorial languages. We then discuss several aspects of Sturmian words that can be expressed through this sequence. Finally, we provide a linear-time algorithm that computes the oc-sequence of a finite word, and a linear-time algorithm that reconstructs a finite Sturmian word from its oc-sequence.

Authors:Pauline Bailet; Simona Settepanella Pages: 46 - 85 Abstract: Publication date: September 2017 Source:Advances in Applied Mathematics, Volume 90 Author(s): Pauline Bailet, Simona Settepanella We study the first homology group H 1 ( F , C ) of the Milnor fiber F of sharp arrangements A ‾ in P R 2 . Our work relies on the minimal complex C ⁎ ( S ( A ) ) of the deconing arrangement A and its boundary map. We describe an algorithm which computes possible eigenvalues of the monodromy operator h 1 of H 1 ( F , C ) . We prove that, if a condition on some intersection points of lines in A is satisfied, then the only possible nontrivial eigenvalues of h 1 are cubic roots of the unity. Moreover we give sufficient conditions for just eigenvalues of order 3 or 4 to appear in cases in which this condition is not satisfied.

Authors:Yan Zhuang Pages: 86 - 144 Abstract: Publication date: September 2017 Source:Advances in Applied Mathematics, Volume 90 Author(s): Yan Zhuang We prove several identities expressing polynomials counting permutations by various descent statistics in terms of Eulerian polynomials, extending results of Stembridge, Petersen, and Brändén. Additionally, we find q-exponential generating functions for q-analogues of these descent statistic polynomials that also keep track of the inversion number or inverse major index. We also present identities relating several of these descent statistic polynomials to refinements of type B Eulerian polynomials and flag descent polynomials by the number of negative letters of a signed permutation. Our methods include permutation enumeration techniques involving noncommutative symmetric functions, the modified Foata–Strehl action, and a group action of Petersen on signed permutations. Notably, the modified Foata–Strehl action yields an analogous relation between Narayana polynomials and the joint distribution of the peak number and descent number over 231-avoiding permutations, which we also interpret in terms of binary trees and Dyck paths.

Authors:Shaked Koplewitz Pages: 145 - 159 Abstract: Publication date: September 2017 Source:Advances in Applied Mathematics, Volume 90 Author(s): Shaked Koplewitz We consider random directed graphs, and calculate the distribution of the cokernels of their laplacian, following the methods used by Wood. As a corollary, we show that the probability that a random digraph is coeulerian is asymptotically upper bounded by a constant around 0.43.

Authors:Alexander Levin Pages: 1 - 17 Abstract: Publication date: August 2017 Source:Advances in Applied Mathematics, Volume 89 Author(s): Alexander Levin We consider Hilbert-type functions associated with difference (not necessarily inversive) field extensions and systems of algebraic difference equations in the case when the translations are assigned some integer weights. We will show that such functions are quasi-polynomials, which can be represented as alternating sums of Ehrhart quasi-polynomials associated with rational conic polytopes. In particular, we obtain generalizations of main theorems on difference dimension polynomials and their invariants to the case of weighted basic difference operators.

Authors:Manjil P. Saikia Pages: 41 - 66 Abstract: Publication date: August 2017 Source:Advances in Applied Mathematics, Volume 89 Author(s): Manjil P. Saikia In this paper we enumerate domino tilings of an Aztec rectangle with arbitrary defects of size one on all boundary sides. This result extends previous work by different authors: Mills–Robbins–Rumsey and Elkies–Kuperberg–Larsen–Propp. We use the method of graphical condensation developed by Kuo and generalized by Ciucu, to prove our results; a common generalization of both Kuo's and Ciucu's result is also presented here.

Authors:Pablo Torres Pages: 67 - 75 Abstract: Publication date: August 2017 Source:Advances in Applied Mathematics, Volume 89 Author(s): Pablo Torres For k , s ≥ 2 , the s-stable Kneser graphs are the graphs with vertex set the k-subsets S of { 1 , … , n } such that the circular distance between any two elements in S is at least s and two vertices are adjacent if and only if the corresponding k-subsets are disjoint. Braun showed that for n ≥ 2 k + 1 the automorphism group of the 2-stable Kneser graphs (Schrijver graphs) is isomorphic to the dihedral group of order 2n. In this paper we generalize this result by proving that for s ≥ 2 and n ≥ s k + 1 the automorphism group of the s-stable Kneser graphs also is isomorphic to the dihedral group of order 2n.

Authors:Gennadiy Averkov; Bernardo González Merino; Ingo Paschke; Matthias Schymura; Stefan Weltge Pages: 76 - 101 Abstract: Publication date: August 2017 Source:Advances in Applied Mathematics, Volume 89 Author(s): Gennadiy Averkov, Bernardo González Merino, Ingo Paschke, Matthias Schymura, Stefan Weltge Let S be a discrete subset of R n and define c ( S , k ) as the smallest number with the property that if a finite family of convex sets has exactly k points of S in common, then at most c ( S , k ) convex sets in this family already have exactly k points of S in common. For S = Z n , this number repeatedly appeared in different contexts as, for instance, optimization and geometry of numbers and, very recently, for general sets S, in the context of Helly and Tverberg theorems in De Loera et al. (2015). In this work, we give a useful description of c ( S , k ) in terms of polytopes with vertices in S. Starting with this description, we answer several fundamental questions about c ( S , k ) . We provide the general upper bound c ( S , k ) ≤ ⌊ ( k + 1 ) / 2 ⌋ ( c ( S , 0 ) − 2 ) + c ( S , 0 ) for every discrete S. For the integer lattice S = Z n , employing techniques from the geometry of numbers, we solve the question on the asymptotic behavior by proving the estimate c ( Z n , k ) = Θ ( k ( n − 1 ) / ( n + 1 ) ) for every fixed n, and we compute the exact values of c ( Z n , k ) for k = 0 , … , 4 .

Authors:Karen T. Kohl Pages: 102 - 124 Abstract: Publication date: August 2017 Source:Advances in Applied Mathematics, Volume 89 Author(s): Karen T. Kohl Ramanujan's Master Theorem and its extension in the method of brackets are a powerful technique for evaluation of many definite integrals, often producing series solutions. In the case that the series are multi-sums, simplification is nontrivial. Recurrence-finding algorithms assist in proving multi-sum identities to verify the correctness of such multi-sum series solutions.

Authors:Persi Diaconis; Angela Hicks Pages: 125 - 155 Abstract: Publication date: August 2017 Source:Advances in Applied Mathematics, Volume 89 Author(s): Persi Diaconis, Angela Hicks We explore the link between combinatorics and probability generated by the question “What does a random parking function look like?” This gives rise to novel probabilistic interpretations of some elegant, known generating functions. It leads to new combinatorics: how many parking functions begin with i? We classify features (e.g., the full descent pattern) of parking functions that have exactly the same distribution among parking functions as among all functions. Finally, we develop the link between parking functions and Brownian excursion theory to give examples where the two ensembles differ.

Authors:A. Hassairi; M.A. Masmoudi; O. Regaig Pages: 184 - 199 Abstract: Publication date: August 2017 Source:Advances in Applied Mathematics, Volume 89 Author(s): A. Hassairi, M.A. Masmoudi, O. Regaig In this paper, we first give some properties based on independence relations between matrix beta random variables of the first kind and of the second kind which are satisfied under a condition on the parameters of the distributions. We then show that with the matrix beta-hypergeometric distribution, the properties established for the beta distribution are satisfied without any condition on the parameters. The results involve many remarkable properties of the zonal polynomials with matrix arguments and the use of random matrix continued fractions. As a particular case, we get the results established for the real beta-hypergeometric distributions by Asci, Letac and Piccioni [1].

Authors:M. Gallet; G. Nawratil; J. Schicho; J.M. Selig Pages: 1 - 25 Abstract: Publication date: July 2017 Source:Advances in Applied Mathematics, Volume 88 Author(s): M. Gallet, G. Nawratil, J. Schicho, J.M. Selig Pods are mechanical devices constituted of two rigid bodies, the base and the platform, connected by a number of other rigid bodies, called legs, that are anchored via spherical joints. It is possible to prove that the maximal number of legs of a mobile pod, when finite, is 20. In 1904, Borel designed a technique to construct examples of such 20-pods, but could not constrain the legs to have base and platform points with real coordinates. We show that Borel's construction yields all mobile 20-pods, and that it is possible to construct examples where all coordinates are real.

Authors:Matthias Reitzner; Matthias Schulte; Christoph Thäle Pages: 26 - 61 Abstract: Publication date: July 2017 Source:Advances in Applied Mathematics, Volume 88 Author(s): Matthias Reitzner, Matthias Schulte, Christoph Thäle For a given homogeneous Poisson point process in R d two points are connected by an edge if their distance is bounded by a prescribed distance parameter. The behavior of the resulting random graph, the Gilbert graph or random geometric graph, is investigated as the intensity of the Poisson point process is increased and the distance parameter goes to zero. The asymptotic expectation and covariance structure of a class of length-power functionals are computed. Distributional limit theorems are derived that have a Gaussian, a stable or a compound Poisson limiting distribution. Finally, concentration inequalities are provided using the convex distance.

Authors:Jean Ponce; Bernd Sturmfels; Mathew Trager Pages: 62 - 91 Abstract: Publication date: July 2017 Source:Advances in Applied Mathematics, Volume 88 Author(s): Jean Ponce, Bernd Sturmfels, Mathew Trager We present a new framework for multi-view geometry in computer vision. A camera is a mapping between P 3 and a line congruence. This model, which ignores image planes and measurements, is a natural abstraction of traditional pinhole cameras. It includes two-slit cameras, pushbroom cameras, catadioptric cameras, and many more. We study the concurrent lines variety, which consists of n-tuples of lines in P 3 that intersect at a point. Combining its equations with those of various congruences, we derive constraints for corresponding images in multiple views. We also study photographic cameras which use image measurements and are modeled as rational maps from P 3 to P 2 or P 1 × P 1 .

Authors:Matthieu Josuat-Vergès; Frédéric Menous; Jean-Christophe Novelli; Jean-Yves Thibon Pages: 92 - 119 Abstract: Publication date: July 2017 Source:Advances in Applied Mathematics, Volume 88 Author(s): Matthieu Josuat-Vergès, Frédéric Menous, Jean-Christophe Novelli, Jean-Yves Thibon The functional equation defining the free cumulants in free probability is lifted successively to the noncommutative Faà di Bruno algebra, and then to the group of a free operad over Schröder trees. This leads to new combinatorial expressions, which remain valid for operator-valued free probability. Specializations of these expressions give back Speicher's formula in terms of noncrossing partitions, and its interpretation in terms of characters due to Ebrahimi-Fard and Patras.

Authors:Lax Chan; Uwe Grimm Pages: 16 - 23 Abstract: Publication date: June 2017 Source:Advances in Applied Mathematics, Volume 87 Author(s): Lax Chan, Uwe Grimm We show that a recently proposed Rudin–Shapiro-like sequence, with balanced weights, has purely singular continuous diffraction spectrum, in contrast to the well-known Rudin–Shapiro sequence whose diffraction is absolutely continuous. This answers a question that had been raised about this new sequence.

Authors:Yue Zhou; Jia Lu; Houshan Fu Pages: 24 - 42 Abstract: Publication date: June 2017 Source:Advances in Applied Mathematics, Volume 87 Author(s): Yue Zhou, Jia Lu, Houshan Fu The Morris constant term identity is known to be equivalent to the famous Selberg integral. In this paper, we regard Morris type constant terms as polynomials of a certain parameter. Thus, we can take the leading coefficients and obtain new identities. These identities happen to be crucial in finding lower bounds for cardinalities of some restricted sumsets, and in calculating the volume of a Tesler polytope.

Authors:Yanping Zhou; Binwu He Pages: 43 - 57 Abstract: Publication date: June 2017 Source:Advances in Applied Mathematics, Volume 87 Author(s): Yanping Zhou, Binwu He To study the well-known Schneider's projection problem, Lutwak, Yang and Zhang introduced a U-functional for polytopes, and posed two conjectures for this U-functional. In this paper, an affirmative answer for the second conjecture is given. As a by-product to prove our main theorem, a new affine inequality is established for the centered cone volume measures.

Authors:Károly J. Böröczky; Hai T. Trinh Pages: 58 - 81 Abstract: Publication date: June 2017 Source:Advances in Applied Mathematics, Volume 87 Author(s): Károly J. Böröczky, Hai T. Trinh The planar L p Minkowski problem is solved for p ∈ ( 0 , 1 ) .

Authors:Mariya Bessonov; Richard Durrett Pages: 82 - 107 Abstract: Publication date: June 2017 Source:Advances in Applied Mathematics, Volume 87 Author(s): Mariya Bessonov, Richard Durrett We study a two dimensional version of Neuhauser's long range sexual reproduction model and prove results that give bounds on the critical values λ f for the process to survive from a finite set and λ e for the existence of a nontrivial stationary distribution. Our first result comes from a standard block construction, while the second involves a comparison with the “generic population model” of Bramson and Gray (1991) [3]. An interesting new feature of our work is the suggestion that, as in the one dimensional contact process, edge speeds characterize critical values. We are able to prove the following for our quadratic contact process when the range is large but suspect they are true for two dimensional finite range attractive particle systems that are symmetric with respect to reflection in each axis. There is a speed c ( θ ) for the expansion of the process in each direction. If c ( θ ) > 0 in all directions, then λ > λ f , while if at least one speed is positive, then λ > λ e . It is a challenging open problem to show that if some speed is negative, then the system dies out from any finite set.

Authors:Wenchang Chu Pages: 108 - 127 Abstract: Publication date: June 2017 Source:Advances in Applied Mathematics, Volume 87 Author(s): Wenchang Chu Two statistics with respect to “upper-corners” and “lower-corners” are introduced for lattice paths. The corresponding refined generating functions are shown to be closely related to the q-ballot polynomials that extend the well-known Narayana polynomials and Catalan numbers.

Authors:Ron M. Adin; Christos A. Athanasiadis; Sergi Elizalde; Yuval Roichman Pages: 128 - 169 Abstract: Publication date: June 2017 Source:Advances in Applied Mathematics, Volume 87 Author(s): Ron M. Adin, Christos A. Athanasiadis, Sergi Elizalde, Yuval Roichman A general setting to study a certain type of formulas, expressing characters of the symmetric group S n explicitly in terms of descent sets of combinatorial objects, has been developed by two of the authors. This theory is further investigated in this paper and extended to the hyperoctahedral group B n . Key ingredients are a new formula for the irreducible characters of B n , the signed quasisymmetric functions introduced by Poirier, and a new family of matrices of Walsh–Hadamard type. Applications include formulas for natural B n -actions on coinvariant and exterior algebras and on the top homology of a certain poset in terms of the combinatorics of various classes of signed permutations, as well as a B n -analogue of an equidistribution theorem of Désarménien and Wachs.

Authors:Carlos A. Alfaro; Hugo Corrales; Carlos E. Valencia Pages: 99 - 131 Abstract: Publication date: May 2017 Source:Advances in Applied Mathematics, Volume 86 Author(s): Carlos A. Alfaro, Hugo Corrales, Carlos E. Valencia This paper studies critical ideals of graphs with twin vertices, which are vertices with the same neighbors. A pair of such vertices are called replicated if they are adjacent, and duplicated, otherwise. Critical ideals of graphs having twin vertices have good properties and show regular patterns. Given a graph G = ( V , E ) and d ∈ Z V , let G d be the graph obtained from G by duplicating d v times or replicating − d v times the vertex v when d v > 0 or d v < 0 , respectively. Moreover, given δ ∈ { 0 , 1 , − 1 } V , let T δ ( G ) = { G d : d ∈ Z V such that d v = 0 T δ ( G ) = { G d : if and only if δ v = 0 and d v δ v > 0 otherwise } be the set of graphs sharing the same pattern of duplication or replication of vertices. More than one half of the critical ideals of a graph in T δ ( G ) can be determined by the critical ideals of G. The algebraic co-rank of a graph G is the maximum integer i such that the i-th critical ideal of G is trivial. We show that the algebraic co-rank of any graph in T δ ( G ) is equal to the algebraic co-rank of G δ . Moreover, the algebraic co-rank can be determined by a simple evaluation of the critical ideals of G. For a large enough d ∈ Z V ( G ) , we show that the critical ideals of G d have similar behavior to the critical ideals of the disjoint union of G and some set { K n v } { ... PubDate: 2017-02-04T11:40:53Z DOI: 10.1016/j.aam.2017.01.005 Issue No:Vol. 86 (2017)

Authors:B.G. Pittel; D.J. Poole Pages: 132 - 174 Abstract: Publication date: May 2017 Source:Advances in Applied Mathematics, Volume 86 Author(s): B.G. Pittel, D.J. Poole The ( k 1 , k 2 ) -core of a digraph is the largest sub-digraph with minimum in-degree and minimum out-degree at least k 1 and k 2 respectively. For max { k 1 , k 2 } ≥ 2 , we establish existence of the threshold edge-density c ⁎ = c ⁎ ( k 1 , k 2 ) , such that the random digraph D ( n , m ) , on the vertex set [ n ] with m edges, asymptotically almost surely has a giant ( k 1 , k 2 ) -core if m / n > c ⁎ , and has no ( k 1 , k 2 ) -core if m / n < c ⁎ . Specifically, denoting P ( Poisson ( z ) ≥ k ) by p k ( z ) , we prove that c ⁎ = min z 1 , z 2 max { z 1 p k 1 ( z 1 ) p k 2 − 1 ( z 2 ) ; z 2 p k 1 − 1 ( z 1 ) p k 2 ( z 2 ) } .

Authors:Denghui Abstract: Publication date: August 2017 Source:Advances in Applied Mathematics, Volume 89 Author(s): Denghui Wu In this paper we extend the concepts of L p -mixed volumes and L p -surface area measures to L p -mixed μ-measures and L p -surface μ-area measures, respectively, for a measure μ on R n . We give an integral representation and discuss some inequalities for the L p -surface μ-area measure. The L p -Minkowski and L p -Brunn–Minkowski inequalities for measures are proved. Moreover, we also show the existence theorem of the related L p -Minkowski problem for measures.

Authors:A. Goodall; M. Hermann; T. Kotek; J.A. Makowsky; S.D. Noble Abstract: Publication date: Available online 14 April 2017 Source:Advances in Applied Mathematics 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:Songjun Abstract: Publication date: August 2017 Source:Advances in Applied Mathematics, Volume 89 Author(s): Songjun Lv We extend the ( q , λ ) -Fisher information to a much broader setting, where the power function x ↦ x q in the ( q , λ ) -Fisher information is replaced by an arbitrarily chosen convex function. We describe qualitative research, which is undertaken within the general framework, on the newly-introduced generalized Fisher information. In particular, we derive the characterization of general Fisher information matrix for a random vector in R n .

Authors:Yanni Chen Pages: 1 - 15 Abstract: Publication date: June 2017 Source:Advances in Applied Mathematics, Volume 87 Author(s): Yanni Chen The classical Beurling–Helson–Lowdenslager theorem characterizes the shift-invariant subspaces of the Hardy space H 2 and of the Lebesgue space L 2 . In this paper, which is self-contained, we define a very general class of norms α and define spaces H α and L α . We then extend the Beurling–Helson–Lowdenslager invariant subspace theorem. The idea of the proof is new and quite simple; most of the details involve extending basic well-known ‖ ⋅ ‖ p -results for our more general norms.

Authors:Joanna N. Chen; Robin D.P. Zhou Pages: 1 - 18 Abstract: Publication date: May 2017 Source:Advances in Applied Mathematics, Volume 86 Author(s): Joanna N. Chen, Robin D.P. Zhou Permutation tableaux were introduced by Steingrímsson and Williams. Corteel and Kim defined the sign of a permutation tableau in terms of the number of unrestricted columns. The sign-imbalance of permutation tableaux of length n is the sum of signs over permutation tableaux of length n. They have obtained a formula for the sign-imbalance of permutation tableaux of length n by using generating functions and asked for a combinatorial proof. Moreover, they raised the question of finding a sign-imbalance formula for type B permutation tableaux introduced by Lam and Williams. We define a statistic wm ‾ over permutations and show that the number of unrestricted columns over permutation tableaux of length n is equally distributed with wm ‾ over permutations of length n. This leads to a combinatorial interpretation of the formula of Corteel and Kim. For type B permutation tableaux, we define the sign of a type B permutation tableau in term of the number of certain rows and columns. On the other hand, we construct a bijection between the type B permutation tableaux of length n and symmetric permutations of length 2n and we show that the statistic wm ‾ over symmetric permutations of length 2n is equally distributed with the number of certain rows and columns over type B permutation tableaux of length n. Based on this correspondence and an involution on symmetric permutations of length 2n, we obtain a sign-imbalance formula for type B permutation tableaux.

Authors:Richard A. Brualdi; Geir Dahl Pages: 19 - 49 Abstract: Publication date: May 2017 Source:Advances in Applied Mathematics, Volume 86 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, and where each row and column sum is 1. We study the convex cone generated by ASMs of order n, called the ASM cone, as well as several related cones and polytopes. Some decomposition results are shown, and we find a minimal Hilbert basis of the ASM cone. The notion of ( ± 1 ) -doubly stochastic matrices and a generalization of ASMs are introduced and various properties are shown. For instance, we give a new short proof of the linear characterization of the ASM polytope, in fact for a more general polytope. Finally, we investigate faces of the ASM polytope, in particular edges associated with permutation matrices.

Authors:Yue Cai; Margaret A. Readdy Pages: 50 - 80 Abstract: Publication date: May 2017 Source:Advances in Applied Mathematics, Volume 86 Author(s): Yue Cai, Margaret A. Readdy We show the classical q-Stirling numbers of the second kind can be expressed compactly as a pair of statistics on a subset of restricted growth words. The resulting expressions are polynomials in q and 1 + q . We extend this enumerative result via a decomposition of a new poset Π ( n , k ) which we call the Stirling poset of the second kind. Its rank generating function is the q-Stirling number S q [ n , k ] . The Stirling poset of the second kind supports an algebraic complex and a basis for integer homology is determined. A parallel enumerative, poset theoretic and homological study for the q-Stirling numbers of the first kind is done. Letting t = 1 + q we give a bijective argument showing the ( q , t ) -Stirling numbers of the first and second kinds are orthogonal.

Authors:Zhi Chen; Hao Pan Pages: 81 - 98 Abstract: Publication date: May 2017 Source:Advances in Applied Mathematics, Volume 86 Author(s): Zhi Chen, Hao Pan In this paper, we investigate the weighted Catalan, Motzkin and Schröder numbers together with the corresponding weighted paths. The relation between these numbers is illustrated by three equations, which also lead to some known and new interesting identities. To show these three equations, we provide combinatorial proofs. One byproduct is to find a bijection between two sets of Catalan paths: one consisting of those with k valleys, and the other consisting of k N steps in even positions.

Authors:A.A. Panferov Pages: 1 - 11 Abstract: Publication date: April 2017 Source:Advances in Applied Mathematics, Volume 85 Author(s): A.A. Panferov Consider the differential field K = Q ‾ ( x ) with derivation d / d x . Let some unknowns (components of the unknown vector y = ( y 1 , … , y n ) T ) of a linear homogeneous differential system S over K be selected. Denote this set of selected unknowns by s. An unselected unknown y j of the system S is called satellite for s if the minimal subfield of a Picard–Vessiot extension over K for S, that contains all selected components of all solutions to S, also contains y j component of any solution. We present an algorithm for constructing the set of satellite unknowns for a given linear homogeneous differential system with selected unknowns.

Authors:Carolyn Chun; Dillon Mayhew; James Oxley Pages: 12 - 30 Abstract: Publication date: April 2017 Source:Advances in Applied Mathematics, Volume 85 Author(s): Carolyn Chun, Dillon Mayhew, James Oxley Our splitter theorem studies pairs of the form ( M , N ) , where M and N are internally 4-connected binary matroids, M has a proper N-minor, and if M ′ is an internally 4-connected matroid such that M has a proper M ′ -minor and M ′ has an N-minor, then E ( M ) − E ( M ′ ) > 3 . The analysis in the splitter theorem requires the constraint E ( M ) ≥ 16 . In this article, we complement that analysis by describing all such pairs for which E ( M ) ≤ 15 .