CanaDAM 2015 UniversitÃ© de la Saskatchewan, 1 - 4 juin 2015 www.smc.math.ca//2015f
 english accueil réunion accueil canadam

[PDF]

IRIT DINUR, Weizmann Institute of Science, Israel
Lifting locally consistent partial solutions to a global solution  [PDF]

We are given a collection of (alleged) partial views of a function. We are promised "local consistency", i.e., that the partial views agree on their intersection with probability $\ge p$. The question is whether the partial views can be lifted to a global function $f$, i.e. whether a $p'$ fraction of the partial views agree with $f$ (aka "global consistency").

This scenario captures "low degree tests" and "direct product tests", both studied for constructions of probabilistically checkable proofs and for proving hardness of approximation results.

We will survey known lifting theorems, and some of their applications, and describe some open questions.

DANIELA KÃœHN, University of Birmingham, UK
Decomposition problems for graphs  [PDF]

In this talk, I will discuss recent progress on graph decomposition problems. Here a graph $G$ has an $F$-decomposition if the edges of $G$ can be covered by edge-disjoint copies of $F$. Usually we consider the case when $G$ is a large graph and $F$ is small or sparse.

A fundamental theorem of Wilson states that, for every graph $F$, every sufficiently large clique has an $F$-decomposition, provided that the clique satisfies the necessary divisibility conditions. We extend Wilsonâ€™s theorem to graphs which are allowed to be far from complete (joint work with B. Barber, A. Lo and D. Osthus). In general, this area abounds with open problems â€“ I will discuss some of these and mention some related results.

WILLIAM MARTIN, Worcester Polytechnic Institute, USA
Some problems arising in quantum information theory  [PDF]

In this expository talk, I will select a few topics of current interest in quantum information theory that I think are well-suited to the talents and expertise of many in the Canadian community. My goal is first to state the problems purely in terms of linear algebra and combinatorics, avoiding physics wherever possible, and also to summarize the core results and immediate challenges.

BRENDAN MCKAY, Australian National University, Australia
Some examples of exhaustive graph generation  [PDF]

We give a brief overview of the art of generating graph classes on the computer, with particular attention to avoidance of isomorphs. Our examples will include two recent projects. One is to generate fullerenes without adjacent pentagons (joint with Jan Goedgebeur) and the other is to catalogue all small Turan graphs for collections of short cycles (joint with Narjess Afzaly). In both cases we manage to considerably improve on earlier results.

KAREN MEAGHER, University of Regina, Canada
Algebraic Approaches to the ErdÅ‘s-Ko-Rado Theorem  [PDF]

The ErdÅ‘s-Ko-Rado (EKR) theorem is a famous result that is one of the cornerstones of extremal set theory. This theorem answers the question "What is the largest family of intersecting sets, of a fixed size, from a base set?" This question may be asked for any type of object for which there is some notion of intersection. For example, there have been recent results that prove that a natural version of the EKR theorem holds for permutations, vector spaces, integer sequences, domino tilings, partitions and matchings.

There are many vastly different proofs of these results, some are simply a straight-forward counting argument, others use graph theory and some require nuanced properties of related matrix algebra. In this talk I will show some of the difference proof methods for EKR theorems, with a focus on the more algebraic methods.

DHRUV MUBAYI, University of Illinois at Chicago, USA
Independent sets in hypergraphs  [PDF]

A basic problem in extremal combinatorics is to determine the independence number of a hypergraph. We will consider this question in various contexts. Our results show that the behavior of the independence number of sparse hypergraphs is quite different than the graph case. We will also describe some hypergraph generalizations of the graph Ramsey number R(3,t).

YANN PONTY, CNRS/Ecole Polytechnique, France
RNA Bioinformatics and ensemble dynamic programming  [PDF]

RiboNucleic Acids (RNAs) are fascinating biomolecules which, similarly to DNA, can be encoded as sequences over a four-letter alphabet, and perform a wide array of biological functions. However, unlike DNA, the precise function of a given RNA depends critically on its structure, adopted as the outcome of a folding process. Luckily, this intricate three- dimensional conformation can be adequately abstracted as a (non-crossing) list of contacts, i.e. a discrete combinatorial object.

In this talk, I will emphasize how, over the past three decades, RNA biology has benefited from a continuous and fruitful cross-talk between discrete mathematicians, computer scientists and biochemists. At the center of this conversation lies the concept of dynamic-programming, an algorithmic design technique which solves a combinatorial optimization problem efficiently by taking advantage of a well-chosen decomposition of its search space. Extensions and optimized instances of this technique now allow to address, at a genomic scale, multiple questions related to the analysis of the Boltzmann ensemble and the sequence-structure(-function) relationship. These developments also raise well-defined open questions, motivating further studies of the underlying discrete structures.

ANGELIKA STEGER, ETH ZÃ¼rich, Switzerland
Games on Random Graphs  [PDF]

Playing games has always been a central part of human social interaction. In this talk we study so-called perfect information or combinatorial games. Here, a player has all the information that any other player has when she decides her next move, as for example in chess, Nim or Tic-Tac-Toe. Analyzing such games in a deterministic setting is often quite complicated (which is why we enjoy playing them). On the other hand, moving from a deterministic setup to a randomly generated board often allows the use of different methods, which in turn yield surprising answers. The aim of this talk is to provide an overview of methods and results for various games on random graphs. In particular, we will discuss Maker-Breaker games, Ramsey games, and Achlioptas processes.