Tuesday, Dec 7, 3pm ET (8pm GMT, 9am Wed NZDT)
Michael Wigal, Georgia Tech
Approximating TSP walks in subcubic graphs
Password: email shaylaredlin ~at~ gmail ~.~ com (The password is the same format as usual, but first instead of last.)
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.
The organizers of the Graphs and Matroids Seminar would like to invite you to participate in our Open Problem Session!
The session will take place on Tuesday, December 14 from 1:30 to 4:00pm EST with social time afterwards on Gather Town. For each problem, we’ll have ~5 minutes for the presentation followed by ~5 minutes for discussion. We’re planning to have two sessions of about an hour each with a break in between.
Call for presenters: If you would like to present an open problem, please email Shayla (shaylaredlin at gmail dot com) and let us know if you would prefer presenting in the first hour or the last hour of the session.
More details about the schedule and how to attend will be posted closer to Dec 14.
– Jim, Peter, and Shayla
Tuesday, Nov 30, 3pm ET (8pm GMT, 9am Wed NZDT)
Rutger Campbell, Institute for Basic Science
Counting Well-Quasi-Ordered Down Sets
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
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.