Author Archives: Shayla Redlin Hume

Online Talk: Michael Wigal

Posted on by
Reply

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.

Open Problem Session – Dec 14

Posted on by
Reply

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. Please email by Friday, Dec 10.

More details about the schedule and how to attend will be posted closer to Dec 14.

 – Jim, Peter, and Shayla

 

Online Talk: Tom Kelly

Posted on by
Reply

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.