Monday, February 1, 3pm ET (8pm GMT, 9am Tue NZDT)
Meike Hatzel, TU Berlin
Perfect Matching Width and a grid minor theorem for bipartite graphs

Abstract:

The grid theorem stating that a graph has small treewidth if and only if it contains no large grid as a minor is known to be an important step in the work by Robertson and Seymour leading to the graph structure theorem. Norine conjectured that a similar property holds on graphs in which every edge is contained in a perfect matching for a bipartite grid version and a width parameter called Perfect matching width. This talk presents a partial solution to this conjecture. We prove a grid theorem using perfect matching width on bipartite graphs by showing that it is equivalent to the directed treewidth and thus we can transfer the directed grid theorem by Kawarabayashi and Kreutzer.

Past online talks:

• Jan 11: Stephan Kreutzer, Directed tangles
• Jan 18: Kazuhiro Nomoto – $I_t$-free, triangle-free binary matroids
• Jan 25: Liana Yepremyan – Ryser’s conjecture and more
• Feb 1: Meike Hatzel – Perfect Matching Width and a grid minor theorem for bipartite graphs
• Feb 8: David Wood – Hypergraph Colouring via Rosenfeld Counting
• Feb 22: Geoff Whittle, Monotone orders of connectivity functions
• Mar 1: O-joung Kwon, A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
• Mar 8: Nick Brettell, The excluded minors for 2-regular matroids, and for Hydra-5-representable matroids
• Mar 15: Ben Moore, A density bound for triangle-free 4-critical graphs
• Mar 22: Peter Nelson, Formalizing matroids
• Mar 29: Charles Semple, Matroids with wheel- and whirl-like properties
• Apr 5: Raphael Steiner, Directed graphs: Substructures and Coloring
• Apr 12: Daryl Funk – The class of bicircular matroids has only a finite number of excluded minors
• Apr 19: Daniel I. Bernstein – Rigidity of symmetry-forced frameworks
• May 10: Sophie Spirkl – The complexity of list-5-colouring of H-free graphs
• May 17: Bertrand Guenin – Graphs with the same even cycles
• May 31: Dan Slilaty – Orientations of golden-mean matroids
• Jun 7: Abhinav Shantanam – Pancyclicity in 4-connected planar graphs
• Jun 14: Youngho Yoo – Packing A-path of length 0 modulo a prime
• Jun 21: Sebastian Wiederrecht – Even Circuits in Oriented Matroids
• Jun 28: Carla Groenland – Universal Graphs and Labelling Schemes
• July 5: Shayla Redlin – Extensions of cliques
• July 12: Eimear Byrne – Some recent results on q-matroids
• July 19: Natasha Morrison – Uncommon systems of equations
• July 26: Matthew Sullivan – Rotation Systems and Simple Drawings of $K_n$
• Sept 14: Evelyne Smith-Roberge – A local choosability theorem for planar graphs
• Sept 21: Zach Walsh – New lift matroids for group-labeled graphs
• Sept 28: Jim Geelen – Is this Ramsey’s Theorem for Matroids?
• Oct 5: Jagdeep Singh – 2-Cographs and Binary Comatroids
• Oct 19: Tara Fife – (Minimal) Tropical Basis for Matroids
• Oct 26: Natalie Behague – Subgraph Games in the Semi-random Graph Process
• Nov 2: Relinde Jurrius – The direct sum of q-matroids
• Nov 9: Dillon Mayhew – Matroids that are transversal and cotransversal
• Nov 16: Nathan Bowler – Infinite Maker-Breaker games
• Nov 23: Tom Kelly – Coloring hypergraphs of small codegree, and a proof of the Erdős–Faber–Lovász conjecture
• Nov 30: Rutger Campbell – Counting Well-Quasi-Ordered Down Sets
• Dec 7: Michael Wigal – Approximating TSP walks in subcubic graphs
• Dec 14: Open Problem Session

Blog Posts

• Matroids on graphs in applied algebraic geometry
• The excluded minors for GF(5)-representability on 10 elements
• Oriented matroid localizations
• The Sylvester-Gallai Theorem
• A breakthrough on the matroid intersection conjecture
• On a Cantor-Bernstein property of infinite matroids