Scheduled presentations

• Jenny, Sorting and preimages of pattern classes. Wednesday, May 16.
• Dan, Sorting with two stacks in parallel. Thursday, May 18, at 1:15 in Kemeny 120. (Note: this is the Combinatorics Seminar time).
• Elizabeth, Simple permutations and pattern restricted permutations. Monday, May 21.
• Zach, Counting Reduced Decompositions. Monday, May 21. Here is a link to the applet.
• Kassie, Counting permutations with given cycle structure and descent set. Wednesday, May 23.
• Natasha, Search games. Wednesday, May 23.
• Nathan, Infinite antichains on permutations. Friday, May 25.
• Jonathan, Simple permutations and algebraic generating functions. Friday, May 25.
• Megan, Permutation tableaux. Wednesday, May 30.

A few suggested topics for student presentations

• [V.R. Pratt, Computing permutations with double-ended queues, parallel stacks and parallel queues, Proc. ACM Symp. Theory of Computing 5 (1973), 268–277.]
  This is a classic paper that characterizes permutations that can be sorted by a dequeue (i.e., a double ended queue, where one can push or pop from either end). These permutations are characterized as those avoiding an infinite set A of patterns. The set A was the first published example of an infinite antichain in the pattern containment psoet. The enumeration of dequeue-sortable permutations remains unsolved.
  Here is what Peter Doyle said about this paper: "I've been reading this paper by Vaughan Pratt. I love the way he writes! It reminds me of the way I write. And yes, nothing gives me more pleasure than rereading stuff I've written, and admiring the author's sense of humor. Well, almost nothing."

• [D. Spielman and M. Bona, An infinite antichain on permutations, Electron. J. Combin. 7 (2000), #N2.]
  This short paper gives another construction of an infinite antichain in the pattern containment poset.

• [A. Claesson and H. Ulfarsson, Sorting and preimages of pattern classes, preprint, available here]
  This is one of the most recent papers about sorting and pattern-avoiding permutations. Among other things, it deals with West-k-stack-sortable permutations, which, defined by Julian West in 1990, are those permutations that can be sorted by k passes through a stack whose operations are forced (by the algorithm for sorting 231-avoiding permutations).

• [V. Vatter and S. Waton, On points drawn from a circle, Electron. J. Combin. 18 (2011), P223].
  This paper characterizes in terms of pattern avoidance the set of permutations that can be obtained from drawing points on a circle. It also enumerates these permutations by length.

• [M. Albert, M. Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (2005), 1-15.]
  This paper proves that every subclass of the separable permutations has an algebraic generating function.

• [Z. Stankova, Frobidden subsequences, Discrete Math. 132 (1994), 291-316.]
  This paper proves that the patterns 4132 and 3142 are Wilf-equivalent.

• [I. Le, Wilf classes of pairs of permutations of length 4, Electron. J. Combin. 12 (2005), #R25.]
  This paper, which is the result of an REU program, finds the generating function for the class Av(1342,2143) that you used in Problem Set 2.

• [M. Albert, M. Elder, A. Rechnitzer, P. Westcott and M. Zabrocki, On the Stanley–Wilf limit of 4231-avoiding permutations and a conjecture of Arratia, Adv. Appl. Math. 36 (2006), 96-105.]
  This paper shows that the growth rate of the pattern 1324 is greater than 9.47, thus disproving a conjecture of Arratia that the growth rate of any pattern of length k is at most (k-1)^2.

• [M. Albert, M. Atkinson, V. Vatter, Counting 1324,4231-avoiding permutations, Electron. J. Combin. 16 (2009), #R135.]
  This paper enumerates permutations avoiding both 1324 and 4231 by giving their generating function, which is rational.

• [V. Vatter, Small permutation classes, Proceedings of the LMS 103 (2011), 879–921.]
  This paper studies permutation classes with smal growth rates, characterizing all the possible growth rates below a certain value.

• [E. Steingrimsson and L. Williams, Permutation tableaux and permutation patterns, J. Combin. Theorey Ser A 114 (2007), 211-234.]

• [E. Steingrimsson and B. Tenner, The Mobius function of the permutation pattern poset, J. Comb. 1 (2010), 39-52.]

Last updated June 17, 2015 12:56:59 EDT