Alexander Belton, Dominique Guillot, Apoorva Khare
et al.
A classical result by Schoenberg (1942) identifies all real-valued functions that preserve positive semidefi- niteness (psd) when applied entrywise to matrices of arbitrary dimension. Schoenberg's work has continued to attract significant interest, including renewed recent attention due to applications in high-dimensional statistics. However, despite a great deal of effort in the area, an effective characterization of entrywise functions preserving positivity in a fixed dimension remains elusive to date. As a first step, we characterize new classes of polynomials preserving pos- itivity in fixed dimension. The proof of our main result is representation theoretic, and employs Schur polynomials. An alternate, variational approach also leads to several interesting consequences including (a) a hitherto unexplored Schubert cell-type stratification of the cone of psd matrices, (b) new connections between generalized Rayleigh quo- tients of Hadamard powers and Schur polynomials, and (c) a description of the joint kernels of Hadamard powers.
We define and enumerate a new class of self-avoiding walks on the square lattice, which we call <i>weakly prudent bridges</i>. Their definition is inspired by two previously-considered classes of self-avoiding walks, and can be viewed as a combination of those two models. We consider several methods for recursively generating these objects, each with its own advantages and disadvantages, and use these methods to solve the generating function, obtain very long series, and randomly generate walks of arbitrary size. We find that the growth constant of these walks is approximately 2.58, which is larger than that of any previously-solved class of self-avoiding walks.
A Weyl arrangement is the arrangement defined by the root system of a finite Weyl group. When a set of positive roots is an ideal in the root poset, we call the corresponding arrangement an ideal subarrangement. Our main theorem asserts that any ideal subarrangement is a free arrangement and that its exponents are given by the dual partition of the height distribution, which was conjectured by Sommers-Tymoczko. In particular, when an ideal subarrangement is equal to the entire Weyl arrangement, our main theorem yields the celebrated formula by Shapiro, Steinberg, Kostant, and Macdonald. The proof of the main theorem is classification-free. It heavily depends on the theory of free arrangements and thus greatly differs from the earlier proofs of the formula.
We prove an identity conjectured by Adin and Roichman involving the descent set of $\lambda$-unimodal cyclic permutations. These permutations appear in the character formulas for certain representations of the symmetric group and these formulas are usually proven algebraically. Here, we give a combinatorial proof for one such formula and discuss the consequences for the distribution of the descent set on cyclic permutations.
We introduce a poset structure on the reduced galleries in a supersolvable arrangement of hyperplanes. In particular, for Coxeter groups of type A or B, we construct a poset of reduced words for the longest element whose Hasse diagram is the graph of reduced words. Using Rambau's Suspension Lemma, we show that these posets are homotopy equivalent to spheres. We furthermore conjecture that its intervals are either homotopy equivalent to spheres or are contractible. One may view this as a analogue of a result of Edelman and Walker on the homotopy type of intervals of a poset of chambers of a hyperplane arrangement.
To every matroid, we associate a class in the K-theory of the Grassmannian. We study this class using the method of equivariant localization. In particular, we provide a geometric interpretation of the Tutte polynomial. We also extend results of the second author concerning the behavior of such classes under direct sum, series and parallel connection and two-sum; these results were previously only established for realizable matroids, and their earlier proofs were more difficult.
K. A. Penson, Pawel Blasiak, Gérard Duchamp
et al.
We construct explicit solutions of a number of Stieltjes moment problems based on moments of the form ${\rho}_{1}^{(r)}(n)=(2rn)!$ and ${\rho}_{2}^{(r)}(n)=[(rn)!]^{2}$, $r=1,2,\dots$, $n=0,1,2,\dots$, \textit{i.e.} we find functions $W^{(r)}_{1,2}(x)>0$ satisfying $\int_{0}^{\infty}x^{n}W^{(r)}_{1,2}(x)dx = {\rho}_{1,2}^{(r)}(n)$. It is shown using criteria for uniqueness and non-uniqueness (Carleman, Krein, Berg, Pakes, Stoyanov) that for $r>1$ both ${\rho}_{1,2}^{(r)}(n)$ give rise to non-unique solutions. Examples of such solutions are constructed using the technique of the inverse Mellin transform supplemented by a Mellin convolution. We outline a general method of generating non-unique solutions for moment problems generalizing ${\rho}_{1,2}^{(r)}(n)$, such as the product ${\rho}_{1}^{(r)}(n)\cdot{\rho}_{2}^{(r)}(n)$ and $[(rn)!]^{p}$, $p=3,4,\dots$.
Anouk Bergeron-Brlek, Christophe Hohlweg, Mike Zabrocki
Let $V$ be a complex vector space with basis $\{x_1,x_2,\ldots,x_n\}$ and $G$ be a finite subgroup of $GL(V)$. The tensor algebra $T(V)$ over the complex is isomorphic to the polynomials in the non-commutative variables $x_1, x_2, \ldots, x_n$ with complex coefficients. We want to give a combinatorial interpretation for the decomposition of $T(V)$ into simple $G$-modules. In particular, we want to study the graded space of invariants in $T(V)$ with respect to the action of $G$. We give a general method for decomposing the space $T(V)$ into simple $G$-module in terms of words in a particular Cayley graph of $G$. To apply the method to a particular group, we require a surjective homomorphism from a subalgebra of the group algebra into the character algebra. In the case of the symmetric group, we give an example of this homomorphism from the descent algebra. When $G$ is the dihedral group, we have a realization of the character algebra as a subalgebra of the group algebra. In those two cases, we have an interpretation for the graded dimensions of the invariant space in term of those words.
A permutation $a_1a_2 \ldots a_n$ is $\textit{indecomposable}$ if there does not exist $p \lt n$ such that $a_1a_2 \ldots a_p$ is a permutation of $\{ 1,2, \ldots ,p\}$. We compute the asymptotic probability that a permutation of $\mathbb{S}_n$ with $m$ cycles is indecomposable as $n$ goes to infinity with $m/n$ fixed. The error term is $O(\frac{\log(n-m)}{ n-m})$. The asymptotic probability is monotone in $m/n$, and there is no threshold phenomenon: it degrades gracefully from $1$ to $0$. When $n=2m$, a slight majority ($51.1 \ldots$ percent) of the permutations are indecomposable. We also consider indecomposable fixed point free involutions which are in bijection with maps of arbitrary genus on orientable surfaces, for these involutions with $m$ left-to-right maxima we obtain a lower bound for the probability of being indecomposable.
It is well-known, and was first established by Knuth in 1969, that the number of 321-avoiding permutations is equal to that of 132-avoiding permutations. In the literature one can find many subsequent bijective proofs confirming this fact. It turns out that some of the published bijections can easily be obtained from others. In this paper we describe all bijections we were able to find in the literature and we show how they are related to each other (via "trivial'' bijections). Thus, we give a comprehensive survey and a systematic analysis of these bijections. We also analyze how many permutation statistics (from a fixed, but large, set of statistics) each of the known bijections preserves, obtaining substantial extensions of known results. We also give a recursive description of the algorithmic bijection given by Richards in 1988 (combined with a bijection by Knuth from 1969). This bijection is equivalent to the celebrated bijection of Simion and Schmidt (1985), as well as to the bijection given by Krattenthaler in 2001, and it respects 11 statistics (the largest number of statistics any of the bijections respect).
In this paper we propose a new bijection between permutation tableaux and permutations. This bijection shows how natural statistics on the tableaux are equidistributed to classical statistics on permutations: descents, RL-minima and pattern enumerations. We then use the bijection, and a related encoding of tableaux by words, to prove results about the enumeration of permutations with a fixed number of 31-2 patterns, and to define subclasses of permutation tableaux that are in bijection with set partitions. An extended version of this work is available in [6].