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:Jason P. Smith Pages: 98 - 114 Abstract: Publication date: October 2017 Source:Advances in Applied Mathematics, Volume 91 Author(s): Jason P. Smith We present a two term formula for the Möbius function of intervals in the poset of all permutations, ordered by pattern containment. The first term in this formula is the number of so called normal occurrences of one permutation in another. Our definition of normal occurrences is similar to those that have appeared in several variations in the literature on the Möbius function of this and other posets, but simpler than most of them. The second term in the formula is complicated, but we conjecture that it equals zero for a significant proportion of intervals. We present some cases where the second term vanishes and others where it is nonzero. Computing the Möbius function recursively from its definition has exponential complexity, whereas the computation of the first term in our formula is polynomial and the exponential part is isolated to the second term, which seems to often vanish. We also present a result on the Möbius function of posets connected by a poset fibration.

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:Daniele D'Angeli; Emanuele Rodaro; Jan Philipp Wächter Pages: 160 - 187 Abstract: Publication date: September 2017 Source:Advances in Applied Mathematics, Volume 90 Author(s): Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are generated by partial, yet invertible automata. We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSpace-complete word problem. We also show that there is an automaton group for which the word problem with a single rational constraint is PSpace-complete. Additionally, we provide simpler constructions for the uniform word problems of these classes. For the uniform word problem for automaton groups (without rational constraints), we show NL-hardness. Finally, we investigate a question asked by Cain about a better upper bound for the length of a word on which two distinct elements of an automaton semigroup must act differently. A detailed listing of the contributions of this paper can be found at the end of this paper.

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

Abstract: Publication date: January 2018 Source:Advances in Applied Mathematics, Volume 92 Author(s): Alice L.L. Gao, Matthew H.Y. Xie, Arthur L.B. Yang In the study of determinant formulas for Schur functions, Hamel and Goulden introduced a class of Giambelli-type matrices with respect to outside decompositions of partition diagrams, which unify the Jacobi–Trudi matrices, the Giambelli matrices and the Lascoux–Pragacz matrices. Stanley determined the Smith normal form of a specialized Jacobi–Trudi matrix. Motivated by Stanley's work, we obtain the Smith normal form of a specialized Giambelli matrix and a specialized Lascoux–Pragacz matrix. Furthermore, we show that, for a given partition, the Smith normal form of any specialized Giambelli-type matrix can be obtained from that of the corresponding specialization of the classical Giambelli matrix by a sequence of stabilization operations.

Abstract: Publication date: January 2018 Source:Advances in Applied Mathematics, Volume 92 Author(s): Stephen DeSalvo We present a probabilistic divide-and-conquer (PDC) method for exact sampling of conditional distributions of the form L ( X X ∈ E ) , where X is a random variable on X , a complete, separable metric space, and event E with P ( E ) ≥ 0 is assumed to have sufficient regularity such that the conditional distribution exists and is unique up to almost sure equivalence. The PDC approach is to define a decomposition of X via sets A and B such that X = A × B , and sample from each separately. The deterministic second half approach is to select the sets A and B such that for each element a ∈ A , there is only one element b a ∈ B for which ( a , b a ) ∈ E . We show how this simple approach provides non-trivial improvements to several conventional random sampling algorithms in combinatorics, and we demonstrate its versatility with applications to sampling from sufficiently regular conditional distributions.

Abstract: Publication date: January 2018 Source:Advances in Applied Mathematics, Volume 92 Author(s): Larry X.W. Wang, Gary Y.B. Xie, Andy Q. Zhang Let p ( n ) denote the integer partition function. Good conjectured that Δ r p ( n ) alternates in sign up to a certain value n = n ( r ) , and then it stays positive. Gupta showed that for any given r and sufficiently large n, Δ r p ( n ) > 0 . Odlyzko proved this conjecture and gave an asymptotic formula for n ( r ) . Then, Almkvist, Knessel and Keller gave many contributions for the exact value of n ( r ) . For the finite difference of log p ( n ) , DeSalvo and Pak proved that 0 ≤ − △ 2 log p ( n − 1 ) ≤ log ( 1 + 1 n ) and conjectured a sharper upper bound for − △ 2 log p ( n ) . Chen, Wang and Xie proved this conjecture and showed the positivity of ( − 1 ) r − 1 △ r log p ( n ) , and further gave an upper bound for ( − 1 ) r − 1 △ r log p ( n ) . As for the overpartition function p ‾ ( n ) , Engel recently proved that p ‾ ( n ) is log-concave for n ≥ 2 , that is, − △ 2 log p ‾ ( n ) ≥ 0 for n ≥ 2 . Motivated by these results, in this paper we will prove the positivity of finite differences of the overpartition function and give an upper bound for △ r p ‾ ( n ) . Then we show that for any given r ≥ 1 , there exists a positive number n ( r ) such that ( − 1 ) r − 1 △ r log p ‾ ( n ) PubDate: 2017-07-23T04:06:40Z

Abstract: Publication date: October 2017 Source:Advances in Applied Mathematics, Volume 91 Author(s): Servet Martínez We study the discrete-time evolution of a recombination transformation in population genetics. The transformation acts on a product probability space, and its evolution can be described by a Markov chain on a set of partitions that converges to the finest partition. We describe the geometric decay rate to this limit and the quasi-stationary behavior of the Markov chain when conditioned on the event that the chain does not hit the limit.

Abstract: Publication date: October 2017 Source:Advances in Applied Mathematics, Volume 91 Author(s): Jean B. Lasserre We provide a numerical scheme to approximate as closely as desired the Gaussian or exponential measure μ ( Ω ) of (not necessarily compact) basic semi-algebraic sets Ω ⊂ R n . We obtain two monotone (non-increasing and non-decreasing) sequences of upper and lower bounds ( ω ‾ d ) , ( ω _ d ) , d ∈ N , each converging to μ ( Ω ) as d → ∞ . For each d, computing ω ‾ d or ω _ d reduces to solving a semidefinite program whose size increases with d. Some preliminary (small dimension) computational experiments are encouraging and illustrate the potential of the method. The method also works for any measure whose moments are known and which satisfies Carleman's condition.

Abstract: Publication date: Available online 22 July 2017 Source:Advances in Applied Mathematics Author(s): Robert Brijder Multimatroids generalize matroids, delta-matroids, and isotropic systems, and transition polynomials of multimatroids subsume various polynomials for these latter combinatorial structures, such as the interlace polynomial and the Tutte–Martin polynomial. We prove evaluations of the Tutte–Martin polynomial of isotropic systems from Bouchet directly and more efficiently in the context of transition polynomials of multimatroids. Moreover, we generalize some related evaluations of the transition polynomial of 4-regular graphs from Jaeger to multimatroids. These evaluations are obtained in a uniform and matroid-theoretic way. We also translate the evaluations in terms of the interlace polynomial of graphs. Finally, we give an excluded-minor theorem for the class of binary tight 3-matroids (a subclass of multimatroids) based on the excluded-minor theorem for the class of binary delta-matroids from Bouchet.

Authors:Spencer Backman Abstract: Publication date: Available online 28 June 2017 Source:Advances in Applied Mathematics Author(s): Spencer Backman Gessel and Sagan investigated the Tutte polynomial, T G ( x , y ) using depth-first search, and applied their techniques to show that the number of acyclic partial orientations of a graph is 2 m − n + 1 T G ( 3 , 1 / 2 ) . We provide a short deletion-contraction proof of this result and demonstrate that dually, the number of strongly connected partial orientations is 2 n − 1 T G ( 1 / 2 , 3 ) . We then prove that the number of partial orientations modulo cycle reversals is 2 g T G ( 3 , 1 ) and the number of partial orientations modulo cut reversals is 2 n − 1 T G ( 1 , 3 ) . To prove these results, we introduce cut and cycle-minimal partial orientations which provide distinguished representatives for partial orientations modulo cut and cycle reversals, extending known representatives for full orientations introduced by Greene and Zaslavksy. We then introduce distinguished partial orientations representing a given indegree sequence. We utilize these partial orientations to derive the Ehrhart polynomial of the win vector polytope, and give a combinatorial interpretation of its volume, thus answering a question of Bartels, Mount, and Welsh. We conclude with edge chromatic generalizations of the quantities presented, which allow for a new interpretation of the reliability polynomial for all probabilities p with 0 < p < 1 / 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: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.