CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Plenary Speakers

MIGUEL ANJOS, CRC in Discrete Nonlinear Optimization in Engineering, Ecole Polytechnique de Montreal
Conic Optimization: Relaxing at the Cutting Edge  [PDF] [SLIDES]

The relationship between nonlinear conic optimization and discrete optimization has been the subject of intense research since the advent in the mid-1990s of the maximum-cut approximation algorithm of Goemans and Williamson that hinges on the use of a semidefinite relaxation. Semidefinite relaxations, and other nonlinear conic relaxations, have since been constructed for various discrete optimization problems. This research has led to important theoretical and computational advances. In this presentation we survey these advances, primarily from a computational standpoint, for graph partitioning problems and for ordering problems. For several versions of these problems, the use of conic relaxations within an enumeration scheme is the basis of the state-of-the-art algorithms. The effectiveness of these algorithms critically depends on the judicious use of cuts to improve the bounds. We present the cutting edge in linear and nonlinear techniques to iteratively tighten the conic relaxations.

ANNE CONDON, University of British Columbia
Programming Molecules  [PDF] [SLIDES]

Programs that execute within cells or that create intricate nanoscale structures are a reality, implemented using DNA molecules. As the scale and variety of DNA programs expand, a rich theory of molecular programming is emerging.

Chemical reactions are a natural programming language, but programming molecules is tricky! For example, reactions execute asynchronously, it's hard to control counts of input molecular species, and challenging to "recycle" species so that the volume (space) of a computation is minimized. In this talk I'll describe results on the power and limitations of programming with chemical reactions, and some open problems in this fascinating field.

REINHARD DIESTEL, Hamburg University
From pretty pictures to infinite matroids via graph homology: a surprising connection  [PDF] [SLIDES]

It has recently (2004--11) been shown that the first homology of locally finite infinite graphs $G$, such as Cayley graphs of finitely generated groups, is best captured by their so-called `topological cycle space', an ${\mathbb F}_2$ vector space generated by possibly infinite sums from the edge sets of topological circles in the end-compactification of $G$.

Solving a 1966 problem of Rado, we recently (2010) proved that infinite matroids with duality can be axiomatized much like finite matroids. This opens up new possibilities in infinite matroid theory that had so far been precluded by the lack of duality, a concept central to finite matroid theory. All infinite matroids now have duals, including such basic finitary matroids as vector spaces of any dimension, or the finite-bond and cycle matroids of an infinite graph.

In studying those duals, we came across a tantalizing connection between graphic matroids and the graph homology outlined above: a connection that points to some hidden theory underlying both, which is still largely mysterious.

CHERYL PRAEGER, The University of Western Australia
Local transitivity properties of graphs and pairwise transitive designs  [PDF] [SLIDES]

One of the earliest triumphs in applying the finite simple group classification in algebraic graph theory was the characterisation of finite distance transitive graphs. Recent work by Devillers, Giudici, Li and myself focuses on a generalisation of this class of graphs: locally $s$-distance transitive graphs where ordered vertex-pairs, with given first vertex and at a given distance at most $s$, are equivalent under automorphisms. One basic type of example is closely linked with the existence of very symmetrical point-line incidence structures which we call pairwise transitive designs. I will trace these developments and their links.

VICTOR REINER, Univ. of Minnesota
Catalan numbers, parking functions, and invariant theory  [PDF] [SLIDES]

Catalan numbers and parking functions are well-studied combinatorial objects with many wonderful properties. There are ways to view them as associated to the symmetric group, viewed as a reflection group, and then generalize them to all finite real reflection groups. We will discuss how some of their wonderful properties generalize, and how invariant theory plays a role.

CARLA SAVAGE, North Carolina State University
Generalized Inversion Sequences  [PDF] [SLIDES]

An inversion sequence is a sequence of positive integers $(e_1, ..., e_n)$ satisfying $e_k < k$. Inversion sequences are used in various ways to encode permutations, for example, Lehmer codes and inversion tables.

In this talk we describe a generalization of inversion sequences, with corresponding statistics derived from the theory of lecture hall partitions. An s-inversion sequence $(e_1, ..., e_n)$ satisfies $e_k < s_k$, where $s=(s_1, ..., s_n)$ is an arbitrary sequence of positiive integers.

These s-inversion sequences provide both combinatorial and geometric models for generalizations of permutations. We will show that s-inversion sequences can be used to unify and generalize results about permutations, Eulerian polynomials, lattice points in polyhedra, partition generating functions, Coxeter groups, and lecture hall partitions.

ROBERT SEDGEWICK, Princeton University
"If You Can Specify It, You Can Analyze It" ---The Lasting Legacy of Philippe Flajolet  [PDF] [SLIDES]

The "Flajolet School" of the analysis of algorithms and combinatorial structures is centered on an effective calculus, known as analytic combinatorics, for the development of mathematical models that are sufficiently accurate and precise that they can be validated through scientific experimentation. It is based on the generating function as the central object of study, first as a formal object that can translate a specification into mathematical equations, then as an analytic object whose properties as a function in the complex plane yield the desired quantitative results. Universal laws of sweeping generality can be proven within the framework, and easily applied. Standing on the shoulders of Cauchy, Polya, de Bruijn, Knuth, and many others, Philippe Flajolet and scores of collaborators developed this theory and demonstrated its effectiveness in a broad range of scientific applications. Flajolet's legacy is a vibrant field of research that holds the key not just to understanding the properties of algorithms and data structures, but also to understanding the properties of discrete structures that arise as models in all fields of science. This talk will survey Flajolet's story and its implications for future research.

Induced Matchings, Arithmetic Progressions and Communication  [PDF] [SLIDES]

Extremal Combinatorics is one of the central branches of discrete mathematics which deals with the problem of estimating the maximum possible size of a combinatorial structure which satisfies certain restrictions. Often, such problems have also applications to other areas including Theoretical Computer Science, Additive Number Theory and Information Theory. In this talk we will illustrate this fact by several closely related examples focusing on a recent work with Alon and Moitra.

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 Memorial University of Newfoundland