Search

In this paper, we study pattern avoidance on the set of biwords with no repetitions in each block and prove that the number of those biwords avoiding π ‾ is independent of the choice of π ∈ S 3 , which extends Knuth's classic result on permutations avoiding π ∈ S 3 . We present the proof in both bijective and inductive methods. As applications, we will give new combinatorial interpretations on Catalan, Riordan, and Motzkin numbers via pattern avoidance of biwords. Using the elementary theory of symmetric functions, we investigate the generating functions of biwords avoiding several specific patterns.

Stanley's symmetrized chromatic polynomial is a generalization of the ordinary chromatic polynomial to a graph invariant with values in a ring of polynomials in infinitely many variables. The ordinary chromatic polynomial is a specialization of Stanley's one. To each orientable embedded graph with a single vertex, a simple graph is associated, which is called the intersection graph of the embedded graph. As a result, we can define Stanley's symmetrized chromatic polynomial for any orientable embedded graph with a single vertex. Our goal is to extend Stanley's chromatic polynomial to embedded graphs with arbitrary number of vertices, and not necessarily orientable. In contrast to well-known extensions of, say, the Tutte polynomial from abstract to embedded graphs [4] , our extension is based not on the structure of the underlying abstract graph and the additional information about the embedding. Instead, we consider the binary delta-matroid associated to an embedded graph and define the extended Stanley chromatic polynomial as an invariant of binary delta-matroids. We show that, similarly to Stanley's symmetrized chromatic polynomial of graphs, which satisfies 4-term relations for simple graphs, the polynomial that we introduce satisfies the 4-term relations for binary delta-matroids [7] . For graphs, Stanley's chromatic function produces a knot invariant by means of the correspondence between simple graphs and knots. Analogously we may interpret the suggested extension as an invariant of links, using the correspondence between binary delta-matroids and links.

We consider here the algebra of noncommutative symmetric functions, and two of its bases, the ribbon basis and the immaculate basis. Although a simple combinatorial formula is known for expanding an element of the ribbon basis in the immaculate basis, the reverse is not known. Using a sign-reversing involution, we prove an analogue of the classical JacobiTrudi formula which is an expression for an immaculate function indexed by a rectangle in the ribbon basis. We generalize this result to immaculate functions indexed by products of rectangles, and use this to prove a combinatorial formula for immaculate functions indexed by a rectangle of the form (2n).

We use the K -Knuth equivalence of Buch and Samuel (2015) to define a K -theoretic analogue of the Poirier-Reutenauer Hopf algebra. As an application, we rederive the K -theoretic Littlewood-Richardson rules of Thomas and Yong (2009, 2011) and of Buch and Samuel (2015).

Rotation symmetric Boolean functions have been extensively studied in the last fifteen years or so because of their importance in cryptography and coding theory. Until recently, very little was known about the basic question of when two such functions are affine equivalent. The simplest case of quadratic rotation symmetric functions which are generated by cyclic permutations of the variables in a single monomial was only settled in a 2009 paper of Kim, Park and Hahn. The much more complicated analogous problem for cubic functions was solved for permutations using a new concept of patterns in a 2011 paper of Cusick, and it is conjectured that, as in the quadratic case, this solution actually applies for all affine transformations. The patterns method enables a detailed analysis of the affine equivalence classes for various special classes of cubic rotation symmetric functions in n variables. Here the case of functions generated by a single monomial and having p q variables, where p and q are primes, is examined in detail, and in particular, a formula for the number of classes is proved. This is significant because it is the first time that a complete enumeration of the number of classes has been found when the number of variables is divisible by two distinct primes.

We show that the symmetric function generalization of the chromatic polynomial, or equivalently, the U-polynomial, distinguishes among a large class of caterpillar trees that we call proper, thus improving previous results by Martin, Morin and Wagner.

Carlitz (1973) [5] and Rawlings (2000) [13] studied two different analogues of up-down permutations for compositions with parts in {1,...,n}. Cristea and Prodinger (2008/2009) [7] studied additional analogues for compositions with unbounded parts. We show that the results of Carlitz, Rawlings, and Cristea and Prodinger on up-down compositions are special cases of four different analogues of generalized Euler numbers for compositions. That is, for any s>=2, we consider classes of compositions that can be divided into an initial set of blocks of size s followed by a block of size j where 0@?j@?s-1. We then consider the classes of such compositions where all the blocks are strictly increasing (weakly increasing) and there are strict (weak) decreases between blocks. We show that the weight generating functions of such compositions w=w"1...w"m, where the weight of w is @?"i"="1^mz"w"""i, are always the quotients of sums of quasi-symmetric functions. Moreover, we give a direct combinatorial proof of our results via simple involutions.

Rotation symmetric Boolean functions have important applications in the design of cryptographic algorithms. We prove the conjecture about rotation symmetric Boolean functions (RSBFs) of degree 3 proposed in Cusick and Stănică (2002) [2] and its generalization, thus the nonlinearity of such functions is determined.

We show that with the exception of four known cases: C3, C4, C5, and S22, all regular permutation groups can be represented as symmetric groups of boolean functions. This solves the problem posed by A. Kisielewicz in the paper [A. Kisielewicz, Symmetry groups of boolean functions and constructions of permutation groups, J. Algebra 199 (1998) 379–403]. A slight extension of our proof yields the same result for semiregular groups.

We resolve affirmatively some conjectures of Reiner, Stanton, and White (2004) [12] regarding enumeration of transportation matrices which are invariant under certain cyclic row and column rotations. Our results are phrased in terms of the bicyclic sieving phenomenon introduced by Barcelo, Reiner, and Stanton (2009) [1]. The proofs of our results use various tools from symmetric function theory such as the Stanton-White rim hook correspondence (Stanton and White (1985) [18]) and results concerning the specialization of Hall-Littlewood polynomials due to Lascoux, Leclerc, and Thibon (1994, 1997) [5,6].

In this paper we analyze the combinatorial properties related to the Walsh spectra of rotation symmetric Boolean functions on even number of variables. These results are then applied in studying rotation symmetric bent functions. For the first time we could present an enumeration strategy for all the 10-variable rotation symmetric bent functions.

As a generalization of Haglund's statistic on Dyck paths [Conjectured statistics for the q,t-Catalan numbers, Adv. Math. 175 (2) (2003) 319-334; A positivity result in the theory of Macdonald polynomials, Proc. Nat. Acad. Sci. 98 (2001) 4313-4316], Egge et al. introduced the (q,t)-Schroder polynomial S"n","d(q,t), which evaluates to the Schroder number when q=t=1 [A Schroder generalization of Haglund's statistic on Catalan paths, Electron. J. Combin. 10 (2003) 21pp (Research Paper 16, electronic)]. In their paper, S"n","d(q,t) was conjectured to be equal to the coefficient of a hook shape on the Schur function expansion of the symmetric function @?e"n, which Haiman [Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002) 371-407] has shown to have a representation-theoretic interpretation. This conjecture was recently proved by Haglund [A proof of the q,t-Schroder conjecture, Internat. Math. Res. Not. (11) (2004) 525-560]. However, because that proof makes heavy use of symmetric function identities and plethystic machinery, the combinatorics behind it is not understood. Therefore, it is worthwhile to study it combinatorially. This paper investigates the limiting case of the (q,t)-Schroder Theorem and obtains interesting results by looking at some special cases.

A multivariate generating function involving the descent, major index, and inversion statistic first given by Ira Gessel is generalized to other permutation groups. We provide generating functions for variants of these three statistics for the Weyl groups of type B and D, wreath product groups, and multiples of permutations. All of our ideas are combinatorial in nature and exploit fundamental relationships between the elementary and homogeneous symmetric functions.

A permutation set (P,A) is said symmetric if for any two elements a,b∈P there is exactly one permutation in A switching a and b. We show two distinct techniques to derive an algebraic structure from a given symmetric permutation set and in each case we determine the conditions to be fulfilled by the permutation set in order to get a left loop, or even a loop (commutative in one case). We also discover some nice links between the two operations and finally consider some applications of these constructions within absolute geometry, where the role of the symmetric permutation set is played by the regular involution set of point reflections.

Recently, Brenti introduced a class of q-symmetric functions based on a simple plethysm with the power-sum symmetric functions. Brenti developed combinatorial interpretations for the transition matrices between these new symmetric functions and the standard symmetric function bases. We provide simplified versions of many of these that are sums over significantly smaller classes of combinatorial objects. We also show that two of our results generalize formulas of MacMahon relating vector compositions to the expansion of a product of binomial coefficients as a sum of binomial coefficients. We then extend Brenti's definitions to symmetric functions on the hyperoctahedral group, B"n, and give combinatorial interpretations of the analogous transition matrices. We also discuss new generating functions on permutation statistics that arise from Brenti's symmetric functions and our extensions, two of which show a curious connection to Stirling numbers of the second kind.

We study the nonlinearity and the weight of the rotation-symmetric (RotS) functions defined by Pieprzyk and Qu. We give exact results for the nonlinearity and weight of 2-degree RotS functions with the help of the semi-bent functions and we give the generating function for the weight of the 3-degree RotS function. Based on the numerical examples and our observations we state a conjecture on the nonlinearity and weight of the 3-degree RotS functions., Comment: 20 pages; submitted to Discrete Mathematics

We present a method of solving combinatorialdifferential equations based on the utilization of symmetric functions in the context of combinatorial species introduced by Joyal (see Adv. in Math. 42 (1981) 1). Our approach relies on an isomorphism between the ring of symmetric functions and the ring of rational set species, whose elements are formal sums involving variables Ei, the species of sets of cardinality i. This isomorphism is used to calculate the kernel of the derivative D operator restricted to the above ring. We also study the equation Y'=(1+Y)2, Y(0)= 0 for which we give, apart from the solution L* (nonempty linear orders), another solution in the half-ring of species of sets. The question of the existence of another solution to this equation has been raised (J. Math. Anal. Appl. 113 (2) (1986) 334).

For any homomorphism V on the space of symmetric functions, we introduce an operation which creates a q-analog of V. By giving several examples we demonstrate that this quantization occurs naturally within the theory of symmetric functions. In particular, we show that the Hall-Littlewood symmetric functions are formed by taking this q-analog of the Schur symmetric functions and the Macdonald symmetric functions appear by taking the q-analog of the Hall-Littlewood symmetric functions in the parameter t. This relation is then used to derive recurrences on the Macdonald q,t-Kostka coefficients., Comment: 17 pages - minor revisions to appear in Discrete Mathematics issue for LaCIM'2000

Stanley associated to a simple graph G a symmetric function X G which generalizes the chromatic polynomial of G . He conjectured that X G is Schur positive when G is clawfree. This is equivalent to the minors of a certain matrix with polynomial entries being polynomials with nonnegative coefficients. We prove this for the 2×2 minors, which extends a result of Krattenthaler (J. Combin. Theory Ser. A 74(2) (1996) 351–354). We also give a characterization of clawfree graphs in terms of cardinalities of stable sets.

We show that the poset of shuffles introduced by Greene in 1988 is flag-symmetric, and we describe a "local" permutation action of the symmetric group on the maximal chains which is closely related to the flag symmetric function of the poset. A key tool is provided by a new labeling of the maximal chains of a poset of shuffles, which is also used to give bijective proofs of enumerative properties originally obtained by Greene. In addition we define a monoid of multiplicative functions on all posets of shuffles and describe this monoid in terms of a new operation on power series in two variables., 34 pages, 6 figures

We present a simple proof of the Littlewood-Richardson rule using a sign-reversing involution, and show that a similar involution provides a combinatorial proof of the SXP algorithm of Chen et al. (1984) which computes the Schur function expansion of the plethysm of a Schur function and a power sum symmetric function. The methods of this paper have also been applied to prove combinatorial formulas for the characters of coordinate rings of nilpotent conjugacy classes of matrices (Shimozono, 1998).

Let F C denote the basic quasi-symmetric functions, in Gessel's notation (1984) ( C any composition). The plethysm s λ oF C is a positive linear combination of functions F D . Under certain conditions, the image under the involution ω of a quasi-symmetric function defined by equalities and inequalities of the variables is obtained by negating the inequalities.

Hopf algebras play a major role in such diverse mathematical areas as algebraic topology, formal group theory, and theoretical physics, and they are achieving prominence in combinatorics through the influence of G.-C. Rota and his school. Our primary purpose in this article is to build on work of Schmitt [18,19], and establish combinatorial models for several of the Hopf algebras associated with umbral calculus and formal group laws. In so doing, we incorporate and extend certain invariants of simple graphs such as the umbral chromatic polynomial, and Stanley's [21] recently introduced symmetric function. Our fundamental combinatorial components are finite set systems, together with a versatile generalization in which they are equipped with a group of automorphisms. Interactions with the Roman-Rota umbral calculus over graded rings of scalars which may contain torsion are a significant feature of our presentation.

We study permutation enumeration of the hyperoctahedral group Bn through a combinatorial use of the Bn-analogues of symmetric functions, denoted AB. We define an appropriate homomorphism ζ:AB → Q[x] and remarkably, applying this homomorphism to one of the bases of AB produces polynomials which correspond to enumerating Bn with respect to descents. Applying ζ to a second basis corresponds to enumerating a conjugacy class of Bn with respect to a new descent type statistic which arises naturally.

In [5] Stanley associated to a (finite) graph G a symmetric function X G generalizing the chromatic polynomial of G . Using an involution on a special type of arrays constructed by Gessel and Viennot [1], we show that if G is the incomparability graph of a ( 3 + 1 )-free poset, then X G is a nonnegative linear combination of Schur functions. Since the elementary symmetric functions are nonnegative linear combinations of Schur functions, this result gives supportive evidence for a conjecture of Stanley and Stembridge ([5, Conjecture 5.1] or [6, Conjecture 5.5]).

In this paper, we develop the combinatorial interpretations of the transition matrices between the bases of the Bn analogues of the symmetric functions. In order to provide a complete reference, we have included a summary of the transition matrices for symmetric functions as well.

Given an algebra A , p n ( A ) denotes the number of distinct n -ary term operations t : A n → A of A which depend on all n variables. We solve some problems of Berman, Gratzer and Kisielewicz concerning the sequence 〈 p 0 ( A ), p 1 ( A ),…, p n ( A ),…〉 in case ¦A¦ is finite. Our methods yield new results about totally symmetric functions on a finite set.

A bijective definition of Littlewood's plethysm of symmetric functions in terms of unlabelled colored combinatorial structures is introduced. The plethystic inverse is understood by examining associated partially ordered sets and using Mobius inversion techniques.

Hanlon, P., A Markov chain on the symmetric group and Jack symmetric functions, Discrete Mathematics 99 (1992) 123-140. Diaconis and Shahshahani studied a Markov chain Wf(l) whose states are the elements of the symmetric group S,. In W,(l), you move from a permutation n to any permutation of the form a(i, j) with equal probability. In this paper we study a deformation W,(a) of this Markov chain which is obtained by applying the Metropolis algorithm to Wf(l). The stable distribution of W,(a) is 6-C(Z) where C(A) denotes the number of cycles of x. Our main result is that the eigenvectors of the transition matrix of W,(a) are the Jack symmetric functions. We use facts about the Jack symmetric functions due to Macdonald and Stanley to obtain precise estimates for the rate of convergence of W,( (u) to its stable distribution.

The sum of Schur symmetric functions in a countable set of variables, over partitions with given trace and upper bound on the number of parts, is evaluated. This generalizes results of Gordon (1971). The method is to extend an analogous sum in a finite set of variables by means of a linear operator.

A given structure is said to be asymmetric if its automorphism group reduces to the identity. The problem of enumerating asymmetric structures (and, more generally, to count structures according to stabilizers) is usually solved by making use of Möbius inversion techniques and symmetric functions in the context of group actions. This method of solution was introduced by Rota (1964, 1969) who defined special classes of polynomials which may be called asymmetry indicator polynomials. Subsequent developments following similar ideas can be found in Stockmeyer (1971), White (1975), Rota, Smith and Sagan (1977, 1980), Kerber (1986). We present here another approach to this problem within the theory of species of structures in the sense of Joyal (1981, 1985, 1986). Every species of structures F contains a sub-species F̄, called the flat part of F, consisting of all asymmetric F-structures. We introduce an asymmetry indicator series ΓF(x1, x2, x3,…) by means of which we study the correspondence F↦F̄ in connection with the various operations existing in the theory of species of structures. The main result is that the ΓF behaves with respect to the combinatorial operations of sum, product, substitution and differentiation as does the classical cycle indicator series ZF. As a consequence, the asymmetry indicator series can be applied to the systematic classification and enumeration of asymmetric F-structures when the species F is defined (explicitly or recursively) by combinatorial equations. We illustrate the method on particular species (including enriched trees and rooted trees) and a table of ΓF is given for the atomic species concentrated on small cardinalities. Examples show that ΓF contains information independent of that in ZF.

Let @D(@a + @b) = |H"@l"""2"-"r"+"1| where H"r is the complete symmetric function in (@a"1 + @b"1), (@a"2 + @b"2), ..., (@a"n + @b"n). It is proved that @D(@a + @b) >= @D(@a) + @D(@b). This inequality is generalised for certain symmetric functions defined by Littlewood. Let @W(@a + @b) = |Q"@l"""2"-"r"+"1^s^t^a^g^g^e^r^e^d^(^@a^ ^+^ ^@b^) (t, k"1, k"2, ..., k"m)|. Then we prove that @W(@a + @b) >= @W(@a) + @W(@b). Here @l"1, @l"2, @l"3, ..., @l"n is a partition such that @l"n > @l"n"-"1 > ... > @l"2 > @l"1.

In a λ-ring there are operations λ π , ψ π and β π for π a partition of n . These operations are related by identities analogous to those between the symmetric functions a π , s π and h π . In a β-ring there is defined an operation β H for [ H ] a conjugacy class of subgroups of the symmetric group S n . This paper defines operations ψ H and λ H in a β-ring such that whenever the β-ring is a λ-ring, and H a Young subgroup S π of S n , then the β H , ψ H and λ H reduce to β π , ψ π and λ π , respectively. The identities relating the new operations are also investigated.

We make a systematic study of a new concept in the theory of jeu-de-taquin , which we call dual equivalence . Using this, we prove a conjecture of Proctor establishing a bijection between standard tableaux of ‘shifted staircase’ shape and reduced expressions for the longest element in the Coxeter group B l . We also get a new and more illuminating proof of the analogous theorem, due to Greene and Edelman, for the Coxeter group A l , and arrive at yet one more theorem of a similar type. We explain some symmetric functions associated to reduced expressions by Stanley and prove his conjecture that one of these for B l is the Schur function s λ for λ an l-by- l square. We classify shifted and unshifted shapes for which the total promotion operator has special properties; in one case this proves another conjecture of Stanley. We determine the previously unknown ‘dual Knuth relations’ for the shifted Schensted correspondence.

For a graph G whose vertices are v1,v2,…,vm and where E is the set of edges, we define a functional U G (h)=ʃʃ…ʃ ∏ {v i ,v j }∈E h(x i ,x j ) dμ(x 1 )dμ(x 2 )…dμ(x m ) , where h is a nonnegative symmetric function of two variables. We consider a binary relation ≽ for graphs with fixed numbers of vertices and edges, where G≽L means that UG(h)⩾UL(h) for every h. We prove that this relation is equivalent to the condition: the number of homomorphisms into every graph H from G is not less than from L. We obtain comparability and incomparability criteria and investigate the poset of k-edge trees. In particular, the first and the second maximal elements of this poset are found.

We give inductive proofs of q -log concavity for the Gaussian polynomials and the q -Stirling numbers of both kinds. Similar techniques are applied to show that certain sequences of elementary and complete symmetric functions are q -log concave.

New subsets of symmetric balanced and symmetric correlation immune functions are identified. The method involves interesting relations on binomial coefficients and highlights the combinatorial richness of these classes. As a consequence of our constructive techniques, we improve upon the existing lower bounds on the cardinality of the above sets. We consider higher order correlation immune functions and show how to construct n -variable, 3rd order correlation immune function for each perfect square n ≥ 9.

RésuméNous démontrons des inégalités entre fonctions symétriques, qui généralisent une conjecture de Sagan. Les spécialisations classiques donnent des résultats de log-concavité pour des analogues de coefficients binômiaux et de nombres de Stirling. En particulier une conjecture de Leroux est vérifiée.AbstractWe prove inequalities between symmetric functions that generalize a conjecture by Sagan. Classical specializations lead to log-concavity results for analogues of the binomial coefficients and Stirling numbers. As a special case, a conjecture by Leroux is proved.

We introduce analogs of the Hopf algebra of Free quasi-symmetric functions with bases labelled by colored permutations. When the color set is a semigroup, an internal product can be introduced. This leads to the construction of generalized descent algebras associated with wreath products $\Gamma\wr\SG_n$ and to the corresponding generalizations of quasi-symmetric functions. The associated Hopf algebras appear as natural analogs of McMahon's multisymmetric functions. As a consequence, we obtain an internal product on ordinary multi-symmetric functions. We extend these constructions to Hopf algebras of colored parking functions, colored non-crossing partitions and parking functions of type B., Comment: 34 pages; LaTEX

This note describes ideals generated by symmetric polynomials in two sets of variables A , B . These ideals generalize the ideals generated by differences of elementary symmetric functions considered by Fischer (1988) and the ideals generated by symmetric functions in the formal difference A-B described by Pragacz (1987). The main tool is divided differences.

The Jack symmetric function J λ ( x ;α) is a symmetric function with interesting properties that J λ ( x ;2) is a spherical function of the symmetric pair ( GL ( n , R ), O ( n , R ) and that J λ ( x ;1) is the Schur function S λ ( x ). Many interesting conjectures about the combinatorial properties of J λ ( x;α ) are given by Stanley (1989). In this paper we give an affirmative answer to one of his conjectures.

In this paper we show that after suitable specialization the ‘balanced’ side of the U ( n +1) Rogers-Selberg identity gives the generating function for all partitions whose parts differ by at least ( n +1). A similar specialization yields the additional condition that the parts must be ⩾ n +1. The case n =1 is the sum side of the pair of classical Rogers-Ramanujan-Schur identities. Our derivation of this connection between classical partition functions and the U ( n +1) Rogers-Selberg identity relies upon partial fraction techniques, Hall-Littlewood polynomials, raising operators, q -Kostka matrices, the Cauchy identity for Schur functions, and generating functions for column-strict plane partitions. One outcome of this work is a new class of symmetric functions H λ ( z ; γ , q ), analogous to Hall-Littlewood polynomials, that interpo- lates between Schur functions and complete homogeneous symmetric functions. Let ω : Λ → Λ be the classical involution on the ring of symmetric functions defined by ω ( h λ )= e λ . Then the function ω ( H λ ( z ;∅; q ))= E λ ( z ;∅; q ) leads to explicit q -difference equations, raising operator formulas, and a combinatorial setting for an important nontrivial special case Macdonald's new class of symmetric functions with two free parameters. This connection with Macdonald's work is observed and developed in the paper of A. Garsia.

Let Σ denote the Coxeter complex of Sn, and let X(Σ) denote the associated toric variety. Since the Betti numbers of the cohomology of X(Σ) are Eulerian numbers, the additional presence of an Sn-module structure permits the definition of an isotypic refinement of these numbers. In some unpublished work, DeConcini and Procesi derived a recurrence for the Sn-character of the cohomology of X(Σ), and Stanley later used this to translate the problem of combinatorially describing the isotypic Eulerian numbers into the language of symmetric functions. In this paper, we explicitly solve this problem by developing a new way to use marked sequences to encode permutations. This encoding also provides a transparent explanation of the unimodality of Eulerian numbers and their isotypic refinements.

We express the number of elements of the hyperoctahedral group Bn, which have descent set K and such that their inverses have descent set J, as a scalar product of two representations of Bn. We also give the number of elements of Bn, which have a prescribed descent set and which are in a given conjugacy class of Bn by another scalar product of representations of Bn. For this, we first establish corresponding results for certain wreath products. We finally give, by generating series of symmetric functions, some analogs of the classical formulas which express the exponential generating series of alternating elements in the Bn's.