CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019 canadam.math.ca/2019f
       

Minisymposium in honor of Frank Ruskey's 65th birthday
Org: Torsten Mütze (TU Berlin) et Joe Sawada (University of Guelph)
[PDF]

ALEJANDRO ERICKSON, University of Victoria
Tatami Tilings in a Template for Teaching to Teenagers  [PDF]

A tatami tiling is a covering of a rectangular grid by 1x1 monominoes and 1x2 dominoes such that no four tiles meet. The local restriction imposes a global combinatorial structure that I explored with Frank Ruskey during my PhD. Tatami tilings enable high schoolers to have their own `eureka' moment in mathematics, and prepares them to look fearlessly into an exciting and complex world of exploration and discovery that goes beyond the standard curriculum. We will visit some of our results in tatami tilings in the context of my favourite template for math outreach: `make a mathematical discovery'.

GARY MACGILLIVRAY, University of Victoria
Using combinatorial algorithms to search for golf schedules  [PDF]

Imagine 12 golfers play one round per day, in foursomes, for five days. How can the groups be arranged so that every two players are in the same group approximately the same number of times? In general there are $n$ golfers arranged in $g$ groups for $d$ days. For ``small'' $n$ one can search though all possible schedules by exploiting a 1-1 correspondence with certain $k$-ary sequences. For ``large'' $n$ one can generate possible schedules at random using an unranking algorithm for such sequences. We will describe simple combinatorial algorithms for generating, ranking and unranking the sequences, and computational results.

TORSTEN MÜTZE, TU Berlin
Combinatorial generation via permutation languages  [PDF]

In this talk I present a new and versatile algorithmic framework for generating different classes of combinatorial objects by encoding them as permutations. One of the main applications are pattern-avoiding permutations. Our algorithm provides a unified view on many known results, such as the Steinhaus-Johnson-Trotter algorithm for permutations, the binary reflected Gray code for bitstrings, the Lucas-Roelants-van Baronaigien Gray code for binary trees, Kaye's Gray code for set partitions, and it also yields many new Gray codes, in particular for several classes of rectangulations, also known as floorplans.

Joint work with Liz Hartung, Hung P. Hoang and Aaron Williams.

GARA PRUESSE, Vancouver Island University
Linear Extensions of Posets -- Gray codes, fast generation algorithms, and a long-standing conjecture  [PDF]

Frank Ruskey's work in generating combinatorial objects broke ground in a to that point barely explored area, producing algorithms of elegance and practical value. In this talk we survey the progress made on the problem of generating the linear extensions of posets. We review the state of the art, present some previously unpublished results, and explore the status of Ruskey's conjecture, posed in Discrete Mathematics in 1988, which states that when the linear extension graph of a poset is balanced -- i.e., its two partite sets are the same size -- then it has a Hamilton cycle.

JOE SAWADA, University of Guelph
From 3/30 on Frank's midterm to a career in Academia  [PDF]

Beer and Basketball. The classic (and rather obvious) solution to one of Frank's decryption questions. Soon after solving this gem, as an early graduate student of Frank's, I was put to work on some combinatorial generation problems related to rotational equivalence. The objects included necklaces, Lyndon words, de Bruijn sequences, chord diagrams, and many more. Now 20+years later, these objects are still fascinating and paying the bills! I will recount some of the results done in collaboration with Frank, along with some future directions and open problems.