Monday, March 15, 3pm ET (7pm GMT, 8am Tue NZDT)
Benjamin Moore, University of Waterloo
A density bound for triangle free 4-critical graphs

Zoom: https://us02web.zoom.us/j/89998025625
Password: email rose.mccarty ~at~ uwaterloo ~.~ ca if you need the password

Abstract:

Carsten Thomassen showed that every girth 5 graph embeddable in the torus or projective plane is 3-colourable. A complementary result of Robin Thomas and Barrett Walls shows that every girth 5 graph embedded in the Klein bottle is 3-colourable.

I’ll show neither the embeddability condition nor the girth 5 condition is needed in the above theorems by showing that every triangle-free 4-critical graph has average degree slightly larger than 10/3.

This is joint work with Evelyne Smith Roberge.

Monday, March 8, 3pm ET (8pm GMT, 9am Tue NZDT)
Nick Brettell‬, Victoria University of Wellington
The excluded minors for 2-regular matroids, and for Hydra-5-representable matroids

YouTube: https://youtu.be/clkv5nZC2qo

Abstract:

The 2-regular matroids are a generalisation of regular matroids (which are representable over all fields), and near-regular matroids (which are representable over all fields of size at least three). Hydra-5-representability characterises matroids with precisely six inequivalent representations over GF(5). I will present the following recent result: any excluded minor for the class of 2-regular matroids, or for Hydra-5-representable matroids, has at most 17 elements. In fact, we can say more about potential excluded minors with 16 or 17 elements. This leads us tantalisingly close to an excluded-minor characterisation for these two classes. In this talk, I will give some background to why these classes are of interest, discuss the long road towards proving this result, give some key ideas from the argument, and discuss where to from here.

Joint work with James Oxley, Charles Semple, and Geoff Whittle.

Monday, March 1, *****5pm ET***** (10pm GMT, 11am Tue NZDT)
O-joung Kwon, Incheon National University
A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

Abstract:

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles.

A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least $\ell$, cycles of length $p$ modulo $q$, cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties.

This is joint work with J. Pascal Gollin, Kevin Hendrey, Ken-ichi Kawarabayashi, and Sang-il Oum.

Monday, February 22, 3pm ET (8pm GMT, 9am Tue NZDT)
Geoff Whittle, Victoria University of Wellington
Monotone orders of connectivity functions

(Joint with Jasmine Hall and Susan Jowett)

Abstract:

A connectivity function is a symmetric submodular set function. Branch width of graphs, carving width of graphs, and branch width of matroids are all determined by connectivity functions associated with vertex connectivity in graphs, edge connectivity in graphs and connectivity in matroids respectively. A natural problem is to bound the size of structures that are “minimal” with respect to having a given branch width, where what is meant by minimal depends on the notion of substructure that one has in mind. In the talk I will discuss a general theorem on connectivity functions that gives sufficient conditions to bound the size of such minimal structures in a variety of situations.