CS 269S, Fall 2013: Theory Seminar
Bren Hall, Room 1422, 1pm
October 18, 2013:

Small superpatterns for dominance drawing

Will Devanny

We exploit the connection between dominance drawings of directed acyclic graphs and permutations, in both directions, to provide improved bounds on the size of universal point sets for certain types of dominance drawing and on superpatterns for certain natural classes of permutations. In particular we show that there exist universal point sets for dominance drawings of the Hasse diagrams of width-two partial orders of size O(n^3/2 ), universal point sets for dominance drawings of st-outerplanar graphs of size O(n log n), and universal point sets for dominance drawings of directed trees of size O(n^2 ). We show that 321-avoiding permutations have superpatterns of size O(n^3/2 ), riffle permutations (321-, 2143-, and 2413-avoiding permutations) have superpatterns of size O(n), and the concatenations of sequences of riffles and their inverses have superpatterns of size O(n log n). Our analysis includes a calculation of the leading constants in these bounds.

Joint work with Michael J Bannister and David Eppstein.