Abstract: This talk is about two distinct Gray codes. A Gray code is an exhaustive listing of some class of combinatorial objects in which successive objects in the list are required to be close in some sense.

First, we present a new Gray code for combinations that is practical and elegant (Knuth includes it in Volume 4). We represent combinations as bitstrings with s 0's and t 1's, and generate them with a remarkably simple rule: Identify the shortest prefix ending in 010 or 011 (or the entire bitstring if no such prefix exists) and then rotate (shift) it by one position to the right. Since the rotated portion of the string consists of at most four contiguous runs of 0's and 1's, each successive combination can be generated by transposing only one or two pairs of bits. This leads to a very efficient loopless implementation. The Gray code also has a simple and efficient ranking algorithm that closely resembles that of combinations in colex order. For this reason, we have given a nickname to our order: cool-lex! (Research with Aaron Williams.)

Next, we consider Gray codes for column-convex polyominoes, which are polyominoes whose intersections with vertical lines are connected. In the code successive polyominoes differ by the movement of one square. These Gray codes have interesting connections with certain classical distributive lattices studied in algebraic combinatorics, particularly with regard to questions of rank unimodality. (Research with Stirling Chow and Scott Craig.)

Short Bio: Frank Ruskey is one of the foremost experts in the area of generating combinatorial structures. He is the author of the dynamic survey of Venn Diagrams in the Electronic Journal of Combinatorics: see http://www.combinatorics.org/Surveys/ds5/VennEJC.html