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: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: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: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: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:Joseph E. Bonin; Joseph P.S. Kung Abstract: Publication date: Available online 22 March 2017 Source:Advances in Applied Mathematics Author(s): Joseph E. Bonin, Joseph P.S. Kung The catenary data of a matroid M of rank r on n elements is the vector ( ν ( M ; a 0 , a 1 , … , a r ) ) , indexed by compositions ( a 0 , a 1 , … , a r ) , where a 0 ≥ 0 , a i > 0 for i ≥ 1 , and a 0 + a 1 + ⋯ + a r = n , with the coordinate ν ( M ; a 0 , a 1 , … , a r ) equal to the number of maximal chains or flags ( X 0 , X 1 , … , X r ) of flats or closed sets such that X i has rank i, X 0 = a 0 , and X i − X i − 1 = a i . We show that the catenary data of M contains the same information about M as its G -invariant, which was defined by H. Derksen (2009) [9]. The Tutte polynomial is a specialization of the G -invariant. We show that many known results for the Tutte polynomial have analogs for the G -invariant. In particular, we show that for many matroid constructions, the G -invariant of the construction can be calculated from the G -invariants of the constituents and that the G -invariant of a matroid can be calculated from its size, the isomorphism class of the lattice of cyclic flats with lattice elements labeled by the rank and size of the underlying set. We also show that the number of flats and cyclic flats of a given rank and size can be derived from the G -invariant, that the G -invariant of M is reconstructible from the deck of G -invariants of restrictions of M to its copoints, and that, apart from free extensions and coextensions, one can detect whether a matroid is a free product from its G -invariant.

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 .

Authors:Caitlin Lienkaemper; Anne Shiu; Zev Woodstock Pages: 31 - 59 Abstract: Publication date: April 2017 Source:Advances in Applied Mathematics, Volume 85 Author(s): Caitlin Lienkaemper, Anne Shiu, Zev Woodstock How does the brain encode spatial structure? One way is through hippocampal neurons called place cells, which become associated to convex regions of space known as their receptive fields: each place cell fires at a high rate precisely when the animal is in the receptive field. The firing patterns of multiple place cells form what is known as a convex neural code. How can we tell when a neural code is convex? To address this question, Giusti and Itskov identified a local obstruction, defined via the topology of a code's simplicial complex, and proved that convex neural codes have no local obstructions. Curto et al. proved the converse for all neural codes on at most four neurons. Via a counterexample on five neurons, we show that this converse is false in general. Additionally, we classify all codes on five neurons with no local obstructions. This classification is enabled by our enumeration of connected simplicial complexes on 5 vertices up to isomorphism. Finally, we examine how local obstructions are related to maximal codewords (maximal sets of neurons that co-fire). Curto et al. proved that a code has no local obstructions if and only if it contains certain “mandatory” intersections of maximal codewords. We give a new criterion for an intersection of maximal codewords to be non-mandatory, and prove that it classifies all such non-mandatory codewords for codes on up to five neurons.

Authors:Eric Rowland; Reem Yassawi Pages: 60 - 83 Abstract: Publication date: April 2017 Source:Advances in Applied Mathematics, Volume 85 Author(s): Eric Rowland, Reem Yassawi Many sequences of p-adic integers project modulo p α to p-automatic sequences for every α ≥ 0 . Examples include algebraic sequences of integers, which satisfy this property for every prime p, and some cocycle sequences, which we show satisfy this property for a fixed p. For such a sequence, we construct a profinite automaton that projects modulo p α to the automaton generating the projected sequence. In general, the profinite automaton has infinitely many states. Additionally, we consider the closure of the orbit, under the shift map, of the p-adic integer sequence, defining a shift dynamical system. We describe how this shift is a letter-to-letter coding of a shift generated by a constant-length substitution defined on an uncountable alphabet, and we establish some dynamical properties of these shifts.

Authors:Jennifer Biermann; Augustine O'Keefe; Adam Van Tuyl Pages: 84 - 102 Abstract: Publication date: April 2017 Source:Advances in Applied Mathematics, Volume 85 Author(s): Jennifer Biermann, Augustine O'Keefe, Adam Van Tuyl Let G be a finite simple graph. We give a lower bound for the Castelnuovo–Mumford regularity of the toric ideal I G associated to G in terms of the sizes and number of induced complete bipartite graphs in G. When G is a chordal bipartite graph, we find an upper bound for the regularity of I G in terms of the size of the bipartition of G. We also give a new proof for the graded Betti numbers of the toric ideal associated to the complete bipartite graph K 2 , n .

Authors:Michael J. Schlosser; Meesue Yoo Pages: 8 - 33 Abstract: Publication date: March 2017 Source:Advances in Applied Mathematics, Volume 84 Author(s): Michael J. Schlosser, Meesue Yoo We construct elliptic extensions of the alpha-parameter rook model introduced by Goldman and Haglund and of the rook model for matchings of Haglund and Remmel. In particular, we extend the product formulas of these models to the elliptic setting. By specializing the parameter α in our elliptic extension of the alpha-parameter model and the shape of the Ferrers board in different ways, we obtain elliptic analogues of the Stirling numbers of the first kind and of the Abel polynomials, and an a , q -analogue of the matching numbers. We further generalize the rook theory model for matchings by introducing l-lazy graphs which correspond to l-shifted boards, where l is a finite vector of positive integers. The corresponding elliptic product formula generalizes Haglund and Remmel's product formula for matchings already in the non-elliptic basic case.

Authors:Steven Kelk; Georgios Stamoulis Pages: 34 - 46 Abstract: Publication date: March 2017 Source:Advances in Applied Mathematics, Volume 84 Author(s): Steven Kelk, Georgios Stamoulis Phylogenetic trees are used to model evolution: leaves are labelled to represent contemporary species (“taxa”) and interior vertices represent extinct ancestors. Informally, convex characters are measurements on the contemporary species in which the subset of species (both contemporary and extinct) that share a given state, forms a connected subtree. Given an unrooted, binary phylogenetic tree T on a set of n ≥ 2 taxa, a closed (but fairly opaque) expression for the number of convex characters on T has been known since 1992, and this is independent of the exact topology of T . In this note we prove that this number is actually equal to the ( 2 n − 1 ) th Fibonacci number. Next, we define g k ( T ) to be the number of convex characters on T in which each state appears on at least k taxa. We show that, somewhat curiously, g 2 ( T ) is also independent of the topology of T , and is equal to the ( n − 1 ) th Fibonacci number. As we demonstrate, this topological neutrality subsequently breaks down for k ≥ 3 . However, we show that for each fixed k ≥ 1 , g k ( T ) can be computed in O ( n ) time and the set of characters thus counted can be efficiently listed and sampled. We use these insights to give a simple but effective exact algorithm for the NP-hard maximum parsimony distance problem that runs in time Θ ( ϕ n ⋅ n 2 ) , where ϕ ≈ 1.618 . . . is the golden ratio, and an exact algorithm which computes the tree bisection and reconnection distance (equivalently, a maximum agreement forest) in time Θ ( ϕ 2 n ⋅ poly ( n ) ) , where ϕ 2 ≈ 2.619 .

Authors:Michał Adamaszek; Henry Adams; Francis Motta Pages: 1 - 23 Abstract: Publication date: February 2017 Source:Advances in Applied Mathematics, Volume 83 Author(s): Michał Adamaszek, Henry Adams, Francis Motta For X a finite subset of the circle and for 0 < r ≤ 1 fixed, consider the function f r : X → X which maps each point to the clockwise furthest element of X within angular distance less than 2 π r . We study the discrete dynamical system on X generated by f r , and especially its expected behavior when X is a large random set. We show that, as X → ∞ , the expected fraction of periodic points of f r tends to 0 if r is irrational and to 1 q if r = p q is rational with p and q coprime. These results are obtained via more refined statistics of f r which we compute explicitly in terms of (generalized) Catalan numbers. The motivation for studying f r comes from Vietoris–Rips complexes, a geometric construction used in computational topology. Our results determine how much one can expect to simplify the Vietoris–Rips complex of a random sample of the circle by removing dominated vertices.

Authors:Teodor Banica; Ion Nechita Pages: 24 - 46 Abstract: Publication date: February 2017 Source:Advances in Applied Mathematics, Volume 83 Author(s): Teodor Banica, Ion Nechita We study the matrix models π : C ( S N + ) → M N ( C ( X ) ) which are flat, in the sense that the standard generators of C ( S N + ) are mapped to rank 1 projections. Our first result is a generalization of the Pauli matrix construction at N = 4 , using finite groups and 2-cocycles. Our second result is the construction of a universal representation of C ( S N + ) , inspired from the Sinkhorn algorithm, that we conjecture to be inner faithful.

Authors:Benoit Collins; Pierre Yves Gaudreau Lamarre Pages: 47 - 80 Abstract: Publication date: February 2017 Source:Advances in Applied Mathematics, Volume 83 Author(s): Benoit Collins, Pierre Yves Gaudreau Lamarre In this paper, we consider the following question and variants thereof: given D : = ( a 1 ; i ⊗ ⋯ ⊗ a K ; i : i ∈ I ) , a collection of elementary tensor non-commutative random variables in the tensor product of probability spaces ( A 1 ⊗ ⋯ ⊗ A K , φ 1 ⊗ ⋯ ⊗ φ K ) , when is D ⁎-free? (See Section 1.2 for a precise formulation of this problem.) Settling whether or not freeness occurs in tensor products is a recurring problem in operator algebras, and the following two examples provide a natural motivation for the above question: (A) If ( a 1 ; i : i ∈ I ) is a ⁎-free family of Haar unitary variables and a k , i are arbitrary unitary variables for k ≥ 2 , then the ⁎-freeness persists at the level of the tensor product D. (B) A converse of (A) holds true if all variables a k ; i are group-like elements (see Corollary 1.7 of Proposition 1.6). It is therefore natural to seek to understand the extent to which such simple characterizations hold true in more general cases. While our results fall short of a complete characterization, we make notable steps toward identifying necessary and sufficient conditions for the freeness of D. For example, we show that under evident assumptions, if more than one family ( a k , i : i ∈ I ) contains non-unitary variables, then the tensor family fails to be ⁎-free (see Theorem 1.8 (1)).

Authors:Andrew Elvey Price; Anthony J. Guttmann Pages: 81 - 96 Abstract: Publication date: February 2017 Source:Advances in Applied Mathematics, Volume 83 Author(s): Andrew Elvey Price, Anthony J. Guttmann We address the problem of the number of permutations that can be sorted by two stacks in series. We do this by first counting all such permutations of length less than 20 exactly, then using a numerical technique to obtain nineteen further coefficients approximately. Analysing these coefficients by a variety of methods we conclude that the OGF behaves as S ( z ) ∼ A ( 1 − μ ⋅ z ) γ , where μ = 12.45 ± 0.15 , γ = 1.5 ± 0.3 , and A ≈ 0.02 .

Authors:Yining Abstract: Publication date: March 2017 Source:Advances in Applied Mathematics, Volume 84 Author(s): Yining Hu In this article, we prove that for a completely multiplicative function f from N ⁎ to a field K such that the set { p f ( p ) ≠ 1 K and p is prime } is finite, the asymptotic subword complexity of f is Θ ( n t ) , where t is the number of primes p that f ( p ) ≠ 0 K , 1 K . This proves in particular that sequences like ( ( − 1 ) v 2 ( n ) + v 3 ( n ) ) n are not k-automatic for k ≥ 2 .

Authors:Jian Cao Abstract: Publication date: March 2017 Source:Advances in Applied Mathematics, Volume 84 Author(s): Jian Cao In this paper, we show how to prove identities and evaluate integrals by expanding functions in terms of products of the q-hypergeometric polynomials by homogeneous q-partial difference equations, we also generalize some results of Liu (2015) [34] and Cao (2016) [14]. In addition, we generalize multilinear and multiple generating functions for the q-hypergeometric polynomials as applications. Moreover, we deduce some recurring formulas for Ramanujan's integrals, Askey–Roy integrals, Andrews–Askey integrals and moment integrals by the method of homogeneous q-partial difference equations. Finally, we build the relation of Ismail–Zhang type generating functions for the q-hypergeometric polynomials by the method of Ismail and Zhang (2016) [26].

Authors:Anthony Zaleski Abstract: Publication date: March 2017 Source:Advances in Applied Mathematics, Volume 84 Author(s): Anthony Zaleski For fixed s, the size of an ( s , s + 1 ) -core partition with distinct parts can be seen as a random variable X s . Using computer-assisted methods, we derive formulas for the expectation, variance, and higher moments of X s in terms of s. Our results give good evidence that X s is asymptotically normal.