CanaDAM 2019
SFU Harbour Centre, May 29 - 31, 2019

Plenary Speakers

FEDERICO ARDILA, San Francisco State University, USA
The geometry of matroids  [PDF]

Matroid theory is a combinatorial theory of independence which has its origins in linear algebra and graph theory, and turns out to have deep connections with many other fields. With time, the geometric roots of the field have grown much deeper, bearing many new fruits.

The geometric approach to matroid theory has recently led to the development of fascinating mathematics at the intersection of combinatorics, algebra, and geometry, and to the solution of long-standing questions. This talk will survey some recent successes.

MARTHE BONAMY, Laboratoire Bordelais de Recherche en Informatique, France
Around Brooks' theorem  [PDF]

In this talk, we will discuss various results around Brooks' theorem: a graph has chromatic number at most its maximum degree, unless it is a clique or an odd cycle. We will consider stronger variants and local versions, as well as the structure of the solution space of all corresponding colorings.

JOHANNES CARMESIN, University of Birmingham, UK
Embedding simply connected 2-complexes in 3-space  [PDF]

We characterise the embeddability of simply connected 2-dimensional simplicial complexes in 3-space in a way analogous to Kuratowski's characterisation of graph planarity, by excluded minors. This answers questions of Lovasz, Pardon and Wagner.

DAVID CONLON, University of Oxford, UK
Around extremal numbers  [PDF]

The extremal number ex$(n, H)$ is the maximum number of edges in an $H$-free graph with $n$ vertices. When $H$ has chromatic number at least three, the extremal number is well understood, but when $H$ is bipartite, the function remains mysterious. Until very recently, the asymptotic behaviour of ex$(n, H)$ was known for only a handful of bipartite graphs. However, the situation has changed dramatically in recent years. In this talk, we will discuss some of this progress.

If time permits, we will also touch upon the related question of counting the number of copies of a fixed bipartite graph in a graph of given density.\Partly based on joint work with Boris Bukh, Oliver Janzer and Joonkyung Lee.

ANNA R. KARLIN, University of Washington, USA
Auctions with interdependent valuations  [PDF]

Most auction theory assumes that the bidders' values for the goods and services being sold do not depend on other bidders' values. The interdependent setting [Milgrom & Weber] goes beyond this to capture the value of resale and the aggregation of information different bidders have about the goods being sold.

In the talk, we will survey research on auction design in interdependent settings and present new results on social welfare maximization in combinatorial auctions for this setting.

Joint work with Alon Eden, Michal Feldman, Amos Fiat and Kira Goldner.

MIKE MOLLOY, University of Toronto
Graph Colouring with the Probabilistic Method  [PDF]

I will overview applications of the probabilistic method to graph colouring problems. This will include uses of entropy compression, a recent variation of the Lovasz Local Lemma. The focus of this talk will be on how to apply the techniques.

PETER NELSON, University of Waterloo
Induced binary submatroids  [PDF]

A binary matroid $M$ can be thought of as a set $X$ of nonzero vectors in an `ambient' vector space $V$ over the field GF$(2)$. Intersecting $X$ with a subspace $W$ of $V$ gives a smaller matroid $N$ with ambient space $W$; we say that $N$ is an induced submatroid of $M$. This gives a rich partial order on binary matroids that is analogous to the induced subgraph order, having its own natural structural and extremal questions with interesting answers. We discuss some new results in this area that concern matroidal analogues of chromatic number, chi-boundedness and claw-free graphs. No knowledge of matroid theory will be assumed.

REKHA THOMAS, University of Washington, USA
Graph Density Inequalities and Sums of Squares  [PDF]

Many results in extremal graph theory can be formulated as inequalities on graph densities. While many inequalites are known,many more are conjectured. A standard tool to establish an inequality is to write the expression whose nonnegativity needs to be certified, as a sum of squares. This technique has had many successes but also limitations. In this talk I will describe new restrictions that show that several simple inequalities cannot be certified by sums of squares. These results extend to the powerful frameworks of flag algebras by Razborov and graph algebras by Lovasz and Szegedy. Joint work with Greg Blekherman, Annie Raymond, and Mohit Singh