Algorithmic construction of combinatorial objects
Responsable et prÃ©sident:
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 kcolorability. Such a finite set of minimal obstructions allows to provide a "nocertificate" which proves that a graph is not kcolorable.
In this talk we will present a new algorithm for generating all minimal forbidden subgraphs to kcolorability for a given graph class. We will also show how it has been applied to fully characterize the forbidden subgraphs for kcolorability 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 2regular 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 twocolor 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 worstcase $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.