Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks

We develop a number of statistical aspects of symmetric groups (mostly dealing with the distribution of cycles in various subsets of Sn), asymptotic properties of (ordinary) characters of symmetric groups, and estimates for the multiplicities of root number functions of these groups. As main applications, we present an estimate for the subgroup growth of an arbitrary Fuchsian group, a finiteness result for the number of Fuchsian presentations of such a group (resolving a long-standing problem of Roger Lyndon), as well as a proof of a well-known conjecture of Roichman concerning the mixing time of random walks on symmetric groups.     

Elementary Proof of MacMahon's Conjecture

Major Percy A. MacMahon's first paper on plane partitions [4] included a conjectured generating function for symmetric plane partitions. This conjecture was proven almost simultaneously by George Andrews and Ian Macdonald, Andrews using the machinery of basic hypergeometric series [1] and Macdonald employing his knowledge of symmetric functions [3]. The purpose of this paper is to simplify Macdonald's proof by providing a direct, inductive proof of his formula which expresses the sum of Schur functions whose partitions fit inside a rectangular box as a ratio of determinants.     

The autocorrelation properties of single cycle polynomial T-functions

T-functions have been widely used in the design of symmetric ciphers, hash functions, and fast cryptographic primitives. Single cycle polynomial T-functions are a special category. If they are used as state transition functions of stream ciphers, the security of the generated sequences is crucial. In 2008, Kolokotronis proposed a conjecture regarding the autocorrelation function’s values of coordinate sequences generated by single cycle polynomial T-functions. In this paper, we show that the conjecture does not hold in general and prove the conditions under which it holds.     

Symmetric Functions and Generating Functions for Descents and Major Indices in Compositions

In [18], Mendes and Remmel showed how Gessel’s generating function for the distributions of the number of descents, the major index, and the number of inversions of permutations in the symmetric group could be derived by applying a ring homomorphism defined on the ring of symmetric functions to a simple symmetric function identity. We show how similar methods may be used to prove analogues of that generating function for compositions.     

The permutation enumeration of wreath products Ck4Sn of cyclic and symmetric groups

Brenti introduced a homomorphism from the symmetric functions to polynomials in one variable with rational coefficients. His map is defined on the elementary symmetric functions. When it is applied to the homogeneous and power symmetric functions the results are generating functions for descents and excedences of permutations in the symmetric group, respectively. Beck and Remmel gave proofs of Brenti's results based on combinatorial definitions of the transition matrices between the bases. In addition, they gave an analog for the hyperoctahedral group. We extend the ideas of these proofs to obtain similar results for wreath products of an arbitrary cyclic group with the symmetric group.     

平面分拆的矢量控制方法：列严格梯形平面分拆

作为移位平面分拆的自然拓广,本文引入了梯形平面分拆的概念.应用矢量控制技巧,建立了给定形状和行(列)分部约束的列严格梯形平面分拆集合之枚举函数的初等对称函数行列式表达式.其中之一的重要特例构成了关于循环对称平面分拆的Macdonald猜想的证明基础.     

A strong log-concavity property for measures on Boolean algebras

We introduce the antipodal pairs property for probability measures on finite Boolean algebras and prove that conditional versions imply strong forms of log-concavity. We give several applications of this fact, including improvements of some results of Wagner, a new proof of a theorem of Liggett stating that ultra-log-concavity of sequences is preserved by convolutions, and some progress on a well-known log-concavity conjecture of J. Mason.     

Log-concavity of characteristic polynomials and the Bergman fan of matroids

In a recent paper, the first author proved the log-concavity of the coefficients of the characteristic polynomial of a matroid realizable over a field of characteristic 0, answering a long-standing conjecture of Read in graph theory. We extend the proof to all realizable matroids, making progress towards a more general conjecture of Rota?CHeron?CWelsh. Our proof follows from an identification of the coefficients of the reduced characteristic polynomial as answers to particular intersection problems on a toric variety. The log-concavity then follows from an inequality of Hodge type.     

Log-concavity for Bernstein-type operators using stochastic orders

This paper aims to study the preservation of log-concavity for Bernstein-type operators. In particular, attention is focused on positive linear operators, defined on the positive semi-axis, admitting a probabilistic representation in terms of a process with independent increments. This class includes classical Gamma, Szász and Szász-Durrmeyer operators. As a main tool in our results we use stochastic orders techniques. Our results include, as a particular case, the log-concavity of certain functions related to the gamma incomplete function.     

The toric ideal of a graphic matroid is generated by quadrics

Describing minimal generating sets of toric ideals is a well-studied and difficult problem. Neil White conjectured in 1980 that the toric ideal associated to a matroid is generated by quadrics corresponding to single element symmetric exchanges. We give a combinatorial proof of White’s conjecture for graphic matroids.     

Tautological integrals on symmetric products of curves

We propose a conjecture on the generating series of Chern numbers of tautological bundles on symmetric products of curves and establish the rank 1 and rank -1 case of this conjecture. Thus we compute explicitly the generating series of integrals of Segre classes of tautological bundles of line bundles on curves, which has a similar structure as Lehn's conjecture for surfaces.     

Schur positivity of skew Schur function differences and applications to ribbons and Schubert classes

Some new relations on skew Schur function differences are established both combinatorially using Schützenberger’s jeu de taquin, and algebraically using Jacobi-Trudi determinants. These relations lead to the conclusion that certain differences of skew Schur functions are Schur positive. Applying these results to a basis of symmetric functions involving ribbon Schur functions confirms the validity of a Schur positivity conjecture due to McNamara. A further application reveals that certain differences of products of Schubert classes are Schubert positive. For Manfred Schocker 1970–2006. S.J. van Willigenburg was supported in part by the National Sciences and Engineering Research Council of Canada.     

Strengthening topological colorful results for graphs

Various results ensure the existence of large complete and colorful bipartite graphs in properly colored graphs when some condition related to a topological lower bound on the chromatic number is satisfied. We generalize three theorems of this kind, respectively due to Simonyi and Tardos 2006), Simonyi et al. (2013), and Chen 2011). As a consequence of the generalization of Chen’s theorem, we get new families of graphs whose chromatic number equals their circular chromatic number and that satisfy Hedetniemi’s conjecture for the circular chromatic number.     

Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups

Eulerian quasisymmetric functions were introduced by Shareshian and Wachs in order to obtain a q-analog of Euler?s exponential generating function formula for the Eulerian numbers (Shareshian and Wachs, 2010 [17]). They are defined via the symmetric group, and applying the stable and nonstable principal specializations yields formulas for joint distributions of permutation statistics. We consider the wreath product of the cyclic group with the symmetric group, also known as the group of colored permutations. We use this group to introduce colored Eulerian quasisymmetric functions, which are a generalization of Eulerian quasisymmetric functions. We derive a formula for the generating function of these colored Eulerian quasisymmetric functions, which reduces to a formula of Shareshian and Wachs for the Eulerian quasisymmetric functions. We show that applying the stable and nonstable principal specializations yields formulas for joint distributions of colored permutation statistics, which generalize the Shareshian–Wachs q-analog of Euler?s formula, formulas of Foata and Han, and a formula of Chow and Gessel.     

Derivative polynomials and enumeration of permutations by number of interior and left peaks

Derivative polynomials in two variables are defined by repeated differentiation of the tangent and secant functions. We establish the connections between the coefficients of these derivative polynomials and the number of interior and left peaks over the symmetric group. Properties of the generating functions for the number of interior and left peaks over the symmetric group, including recurrence relations, generating functions and real-rootedness, are studied.     

Jack vertex operators and realization of Jack functions

We give an iterative method to realize general Jack functions using vertex operators. We first prove some cases of Stanley’s conjecture on positivity of the Littlewood–Richardson coefficients, and then use this method to give a new realization of Jack functions. We also show in general that the images of coefficients of products of Jack vertex operators form a basis of symmetric functions. In particular, this gives a new proof of linear independence for the rectangular and marked rectangular Jack vertex operators. Finally, a generalized Frobenius formula for Jack functions is given and used for evaluation of Dyson integrals and even powers of Vandermonde determinants.     

两类对称函数的Schur凸性

本文用一种新方法研究两类对称函数的Schur凸性.首先,对x=(x1,...,xn)∈(-∞,1)n∪(1,+∞)n和r∈{1,2,...,n},讨论Guan(2007)定义的对称函数Fn(x,r)=Fn(x1,x2,...,xn;r)=∑1≤i1≤i2≤···≤ir≤n r∏j=1xij/(1-xij)的Schur凸性,其中i1,i2,...,in为正整数;推广褚玉明等人(2009)的主要结果,因而用新方法推广并解决Guan(2007)提出的一个公开问题.然后,对x=(x1,...,xn)∈(-∞,1)n∪(1,+∞)n和r∈{1,2,...,n},研究本文定义的对称函数Gn(x,r)=Gn(x1,x2,...,xn;r)=∑1≤i1≤i2≤···≤ir≤n(r∏j=1xij/(1-xij))1/r的Schur凸性、Schur乘性凸性和Schur调和凸性,其中i1,i2,...,in为正整数.作为应用,用Schur凸函数自变量的双射变换得到其他几类对称函数的Schur凸性,用控制理论建立一些不等式,特别地,由此给出Sharpiro不等式和Ky Fan不等式一个共同的推广,导出Safta猜想在高维空间的推广.     

Characterization of the alternating groups by their order and one conjugacy class length

Let G be a finite group, and let N(G) be the set of conjugacy class sizes of G. By Thompson’s conjecture, if L is a finite non-abelian simple group, G is a finite group with a trivial center, and N(G) = N(L), then L and G are isomorphic. Recently, Chen et al. contributed interestingly to Thompson’s conjecture under a weak condition. They only used the group order and one or two special conjugacy class sizes of simple groups and characterized successfully sporadic simple groups (see Li’s PhD dissertation). In this article, we investigate validity of Thompson’s conjecture under a weak condition for the alternating groups of degrees p+1 and p+2, where p is a prime number. This work implies that Thompson’s conjecture holds for the alternating groups of degree p + 1 and p + 2.     

Differential equations for septic theta functions

We demonstrate that quotients of septic theta functions appearing in Ramanujan’s Notebooks and in Klein’s work satisfy a new coupled system of nonlinear differential equations with symmetric form. This differential system bears a close resemblance to an analogous system for quintic theta functions. The proof extends an elementary technique used by Ramanujan to prove the classical differential system for normalized Eisenstein series on the full modular group. In the course of our work, we show that Klein’s quartic relation induces symmetric representations for low-weight Eisenstein series in terms of weight one modular forms of level seven.     

On graded Cartan invariants of symmetric groups and Hecke algebras

We consider graded Cartan matrices of the symmetric groups and the Iwahori-Hecke algebras of type A at roots of unity. These matrices are \({\mathbb {Z}}[v,v^{-1}]\)-valued and may also be interpreted as Gram matrices of the Shapovalov form on sums of weight spaces of a basic representation of an affine quantum group. We present a conjecture predicting the invariant factors of these matrices and give evidence for the conjecture by proving its implications under a localization and certain specializations of the ring \({\mathbb {Z}}[v,v^{-1}]\). This proves and generalizes a conjecture of Ando-Suzuki-Yamada on the invariants of these matrices over \({\mathbb {Q}}[v,v^{-1}]\) and also generalizes the first author’s recent proof of the Külshammer-Olsson-Robinson conjecture over \({\mathbb {Z}}\).