Abstract: Publication date: October 2018Source: Advances in Applied Mathematics, Volume 101Author(s): Sinan G. Aksoy, Fan Chung, Michael Tait, Josh Tobin We show the minimum spectral gap of the normalized Laplacian over all simple, connected graphs on n vertices is (1+o(1))54n3. This minimum is achieved asymptotically by a double kite graph. Consequently, this leads to sharp upper bounds for the maximum relaxation time of a random walk, settling a conjecture of Aldous and Fill. We also improve an eigenvalue–diameter inequality by giving a new lower bound for the spectral gap of the normalized Laplacian. This eigenvalue lower bound is asymptotically best possible.

Abstract: Publication date: September 2018Source: Advances in Applied Mathematics, Volume 100Author(s): Amy M. Fu This paper is concerned with the joint distribution of the number of exterior peaks and the number of proper double descents over permutations on [n]={1,2,…,n}. The notion of exterior peaks of a permutation was introduced by Aguiar, Bergeron and Nyman in their study of the peak algebra. Gessel obtained the generating function of the number of permutations on [n] with a given number of exterior peaks. On the other hand, by establishing differential equations, Elizalde and Noy derived the generating function for the number of permutations on [n] with a given number of proper double descents. Barry and Basset deduced the generating function of the number of permutations on [n] with no proper double descents. We find a context-free grammar that can be used to compute the number of permutations on [n] with a given number of exterior peaks and a given number of proper double descents. Based on the grammar, the recurrence relation of the number of permutations on [n] with a give number of exterior peaks can be easily obtained. Moreover, we use the grammatical calculus to derive the generating function without solving differential equations. Our formula reduces to the formulas of Gessel, Elizalde-Noy, Barry, and Basset. Finally, from the grammar we establish a relationship between our generating function and the generating function of the joint distribution of the number of peaks and the number of double descents derived by Carlitz and Scoville.

Abstract: Publication date: September 2018Source: Advances in Applied Mathematics, Volume 100Author(s): Zachary Gershkoff, James Oxley For a matroid N, a matroid M is N-connected if every two elements of M are in an N-minor together. Thus a matroid is connected if and only if it is U1,2-connected. This paper proves that U1,2 is the only connected matroid N such that if M is N-connected with E(M) > E(N) , then M\e or M/e is N-connected for all elements e. Moreover, we show that U1,2 and M(W2) are the only matroids N such that, whenever a matroid has an N-minor using {e,f} and an N-minor using {f,g}, it also has an N-minor using {e,g}. Finally, we show that M is U0,1⊕U1,1-connected if and only if every clonal class of M is trivial.

Abstract: Publication date: September 2018Source: Advances in Applied Mathematics, Volume 100Author(s): Sandra Di Rocco, David Eklund, Chris Peterson Let L1,…,Ls be line bundles on a smooth complex variety X⊂Pr and let D1,…,Ds be divisors on X such that Di represents Li. We give a probabilistic algorithm for computing the degree of intersections of polar classes which are in turn used for computing the Euler characteristic of linear combinations of L1,…,Ls. The input consists of generators for the homogeneous ideals IX,IDi⊂C[x0,…,xr] defining X and Di.

Abstract: Publication date: September 2018Source: Advances in Applied Mathematics, Volume 100Author(s): Adam Brown, Peter Nelson We construct, for every r≥3 and every prime power q>10, a rank-r matroid with no U2,q+2-minor, having more hyperplanes than the rank-r projective geometry over GF(q).

Abstract: Publication date: September 2018Source: Advances in Applied Mathematics, Volume 100Author(s): Benjamin Braun, Robert Davis, Liam Solus A long-standing open conjecture in combinatorics asserts that a Gorenstein lattice polytope with the integer decomposition property (IDP) has a unimodal (Ehrhart) h⁎-polynomial. This conjecture can be viewed as a strengthening of a previously disproved conjecture which stated that any Gorenstein lattice polytope has a unimodal h⁎-polynomial. The first counterexamples to unimodality for Gorenstein lattice polytopes were given in even dimensions greater than five by Mustaţǎ and Payne, and this was extended to all dimensions greater than five by Payne. While there exist numerous examples in support of the conjecture that IDP reflexives are h⁎-unimodal, its validity has not yet been considered for families of reflexive lattice simplices that closely generalize Payne's counterexamples. The main purpose of this work is to prove that the former conjecture does indeed hold for a natural generalization of Payne's examples. The second purpose of this work is to extend this investigation to a broader class of lattice simplices, for which we present new results and open problems.

Abstract: Publication date: September 2018Source: Advances in Applied Mathematics, Volume 100Author(s): Vasu Tewari, Stephanie van Willigenburg In this note we derive skew Pieri rules in the spirit of Assaf–McNamara for skew quasisymmetric Schur functions using the Hopf algebraic techniques of Lam–Lauve–Sottile, and recover the original rules of Assaf–McNamara as a special case. We then apply these techniques a second time to obtain skew Pieri rules for skew noncommutative Schur functions.

Abstract: Publication date: September 2018Source: Advances in Applied Mathematics, Volume 100Author(s): Ting Guo, Christian Krattenthaler, Yi Zhang Stankova and West showed that for any non-negative integer s and any permutation γ of {4,5,…,s+3} there are as many permutations that avoid 231γ as there are that avoid 312γ. We extend this result to the setting of words.

Abstract: Publication date: September 2018Source: Advances in Applied Mathematics, Volume 100Author(s): Woong Kook, Kang-Ju Lee We introduce the notion of effective resistance for a simplicial network(X,R) where X is a simplicial complex and R is a set of resistances for the top simplices, and prove two formulas generalizing previous results concerning effective resistance for resistor networks. Our approach, based on combinatorial Hodge theory, is to assign a unique harmonic class to a current generatorσ, an extra top-dimensional simplex to be attached to X. We will show that the harmonic class gives rise to the currentIσ and the voltageVσ for X∪σ, satisfying Thomson's energy-minimizing principle and Ohm's law for simplicial networks.The effective resistance Rσ of a current generator σ shall be defined as a ratio of the σ-components of Vσ and Iσ. By introducing potential for voltage vectors, we present a formula for Rσ via the inverse of the weighted combinatorial Laplacian of X in codimension one. We also derive a formula for Rσ via weighted high-dimensional tree-numbers for X, providing a combinatorial interpretation for Rσ. As an application, we generalize Foster's Theorem, and discuss various high-dimensional examples.

Abstract: Publication date: September 2018Source: Advances in Applied Mathematics, Volume 100Author(s): Karl Dilcher, Christophe Vignat Using some basic properties of the gamma function, we evaluate a simple class of infinite products involving Dirichlet characters as a finite product of gamma functions and, in the case of odd characters, as a finite product of sines. As a consequence we obtain evaluations of certain multiple L-series. In the final part of this paper we derive expressions for infinite products of cyclotomic polynomials, again as finite products of gamma or of sine functions.

Abstract: Publication date: September 2018Source: Advances in Applied Mathematics, Volume 100Author(s): Lindsey R. Campbell, Samantha Dahlberg, Robert Dorward, Jonathan Gerhard, Thomas Grubb, Carlin Purcell, Bruce E. Sagan A restricted growth function (RGF) of length n is a sequence w=w1w2…wn of positive integers such that w1=1 and wi≤1+max{w1,…,wi−1} for i≥2. RGFs are of interest because they are in natural bijection with set partitions of {1,2,…,n}. An RGF w avoids another RGF v if there is no subword of w which standardizes to v. We study the generating functions ∑w∈Rn(v)qst(w) where Rn(v) is the set of RGFs of length n which avoid v and st(w) is any of the four fundamental statistics on RGFs defined by Wachs and White. These generating functions exhibit interesting connections with multiset permutations, integer partitions, and two-colored Motzkin paths, as well as noncrossing and nonnesting set partitions.