# 321-avoiding permutations and their superpatterns

My co-authors and I have another paper on superpatterns up on the arXiv, "Small Superpatterns for Dominance Drawing", arXiv:1310.3770. It's a follow-up to our Graph Drawing paper, which used superpatterns for 213-avoiding permutations to improve the size of universal point sets for straight-line planar drawing. This one instead considers a different drawing style, dominance drawing, which led us to the problem of finding small superpatterns for 321-avoiding permutations.

If you shuffle a deck of cards (just once, using a single riffle) then the permutation you get will be 321-avoiding. (It will also avoid some other patterns as well.) 213-avoiding and 321-avoiding permutations are very similar to each other in many ways; for instance, there are the same number of them (the Catalan numbers). However, their behavior with respect to superpatterns is not so similar, and we were able to find significantly smaller superpatterns in this case, with size proportional to \( n^{3/2} \) instead of \( n^2 \).

This will be appearing at ANALCO, which unlike previous years is concurrent with SODA instead of prior to it. So if you're going to SODA anyway, check out the program; you might find some interesting side talks.