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.

Monday, February 8, ****5pm ET**** (10pm GMT, 11am Tue NZDT)
David Wood, Monash University
Hypergraph Colouring via Rosenfeld Counting

Abstract:

The Lovász Local Lemma is a powerful probabilistic technique for proving the existence of combinatorial objects. It is especially useful for colouring graphs and hypergraphs with bounded maximum degree. This talk describes a general theorem for colouring hypergraphs that in many instances matches or slightly improves upon the bounds obtained using the Lovász Local Lemma. Moreover, the theorem shows that there are exponentially many colourings. The elementary and self-contained proof is inspired by a recent result for nonrepetitive colourings by Rosenfeld [2020]. We apply our general theorem in the setting of proper hypergraph colouring, proper graph colouring, independent transversals, star colouring, nonrepetitive colouring, frugal colouring, Ramsey number lower bounds, and for k-SAT. This is joint work with Ian Wanless [arXiv:2008.00775].

Monday, January 25, 3pm ET (8pm GMT, 9am Tue NZDT)
‪Liana Yepremyan‬, LSE and UIC
Ryser’s conjecture and more

Abstract:

A Latin square of order $n$ is an $n \times n$ array filled with $n$ symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser, Brualdi and Stein from 60s which says that every Latin square of order $n\times n$ contains a transversal of order $n-1$. A closely related problem is 40 year old conjecture of Brouwer that every Steiner triple system of order $n$ contains a matching of size $(n-4)/3$. The third problem we’d like to mention asks how many distinct symbols in Latin arrays suffice to guarantee a full transversal? In this talk we discuss a novel approach to attack these problems.

Joint work with Peter Keevash, Alexey Pokrovskiy and Benny Sudakov.