Tuesday, Dec 7, 3pm ET (8pm GMT, 9am Wed NZDT)
Michael Wigal, Georgia Tech
Approximating TSP walks in subcubic graphs

Abstract:

We will show that if $G$ is a $2$-connected simple subcubic graph on $n$ vertices with $n_2$ vertices of degree $2$, then $G$ has a TSP walk of length at most $5n/4 + n_2/4 -1$, establishing a conjecture of Dvořák, Kráľ, and Mohar. This upper bound is best possible. In particular, there are infinitely many subcubic (respectively, cubic) graphs whose minimum TSP walks have length $5n/4 + n_2/4 -1$ (respectively, $5n/4 – 2$). Our proof implies a quadratic-time algorithm for finding such a TSP walk, thereby giving a $5/4$ approximation algorithm for the graphic TSP on simple cubic graphs and improving on the previously best known approximation ratio of $9/7$.

Joint work with Youngho Yoo and Xingxing Yu.

Tuesday, Nov 30, 3pm ET (8pm GMT, 9am Wed NZDT)
Rutger Campbell, Institute for Basic Science
Counting Well-Quasi-Ordered Down Sets

Abstract:

For a poset of combinatorial objects under some substructure relation, we characterize when there are countably many well-quasi-ordered down sets.

Tuesday, Nov 23, 3:30pm ET (8:30pm GMT, 9:30am Wed NZDT)
Tom Kelly, University of Birmingham
Coloring hypergraphs of small codegree, and a proof of the Erdős–Faber–Lovász conjecture

Abstract:

The theory of edge-coloring hypergraphs has a rich history with important connections and application to other areas of combinatorics e.g. design theory and combinatorial geometry. A long-standing problem in the field is the Erdős–Faber–Lovász conjecture (posed in 1972), which states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In joint work with Dong Yeap Kang, Daniela Kühn, Abhishek Methuku, and Deryk Osthus, we proved this conjecture for every sufficiently large $n$. Recently, we also solved a related problem of Erdős from 1977 on the chromatic index of hypergraphs of small codegree. In this talk, I will survey the history behind these results and discuss some aspects of the proofs.

Tuesday, Nov 16, 3pm ET (8pm GMT, 9am Wed NZDT)
Nathan Bowler, University of Hamburg
Infinite Maker-Breaker games

Abstract:

Consider a game played on a countably infinite complete graph, in which two players, called Maker and Breaker, alternately claim edges. Maker’s aim is that after infinitely many moves she should have claimed all edges of some infinite complete subgraph, and Breaker’s aim is to prevent this. Marit Emde recently found a winning strategy for Maker in this game. We’ll investigate a number of variants of this basic game, and the kinds of winning strategies Maker and Breaker have in them.