Contributed Talks (PDF, 160KB)
Plenary Talks
Dr. Andrea Burgess: The Directed Oberwolfach Problem
The Oberwolfach Problem, originally posed by Ringel in 1967, asks whether n people can be seated at round tables of sizes k1, …, kt, where k1 + ⋯ + kt=n, over successive nights in such a way that each person sits next to each other person exactly once. In other words, does the complete graph Kn admit a 2-factorization in which each 2-factor consists of cycles of lengths k1, …, kt? Over the course of the next six decades, many instances of the Oberwolfach Problem have been solved, including for uniform 2-factors, 2-factors containing exactly two components and bipartite 2-factors. While an asymptotic existence result is known, a complete solution to the Oberwolfach problem remains elusive.
The Oberwolfach Problem has also been extended to the directed case, where we seek to find a 2-factorization of the complete symmetric digraph Kn*. Echoing some of the history of the original problem, instances for which the directed Oberwolfach Problem has been settled include uniform directed 2-factors and directed 2-factors with exactly two components.
In this talk, we give an overview of the history of the Oberwolfach Problem and its directed variant. We then discuss a recent result which completely solves the directed Oberwolfach problem with bipartite 2-factors when the order n is congruent to 2 modulo 4. This is joint work with Peter Danziger and Alice Lacaze-Masmonteil.
Dr. Mohamed Omar: Roots of Combinatorial Polynomials
We discuss why studying roots of combinatorial polynomials plays an important role in understanding the underlying combinatorics of the structures these polynomials encode. We highlight the author’s recent proof that real roots of all-terminal reliability polynomials of simple graphs are dense in [-1,0]U{1}; refining the same theorem proved for multigraphs by Brown and Colbourn (1992).
Dr. Erin Meger: Pursuit-Evasion and Graph Structure
In this talk, we consider the pursuit-evasion game Cops and Robbers. The game is played on a graph between two players: a set of cops and a single robber, who take turns moving along the edges. The cop number of a graph is the minimum number of cops needed to guarantee capture of the robber, meaning they eventually occupy the same vertex. This parameter has been studied on a wide range of graph classes.
The underlying graph structure plays an important role in the cop number. We consider classes of graphs defined by forbidden substructures such as minors or induced subgraphs. A graph G is H-free or H-minor free if G does not contain, respectively, any induced subgraph or minor which is isomorphic to H.
The role of forbidden minors in pursuit-evasion began in Andrae’s work in 1986. For graphs that exclude a fixed minor H, the upper bound for the cop-number is nearly the number of edges in this forbidden minor. More recently Chudnovsky et al. showed that excluding an induced subgraph of P5 yields graphs that have cop number at most 2. This talk presents two new results on both forbidden structure types. For graphs with forbidden minors, we present the necessary decomposition of the minor to bound the cop number. For graphs with path-like constraints, we present a significant improvement on the bound of the cop number.