CMS/SMC
CanaDAM 2015
University of Saskatchewan, June 1 - 4, 2015 www.cms.math.ca//2015
       

Algorithmic construction of combinatorial objects
Organizer and Chair: Jan Goedgebeur (Ghent University)
[PDF]

GEOFFREY EXOO, Indiana State University
Finding Combinatorial Structures with Simple Heuristics  [PDF]

We outline some simple heuristics for finding combinatorial structures. Our methods have been successfully applied to problems related to unit distance graphs, cages, Ramsey numbers, degree/diameter graphs, various types of codes, and other similar problems. A general approach to finding the right heuristic is described. Recent efforts to extend these methods to the search for large prime numbers and twin primes (joint work with Jeff Kinne) will be discussed.

JAN GOEDGEBEUR, Ghent University
Minimal obstructions to graph coloring  [PDF]

For several graph classes without long induced paths there exists a finite forbidden subgraph characterization for k-colorability. Such a finite set of minimal obstructions allows to provide a "no-certificate" which proves that a graph is not k-colorable.

In this talk we will present a new algorithm for generating all minimal forbidden subgraphs to k-colorability for a given graph class. We will also show how it has been applied to fully characterize the forbidden subgraphs for k-colorability of various classes of graphs without long induced paths.

This is joint work with Oliver Schaudt.

VERONIKA IRVINE, University of Victoria, Department of Computer Science
A Mathematical Model for Lace: Its use in enumerating and generating lace patterns  [PDF]

Bobbin lace is a fibre art form used for over 450 years. A fundamental component of bobbin lace is an alternating braid which we model as the pair $(D,\zeta)$. Here $D$ is a 2-regular directed graph and $\zeta$ is a mapping from the vertices of $D$ to a braid word. We will discuss some interesting properties of the associated directed graphs and demonstrate how lattice paths can be used to exhaustively generate graphs satisfying the lace criteria. With this approach, we have generated millions of patterns, several of which have been rendered by lacemakers worldwide. Joint research with Frank Ruskey.

STANISLAW RADZISZOWSKI, Rochester Institute of Technology
Some computational and theoretical problems for Ramsey numbers  [PDF]

We discuss some computational challenges and related open questions concerning classical Ramsey numbers. We overview known constructive bounds for the difference between consecutive two-color Ramsey numbers. We present what is known about the Ramsey number $R(5,5)$ and discuss the conjecture that $R(5,5)=43$. For the multicolor Ramsey numbers, we focus on the growth of $R_r(k)$ for fixed $k$ (in particular $k=3$), and two concrete conjectured cases, $R(3,3,3,3)=51$ and $R(3,3,4)=30$. Although the main problems we discuss are concerned with concrete cases, and they involve significant computational approaches, there are interesting and important theoretical questions behind each of them.

AARON WILLIAMS, Bard College at Simon's Rock
Recent Results on Necklaces, Lyndon Words, and Universal Cycles  [PDF]

We provide algorithms for ranking and unranking necklaces and Lyndon words in lexicographic order in worst-case $O(n^2)$-time and $O(n^3)$-time respectively. We also provide a new characterization for the existence of universal cycles for sets of strings that are closed under rotation. The first result is joint work with Joe Sawada while the second result is joint work with Brett Stevens.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Saskatchewan