Publications and Preprints by Sami Assaf

On dual equivalence.

We define dual equivalence for an arbitrary collection of objects endowed with a descent set and show that giving a dual equivalence for a collection implies that the quasi-symmetric generating function is symmetric and Schur positive. We give an explicit formula for the Schur expansion of the generating function in terms of distinguished elements of the dual equivalence classes. We also show how this method simplifies when the collection of objects has a sufficiently nice reading word. arXiv:1107.0090
Video from Banff worshop on Quasisymmetric Functions

Cyclic derangements. Electronic Journal of Combinatorics 17 (2010), no. 1, Research Paper 163, 14 pp.

A classic problem in enumerative combinatorics is to count the number of derangements, that is, permutations with no fixed point. Inspired by a recent generalization to facet derangements of the hypercube by Gordon and McMahon, we generalize this problem to enumerating derangements in the wreath product of any finite cyclic group with the symmetric group. We also give q- and (q,t)-analogs for cyclic derangements, generalizing results of Brenti and Gessel. arXiv:1002.3138

(with Peter McNamara) A Pieri rule for skew shapes. Journal of Combinatorial Theory, Series A 118 (2011), 277--290.

The Pieri rule expresses the product of a Schur function and a single row Schur function in terms of Schur functions. We extend the classical Pieri rule by expressing the product of a skew Schur function and a single row Schur function in terms of skew Schur functions. Like the classical rule, our rule involves simple additions of boxes to the original skew shape. arXiv:0908.0345

(with Sara Billey) Affine dual equivalence and k-Schur positivity.

The k-Schur functions were first introduced by Lapointe, Lascoux and Morse in the hopes of refining the expansion of Macdonald polynomials into Schur functions. Recently, an alternative definition for k-Schur functions was given by Lam, Lapointe, Morse, and Shimozono as the weighted generating function of starred strong tableaux. This definition has been shown to correspond to the Schubert basis for the affine Grassmannian and at t=1 it is equivalent to the k-tableaux characterization of Lapointe and Morse. Using this new definition for k-Schur functions, we prove the symmetry and Schur positivity of k-Schur functions combinatorially using the theory of dual equivalence graphs. Central to our proof is our discovery of an analog of dual equivalence for the affine symmetric group. We also make connections between k-Schur functions and both LLT and Macdonald polynomials by comparing the graphs for these functions.
&bull  ~ 35 pages  &bull

Towards a kicking basis for Garsia-Haiman modules.

In the early 1990s, Garsia and Haiman conjectured that the dimension of the Garsia-Haiman module indexed by a partition of n is n!, and they showed that the resolution of this conjecture implies the Macdonald Positivity Conjecture. Haiman proved these conjectures in 2001 using algebraic geometry, but the question remains to find an explicit basis for the modules which would give a simple proof of the dimension. Using the theory of Orbit Harmonics developed by Garsia and Haiman, we present a "kicking basis" for Garsia-Haiman modules indexed by any partition not containing the partition (3,3,2).
&bull  ~ 20 pages  &bull

(with Adriano Garsia) A kicking basis for the two column Garsia-Haiman modules. 21st Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), pp. 103--114, Discrete Math. Theor. Comput. Sci. Proc., AJ, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, France, 2009.

In the early 1990s, Garsia and Haiman conjectured that the dimension of the Garsia-Haiman module indexed by a partition of n is n!, and they showed that the resolution of this conjecture implies the Macdonald Positivity Conjecture. Haiman proved these conjectures in 2001 using algebraic geometry, but the question remains to find an explicit basis for the modules which would give a simple proof of the dimension. Using the theory of Orbit Harmonics developed by Garsia and Haiman, we present a "kicking basis" for Garsia-Haiman modules indexed by a two-column partition. arXiv:0905.2333

(with Persi Diaconis and K. Soundararajan) Riffle shuffles of a deck with repeated cards. 21st Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), pp. 89--103, Discrete Math. Theor. Comput. Sci. Proc., AJ, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, France, 2009.

We study the Gilbert-Shannon-Reeds model for riffle shuffles and ask 'How many times must a deck of cards be shuffled for the deck to be in close to random order?'. In 1992, Bayer and Diaconis gave a solution which gives exact and asymptotic results for all decks of practical interest, e.g. a deck of 52 cards. But what if one only cares about the colors of the cards or disregards the suits focusing solely on the ranks? More generally, how does the rate of convergence of a Markov chain change if we are interested in only certain features? Our exploration of this problem takes us through random walks on groups and their cosets, discovering along the way exact formulas leading to interesting combinatorics, an 'amazing matrix', and new analytic methods which produce a completely general asymptotic solution that is remarkable accurate. arXiv:0905.4698

(with Persi Diaconis and K. Soundararajan) A rule of thumb for riffle shuffling. To appear in Ann. Appl. Probab.

We study how many riffle shuffles are required to mix n cards if only certain features of the deck are of interest, e.g. suits disregarded or only the colors of interest. For a wide variety of features, the number of shuffles drops from 3/2 log_2 n to log_2 n. We derive closed formulae and an asymptotic `rule of thumb' formula which is remarkably accurate. arXiv:0908.3462

A generalized major index statistic. Seminaire Lotharingien de Combinatoire 60 (2008), Art. B60c, 13 pp. (electronic).

Inspired by the k-inversion statistic for LLT polynomials, we define the k-inversion number and k-descent set for words. Using these, we define a new statistic on words, called the k-major index, that interpolates between the major index and inversion number. We give a bijective proof that the k-major index is equidistributed with the major index, generalizing a classical result of Foata and rediscovering a result of Kadell. Inspired by recent work of Haglund and Stevens, we give a partial extension of these definitions and constructions to standard Young tableaux. Finally, we give an application to Macdonald polynomials made possible by connections with LLT polynomials. arXiv:0807.0433

A combinatorial realization of Schur-Weyl duality via crystal graphs and dual equivalence graphs. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), pp. 141--152, Discrete Math. Theor. Comput. Sci. Proc., AJ, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, France, 2008.
&bull  slides from MSRI Workshop (01/2008)  &bull

For any polynomial representation of the special linear group, the nodes of the corresponding crystal may be indexed by semi-standard Young tableaux. Under certain conditions, the standard Young tableaux occur, and do so with weight 0. Standard Young tableaux also parametrize the vertices of dual equivalence graphs. Motivated by the underlying representation theory, in this paper, we explain this connection by giving a combinatorial manifestation of Schur-Weyl duality. In particular, we put a dual equivalence graph structure on the 0-weight space of certain crystal graphs, producing edges combinatorially from the crystal edges. The construction can be expressed in terms of the local characterizations given by Stembridge for crystal graphs and the author for dual equivalence graphs. arXiv:0804.1587

The Schur expansion of Macdonald polynomials. Submitted.

Building on Haglund's combinatorial formula for the transformed Macdonald polynomials, we provide a purely combinatorial proof of Macdonald positivity using dual equivalence graphs and give a combinatorial formula for the coefficients in the Schur expansion. Preprint.
&bull  slides from BIRS Workshop (09/2007)  &bull

Dual Equivalence Graphs I: A combinatorial proof of LLT and Macdonald positivity. Submitted.

We make a systematic study of a new combinatorial construction called a dual equivalence graph. We axiomatize these graphs and prove that their generating functions are symmetric and Schur positive. By constructing a graph on ribbon tableaux which we transform into a dual equivalence graph, we give a combinatorial proof of the symmetry and Schur positivity of the ribbon tableaux generating functions introduced by Lascoux, Leclerc and Thibon. Using Haglund's formula for the transformed Macdonald polynomials, this also gives a combinatorial formula for the Schur expansion of Macdonald polynomials. arXiv:1005.3759

Dual equivalence graphs, ribbon tableaux and Macdonald polynomials. Ph.D. Thesis, UC Berkeley, 2007.
My dissertation received the 2007 Herb Alexander Prize for outstanding dissertations in pure mathematics at UC Berkeley.

We make a systematic study of a new combinatorial construction called a dual equivalence graph. We axiomatize such constructions and prove that the generating functions of these graphs are Schur positive. We construct a graph on k-ribbon tableaux which we conjecture to be a dual equivalence graph, and we prove the conjecture for k at most 3. This implies the Schur positivity of the k-ribbon tableaux generating functions introduced by Lascoux, Leclerc and Thibon. From Haglund's formula for the transformed Macdonald polynomials, this has the further consequence of a combinatorial expansion of the Macdonald-Kostka polynomials indexed by a partition with at most 3 columns.
&bull  qualifying exam syllabus  &bull  3 page synopsis  &bull  9 page extended abstract  &bull