Title: 3-Connected binary matroids with no $P_9$-minor
Speaker: Haidong Wu
Abstract: Kuratowski’s Theorem states that a graph is planar if any only if it has no minor that is isomorphic to $K_{3,3}$ or $K_5$. Mayhew, Royle and Whittle characterize internally 4-connected binary matroids with no $M(K_{3,3})$-minor. Oxley characterizes 3-connected binary matroids without any $P_9$- or $P_9^*$-minor. We first determine internally 4-connected binary matroids with no $P_9$-minor. Using this we characterize 3-connected binary matroids with no $P_9$-minor. This preliminary result is joint work with Guoli Ding.
Title: Highly connected matroids in minor-closed classes.
Speaker: Jim Geelen
Abstract: With Bert Gerards and Geoff Whittle we have a structure theorem for any minor-closed class of matroids over a given finite field. That result simplifies considerably when one restricts attention to sufficiently connected matroids. More surprisingly, we can characterize the sufficiently connected matroids in the class exactly.
Title: Inequivalent representations of highly connected matroids
Speaker: Tony Huynh
Abstract: We prove that for each finite field F, every sufficiently connected matroid has only a bounded number of inequivalent F-representations. We obtain this result via a chain theorem for highly connected matroids, which we believe is new even when restricted to graphs. This theorem will be used in the recently announced proof of Rota’s Conjecture by Geelen, Gerards and Whittle.
This is joint work with Jim Geelen, Bert Gerards and Stefan van Zwam.
Title: Combinatorial limits and matroid theory
Speaker: Daniel Kral
Abstract: The theory of combinatorial limits keeps attracting a substantial amount of attention. The theory has developed separately for dense structures (such as graphs with quadratically many edges) and sparse structures (such as graphs with bounded degrees). Nesetril and Ossona de Mendez introduced a notion of first order convergence as an attempt to bridge the realms of the notions of dense and sparse convergence. In the talk, we will first survey concepts from the theory of combinatorial limits and we will then present results related to the first order convergence of matroids. Specifically, we will show that every first order convergent sequence of matroids with bounded branch-depth representable over a fixed finite field has a modeling, i.e. there exists an infinite matroid that quantitatively has the same first order properties as the matroids in the sequence.
This talk is based on joint work with Frantisek Kardos, Anita Liebenau and Lukas Mach.
Title: Enumeration of $2$-Polymatroids on up to Seven Elements
Speaker: Thomas J. Savitsky
Abstract: A theory of single-element extensions of integer polymatroids analogous to that of matroids is developed. We present an algorithm to generate a catalog of $2$-polymatroids, up to isomorphism. When we implemented this algorithm on a computer, obtaining all $2$-polymatroids on at most seven elements, we discovered the surprising fact that the number of $2$-polymatroids on seven elements fails to be unimodal in rank.
Title: Splitters and Decomposers for Binary Matroids
Speaker: Sandra Kingan
Abstract: Let $\mathcal{M}$ denote the class of binary matroids with no minors isomorphic to $M_1, \dots, M_k$. A splitter $N$ for $\mathcal{M}$ is a 3-connected matroid such that no 3-connected matroid in $\mathcal{M}$ has a proper $N$-minor. A 3-decomposer $N$ for $\mathcal{M}$ is a 3-connected matroid with a non-minimal exact 3-separation $(A, B)$ such that any matroid $M$ in $\mathcal{M}$ with an $N$-minor has a
3-separation $(X, Y)$ such that $A\subseteq X$ and $B\subseteq Y$. Splitters and 3-decomposers capture the structure present in excluded minor classes. We characterize classes of binary matroids using splitters and 3-decomposers.
Title: Biased graphs with no two vertex-disjoint unbalanced cycles.
Speaker: Irene Pivotto
Abstract: Both frame and lift matroids arise from biased graphs. A biased graph is a graph with a distinguished set of cycles (called balanced) with the property that any theta subgraph does not contain exactly two balanced cycles. Examples of frame and lift matroids are graphic matroids, bicircular matroids, even cycle matroids, and Dowling geometries.
The lift and frame matroid of a given biased graph coincide exactly when the biased graph has no two vertex-disjoint unbalanced cycles (unbalanced cycles are cycles that are not balanced). We give a complete characterisation of the structure of biased graphs with no two vertex-disjoint unbalanced cycles.
This is joint work with Rong Chen.
Title: Positroids, non-crossing partitions, and positively oriented matroids
Speaker: Federico Ardila
Abstract: We investigate the role that non-crossing partitions play in the study of positroids, a class of matroids introduced by Postnikov. We prove that every positroid can be constructed uniquely by choosing a non-crossing partition on the ground set, and then freely placing the structure of a connected positroid on each of the blocks of the partition. We use this to enumerate connected positroids, and we prove that the probability that a positroid on $[n]$ is connected equals $1/e^2$ asymptotically. We also prove da Silva’s 1987 conjecture that any positively oriented matroid is a positroid; that is, it can be realized by a set of vectors in a real vector space. It follows from this result that the positive matroid Grassmannian (or positive MacPhersonian) is homeomorphic to a closed ball.
This is joint work with Felipe Rincón (Warwick) and Lauren Williams (Berkeley).
Title: On Maximum-sized Golden-mean Matroids
Speaker: Michael Welsh
Abstract: A rank-$r$ simple matroid is maximum-sized in a class if it has the largest number of elements out of all simple rank-$r$ matroids in that class. Golden-mean matroids are matroids that are representable over the golden-mean partial field. Equivalently, a golden-mean matroid is a matroid that is representable over $GF(4)$ and $GF(5)$.
Archer conjectured in 2005 that there are three families of maximum-sized golden-mean matroids. Proving Archer’s conjecture appears to be much more difficult than proving any of the existing maximum-sized characterisations.
In this talk, we consider golden-mean matroids that have a spanning clique. We will outline a proof of Archer’s conjecture within this class. It is anticipated that this result will lead to a proof of the conjecture for golden-mean matroids of sufficiently high rank.
Speaker: João Paulo Costalonga
Abstract: We prove the following splitter theorem for graphs and its generalization for matroids: Let $G$ and $H$ be $3$-connected simple graphs such that $G$ has an $H$-minor and $k:=|V(G)|-|V(H)|\ge 2$. Then there are sets $X_1,\dots,X_n\subseteq E(G)$ such that $n\ge \left\lfloor(1/2)(k+3)\right\rfloor$, each $G/X_i$ is a $3$-connected graph with an $H$-minor, each $X_i$ is a singleton set or the edge-set of a triangle of $G$ with $3$ degree-$3$ vertices and $X_1\cup\cdots\cup X_n$ contains no edge sets of circuits of $G$ other than the $X_i$’s. In particular, this implies that $G$ has a forest with at least $(3/5)\left\lfloor(1/2)(k+3)\right\rfloor$ edges, whose contraction of each edge in $G$ is $3$-connected with an $H$-minor. The main result extends previous ones of Whittle and the author for $k=1,2,3$.
Pre-print on arXiv:1405.6454
Title: Linear relations for a generalized Tutte polynomial
Speaker: Gary Gordon
Abstract: Brylawski proved the coefficients of the Tutte polynomial of a matroid satisfy a set of linear relations. We extend these relations to a generalization of the Tutte polynomial that includes greedoids and antimatroids. This leads to families of new identities for antimatroids, including trees, posets, chordal graphs and finite point sets in $\mathbb{R}^n$. It also gives a “new” linear relation for matroids that is implied by Brylawski’s identities.
Title: Constructive algorithm for path-width and branch-width of matroids
Speaker: Sang-il Oum
Abstract: We will describe a polynomial-time algorithm to construct a path-decomposition or a branch-decomposition of width at most $k$, if it exists, for a matroid represented over a fixed finite field for fixed $k$. Our approach is based on the dynamic programming combined with the idea developed by Bodlaender for his work on tree-width of graphs.
For path-width, this is a new result. For branch-width, the previous work by Hlineny and Oum (Finding branch-decompositions and rank-decompositions, SIAM J. Comput., 2008) was very indirect; their algorithm is based on the upper bound on the size of minor obstructions proved by Geelen et al. (Obstructions to branch-decompositions of matroids, JCTB, 2006) and requires testing minors for each of these obstructions. Our new algorithm does not use minor obstructions. As a corollary, for graphs, we obtain an algorithm to construct a rank-decomposition of width at most $k$ if it exists for fixed $k$. This is a joint work with Jisu Jeong and Eunjung Kim.
Title: Intertwining connectivity in matroids
Speaker: Rong Chen
Abstract: Let $M$ be a matroid and let $Q$, $R$, $S$ and $T$ be subsets of the ground
set such that the smallest separation that separates $Q$ from $R$ has order
$k$ and the smallest separation that separates $S$ from $T$ has order $\ell$.
We prove that if $E(M)-(Q\cup R\cup S\cup T)$ is sufficiently large,
then there is an element $e$ of $M$ such that, in one of $M\backslash e$
or $M/e$, both connectivities are preserved.
Title: Presentations and Extensions of Transversal Matroids
Speaker: Joseph E. Bonin
Abstract: Because of inequivalent representations, a matrix representation of a
matroid can limit which representable extensions of the matroid can be
obtained by adding a column to the matrix. Likewise, a presentation
of a transversal matroid can limit which transversal extensions of the
matroid have presentations that can be obtained by adding a new
element to some of the sets in the original presentation. We examine
presentations of transversal matroids from the perspective of the
collections of transversal extensions they can realize. (This talk
includes joint work with Anna de Mier, UPC, Barcelona).
Title: Infinite Matroid Intersection Conjecture – An Overview
Speaker: Johannes Carmesin
Abstract: After an introduction to Nash-Williams’ Matroid Intersection
Conjecture, we report about our recent progress on this conjecture.
This is joint work with Nathan Bowler.
Title: When matroids guarantee their duals as minors
Speaker: Jesse Taylor
Abstract: Duality is of fundamental importance in matroid theory. In this talk, we answer the following natural question: Which matroids guarantee the presence of their duals as minors when they themselves are present as minors? Specifically, this talk will focus on the problem for 3-connected binary matroids and 3-connected graphic matroids.
Title: Relationships between entropy and matroids
Speaker: Emmanuel Abbe
Abstract: I will talk about connections between entropy and matroids.
In particular, a class of matroids whose rank function is given by the entropy of a subset of random variables, and discuss relationships with representable matroids.
Title: Extension from precoloured sets of edges
Speaker: Ross Kang
Abstract: We consider precolouring extension problems for proper edge-colourings
of graphs, in an attempt to prove stronger versions of Shannon’s and
Vizing’s theorems. We are most interested to extend a colouring from
some arbitrarily precoloured matching. We introduce a natural
conjecture for graphs of bounded maximum degree, and verify it for
several important graph classes. It transpires that this is related to
the list colouring conjecture and other classic notions of
choosability.
Joint work with Katherine Edwards, Jan van den Heuvel and Jean-Sebastien Sereni.
Title: Solving Rota’s Conjecture
Speaker: Geoff Whittle
Abstract: In the talk I will give a broad overview of some aspects of the proof of Rota’s Conjecture. This is joint work with Jim Geelen and Bert Gerards.
Title: Recovering a binary matroid without knowing its big circuits
Speaker: Charles Semple
Abstract: Seymour (1981) conjectured that every $3$-element set in a $4$-connected non-binary matroid is contained in a $U_{2, 4}$-minor. The conjecture is false, but all known counterexamples are circuit-hyperplane relaxations of binary matroids. Prompted by this conjecture and these counterexamples, in this talk we investigate the following question: Given a rank-$r$ binary matroid $M$, can we recover $M$ if we know only its circuits of size at most $r-1$? This is joint work with James Oxley and Geoff Whittle.
Title: Unifying duality theorems for width parameters in graphs and matroids (with Sang-il Oum)
Speaker: Reinhard Diestel
Abstract: We prove a general duality theorem for width parameters in combinatorial structures such as graphs and matroids. It implies the classical such theorems for path-width, tree-width, branch-width and rank-width, and gives rise to new width parameters with associated duality theorems. The dense substructures witnessing large width are presented in a unified way akin to tangles, as orientations of separation systems satisfying certain consistency axioms.
Title: Biased graphs realized by gain functions.
Speaker: Dan Slilaty
Abstract: A biased graph is a pair $(G,B)$ in which $G$ is a graph and $B$ a collection of cycles in $G$ (referred to as balanced cycles) such that every theta subgraph of $G$ contains exactly zero, one, or three balanced cycles (i.e., not exactly two balanced cycles). Biased graphs (an invention of Tom Zaslavsky) are a canonical way to encode frame matroids. Frame matroids are central objects in matroid theory given the Matroid Varieties Theorem of Kahn and Kung and the Weak Structure Theorem of Geelen, Gerards, and Whittle.
An edge $e$ in a graph $G$ is understood to come along with a specific direction along it; the reverse edge is denoted $e^{-1}$. Given a group $\Gamma$, a $\Gamma$-gain function on $G$ is a function $\gamma\colon\Gamma\to E(G)$ satisfying $\gamma(e^{-1})=\gamma(e)^{-1}$. Taking any cyclic ordering of the edges along a cycle $C$ in $G$, consider the corresponding product of group labels. The cycle $C$ is said to be balanced with respect to $\gamma$ when this product is $1\in\Gamma$. (This is well defined by using group conjugation.) This pair $(G,B_\gamma)$ is the canonical example of a biased graph and it is a canonical way of viewing Dowling Geometries and their minors.
A $\Gamma$-realization of a biased graph $(G,B)$ is a $\Gamma$-gain function $\gamma$ such that $B_\gamma=B$. We will survey some new results on $\Gamma$-realizations concerning: the existence of $\Gamma$-realizations, bounding the number of inequivalent $\Gamma$-realizations, and stabilizing $\Gamma$-realizations of a biased graph with a given minor. Results parallel the analogous topic of matroid representations over finite fields. The tighter structure of graphs, however, leads to (and much more easily) the intuitively expected results.
Title: Unavoidable connected matroids retaining a specified minor
Speaker: James Oxley
Abstract: This talk is based on joint work with Carolyn Chun, Guoli Ding, and Dillon Mayhew. We begin with a fixed connected matroid $N$ and look at a sufficiently large connected matroid $M$ that has $N$ as a minor. By a 1991 result of Lovász, Schrijver, and Seymour, $M$ has a big circuit or a big cocircuit. Hence $M$ itself is a connected matroid that has $N$ as a minor and also has a big uniform minor. But $M$ may have many other elements that are not in either of these minors. Our goal is to pack these two minors compactly into some connected minor of $M$. Our main theorem proves that this can be done. Some variants on this theme will also be discussed.
In particular, we find a set of unavoidable minors for the class of graphs that have a cycle and a bond with a big intersection, and we pose a conjecture about the corresponding result for binary matroids.
Title: Dense triangle-free binary matroids
Speaker: Peter Nelson
Abstract: Brandt and Thomassé proved that a triangle-free graph $G$ with minimum degree greater than $\frac{1}{3}|V(G)|$ has chromatic number at most 4. On the other hand, Hajnal proved that for all real $\alpha > 0$ there exist triangle-free graphs G with minimum degree at least $(\frac{1}{3} – \alpha)|V(G)|$ and arbitrarily large chromatic number. I discuss a surprisingly similar theorem for triangle-free binary matroids, where we consider their critical number (exponent) in place of chromatic number. This is joint work with Jim Geelen.
Title: Accessibility in transitive graphs
Speaker: Matthias Hamann
Abstract: We discuss the connections between the cycle space and the cut space of transitive graphs. In particular, we will see that the cut space of a transitive graph $G$ is a finitely generated ${\rm Aut}(G)$-module as soon as the same holds for the cycle space.
We will use our result and talk about accessibility of transitive locally finite graphs: when does there exist some positive integer $n$ such that any two ends can be separated by removing at most $n$ edges? It follows that this is the case if the cycle space is generated by cycles of bounded length, and it turns out that this condition on the cycle space is satisfied in various natural classes of graphs.
Title: Graph-like representations of represented matroids
Speaker: Rohan Kapadia
Abstract: A consequence of the regular matroid decomposition theorem of Seymour is that if a sufficiently-connected binary matroid has a certain graphic minor, then either it is graphic or it has the Fano matroid as a minor. In this talk I present generalizations to matroids represented over other fields, considering when a matroid with a large Dowling geometry minor has a certain graph-like structure. I will also mention connections to the problem of classifying matroids in which some triple of elements is not contained in any circuit. This is joint work with Jim Geelen.
Title: Orienting $GF(4)$-representable matroids
Speaker: Jakayla Robbins
Abstract: Orientations of binary and ternary matroids are well-understood. If a binary matroid is orientable, the orientation can be derived from a totally unimodular matrix. If a ternary matroid is orientable, the orientation can be derived from a dyadic matrix. We present some preliminary findings about orientations of quaternary matroids. This is joint work with Dan Slilaty.
Title: Minimal non-orientable matroids of rank three
Speaker: Sonoko Moriyama
Abstract: Minimal non-orientable matroids have been investigated to characterize orientable matroids. The Fano matroid and the MacLane matroid are well-known minimal non-orientable matroids of rank $3$. A natural question is whether there exists a minimal non-orientable matroid of every rank $r$ with $m$ elements. In this talk, we give an answer to the question in rank $3$ that for every $m \geq 7$, there exists a minimal non-orientable matroid of rank $3$ with $m$ elements. To prove this statement, we construct two new infinite families of minimal non-orientable matroids of rank $3$. This is a joint work with Hidefumi Hiraishi.
Title: Edge Contraction Reconstruction
Speaker: Antoine Poirier
Abstract: The edge contraction reconstruction conjecture claims that all simple graphs with at least four edges are determined, or reconstructed, from the multiset of edge contraction minors. We will show that most disconnected graphs and most separable graphs are edge contraction “reconstructible”, and then we will present some of the strategies we use and the challenges we face for reconstructing graphs with a higher connectivity. This is joint work with Mike Newman.
Speaker: Simon Pfeil
Abstract: A matroid M is unbreakable if M/F is connected for all flats F of M. It is not difficult to show that M is unbreakable if and only if M^* has no two skew circuits. This talk will discuss some properties of unbreakable matroids and, in particular, will describe all regular unbreakable matroids.
Speaker: Vaidyanathan Sivaraman
Abstract: Ever since the resolution of the Strong Perfect Graph Conjecture by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, the subject of induced subgraphs has attracted the attention of several researchers. A graph is said to be a threshold graph if its vertices can be assigned weights (real numbers) such that there is an edge between two vertices if and only if the sum of their weights crosses a fixed threshold (another real number). There is a simple forbidden induced subgraph characterization of threshold graphs. We relax the definition of a threshold graph to get a bigger class, one we call the class of mock-threshold graphs. We will discuss their place with respect to other well-known classes of graphs, and aim for a forbidden induced subgraph characterization of mock-threshold graphs. This is joint work with Richard Behr and Thomas Zaslavsky.
Title: Tree-depth and vertex minors
Speaker: Petr Hlineny
Abstract: We show that graph classes of bounded shrub-depth coincide with vertex minors of graphs of bounded tree-depth, which extends a result of Kwon and Oum relating graphs of bounded rank-width to pivot minors of bounded tree-width graphs. Shrub-depth of a graph class can be defined as the least d such that this class has a simple FO interpretation into trees of height d. Our result has two parts – showing how every graph of such a class is obtained as a pivot minor of a bounded tree-depth graph, and proving that shrub-depth is preserved under local complementations. The latter is actually a corollary of two other strong results about MSO logic on graphs. We also argue why pivot minors are not enough to obtain a similar result.
This is joint work with O.Kwon, J.Obdrzalek, and S.Ordyniak.
Title: Axiomatizing real representability
Speaker: Mike Newman
Abstract: One of the oldest questions in matroid theory, from Whitney’s 1935 paper, asks for a characterization of representable matroids. There are several ways of interpreting this question. We focus on investigating when a “natural” set of axioms can exactly capture representability. We find that the missing axiom of matroid theory really is lost forever. This is joint work with Dillon Mayhew and Geoff Whittle.
Title: Towards an excluded-minor characterisation of the Hydra-5 matroids
Speaker: Ben Clark
Abstract: An excluded-minor characterisation of the Hydra-5 matroids can be thought of as the first step towards an excluded-minor characterisation of the matroids representable over the 5-element field. This talk will provide an overview of the progress towards an excluded-minor characterisation of the class of Hydra-5 matroids, and discuss how the problem of bounding an excluded minor can be reduced to a fragility problem. An outline of the work that remains will also be given.
Title: Excluded minors for orientability and representability of matroids
Speaker: Hidefumi Hiraishi
Abstract: Different from graphs, there exist minor-closed classes of matroids which cannot be characterized by a finite list of excluded minors. The following fundamental classes are known to have infinitely many excluded minors: the class of orientable matroids, and the classes of matroids representable over a given infinite field In this talk, we investigate the number of excluded minors of these classes further, motivated by the following question; under some natural assumption, whether the classes with infinitely many excluded minors can be characterized by a finite number excluded minors or not. Then we obtain the negative results as follows; for a given infinite field, (i) there exists an infinite number of orientable excluded minors of rank 3 for the class of matroids representable over the field, and (ii) there exists an infinite number of excluded minors of rank 3 for the union of the class of orientable matroids and class of matroids representable over the field. This is a joint work with Sonoko Moriyama.
Title: An algorithm for constructing a matroid’s $k$-tree
Speaker: Nick Brettell
Abstract: Oxley, Semple and Whittle (2004) showed that for a $3$-connected matroid $M$ with at least nine elements, there is a “$3$-tree” that describes, up to a natural equivalence, all the non-sequential $3$-separations of $M$. Clark and Whittle (2013) generalised this result to tangles in a connectivity system; in particular, their result implies that for a $k$-connected matroid $M$, there is a “$k$-tree” that displays all the non-sequential $k$-separations of $M$. In this talk, we present an algorithm for constructing such a $k$-tree in polynomial time, for arbitrary $k$. This generalises a similar algorithm by Oxley and Semple (2013) for constructing a $3$-tree in polynomial time.
Title: Fragility and excluded minors for dyadic matroids
Speaker: Dillon Mayhew
Abstract: This talk covers some recent work in a long-term project involving many collaborators. The basic idea of the project is to exploit the link between fragile matroids and excluded minors to find new excluded-minor characterisations. Say that $S$ is a set of matroids. A matroid, $M$, is $S$-fragile, if for every element $e$, either $M\backslash e$ or $M/e$ has no minor isomorphic to a member of $S$. Some fragile classes are easy to understand. For example, a 3-connected $\mathrm{GF}(4)$-representable or near-regular matroid is non-binary and $\{U_{2,4}\}$-fragile if and only if it is isomorphic to a whirl. This fact plays a critical role in the excluded-minor characterisations of $\mathrm{GF}(4)$-representable and near-regular matroids.
In the talk, I will give an overview of the connection between fragility and excluded-minor characterisations, and I will describe some recent progress we have made in understanding a dyadic class of fragile matroids. This moves us closer to an excluded-minor characterisation of dyadic matroids.
Title: A splitter theorem for large 3-connected graphs
Speaker: Guoli Ding
Abstract: We present the following theorem. If a 3-connected graph H is a
minor of a large 3-connected graph G, then G contains a large 3-connected
minor G’ such that G’ contains H as a minor and moreover G’ is a simple
modification of H.
Title: Coloring graphs with forbidden induced subgraphs
Speaker: Maria Chudnovsky
Abstract: Since graph-coloring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Due to results of Kaminski and Lozin, and Hoyler, the problem remains NP-complete, unless H is the disjoint union of paths. Recently the question of coloring graphs with a fixed-length induced path forbidden has received considerable attention. Only one case of that problem remains open for k-coloring when k>=4, and that is the case of 4-coloring graphs with no induced 6-vertex path. However, little is known for 3-coloring. Recently we settled the first open case for 3-coloring; namely we showed that 3-coloring graphs with no induced 7-vertex paths can be done in polynomial time. We also made progress on the 4-coloring question, and on other related problems. In this talk we will discuss some of the ideas of the algorithms.
This is joint work with Peter Maceli, Juraj Stacho and Mingxian Zhong.
Speaker: Hiu-Fai Law
Abstract: Linkability in finite digraphs can be studied in the framework of gammoids, where independent sets are those linkable to a fixed set of sinks. In an infinite digraph, linkable sets need not form the independent sets of a matroid – the natural characterization of a maximal independent set as sets linkable onto the fixed sinks need not hold. We prove that there is in fact a unique obstruction to this characterization, called the alternating comb. Problems and progress in the study of minors and duals of infinite gammoids will also be discussed.
Title: Binary and Regular Matroids without a Certain Minor.
Speaker: Talmage James Reid
Abstract: We use the tools of matroid 3-connectivity and internal 4-connectivity to determine classes of binary and regular matroids that do not contain a certain single minor. These results generalize both classical and recent results from the literature for graphs.
This talk is based on joint work with Kayla Harville and Haidong Wu.
Title: Infinite trees of matroids
Speaker: Nathan Bowler
Abstract: We show how to stick together an infinite tree of matroids to obtain an infinite matroid. We present a natural class of infinite matroids which can be decomposed in this way into finite matroids. We explain how any matroid with no infinite circuit-cocircuit intersection can be constructed in this way from a tree of parts which are all either 3-connected, circuits or cocircuits.
This is joint work with Johannes Carmesin.
Title: Criteria for embedding a biased expansion (or regular 3-net) matroid in a non-Desarguesian projective plane.
Speaker: Thomas Zaslavsky
Abstract: A regular 3-net matroid, also known as the matroid of a biased expansion of $K_3$, is associated with a unique quasigroup (up to some simple transforms). It can be embedded in a projective plane over a skew field (a Desarguesian plane) if and only if the quasigroup is contained in the additive or multiplicative group of the skew field. On the other hand, it seems that no similar criterion is known for embedding in a non-Desarguesian plane. Rigoberto Florez and I have developed such a criterion in terms of a planar ternary ring associated to the plane. I will explain the terminology and the criterion.
Title: Introduction to delta-matroids
Speaker: Steven Noble
Abstract: Delta-matroids generalize matroids, and were defined by Andr\’e Bouchet in 1986. Roughly speaking they comprise a set of feasible sets, that obey an exchange axiom similar to that governing the bases of a matroid, but are not necessarily equicardinal. A key concept in delta-matroids is a twist (or partial dual) where one forms a dual with respect to a subset of the elements. We give 3 examples of families of delta-matroids: graphic delta-matroids (which come from ribbon graphs), representable delta-matroids and twists of matroids, and present an excluded minor characterization of the last class.
Title: Inductive tools for delta-matroids
Speaker: Carolyn Chun
Abstract: Delta-matroids generalize matroids and were defined by André Bouchet in 1986. In this talk, we give a characterization of connectivity for matroids that generalizes to delta-matroids, and we present some inductive tools for delta-matroids.
Title: Matroid Tree Width and the Chromatic Polynomial
Speaker: Rhiannon Hall
Abstract: This talk will look at introductory matroid tree-width material and chromatic polynomial material. We will then restrict ourselves to a finite field $GF(q)$ and show that for any $k\in\mathbb{N}$, there exists $c_k\in\mathbb{R}$ such that the chromatic polynomials of all $GF(q)$-representable matroids of tree-width at most $k$ satisfy $$\chi (M,\lambda)>0\ \ \text{for all}\ \ \lambda>c_k.$$ In other words, bounding the tree-width of a $GF(q)$-representable matroid will also bound the size of the maximum root of its chromatic polynomial.
This is joint work with Steve Noble, Carolyn Chun, and Criel Merino.
Title: Counting matroids in minor-closed classes
Speaker: Jorn van der Pol
Abstract: We introduce cover complexity as the minimal size of a certain faithful description of a matroid. As the cover complexity of a matroid bounds the amount of information needed to specify it, a uniform bound on the cover complexity of all the matroids in a class immediately bounds the number of matroids in that class.
A technical lemma allows us to translate upper bounds on the cover complexity of a class of matroids of fixed (low) rank to upper bounds on the cover complexity of matroids of arbitrary rank. Using this machinery, it can be shown that the class of matroids without an $N$-minor is asymptotically small in each of the cases $N = U_{2,k}, U_{3,6}, P_6, Q_6$, and $R_6$, thus confirming a few special cases of a conjecture due to Mayhew, Newman, Welsh, and Whittle.
This is joint work with Rudi Pendavingh.
Title: A refinement of the grid theorem
Speaker: Benson Joeris
Abstract: A $k$-connected set of vertices in a graph $G$ is a set $X$ of vertices in $G$ such that if $X_1,X_2\subseteq X$ then $G$ contains $\min\{|X_1|,|X_2|,k\}$ vertex-disjoint paths between $X_1$ and $X_2$. The unavoidable minors for graphs containing a large $k$-connected set will be presented. In particular, for graphs containing a large, highly connected set, all of the unavoidable minors contain a large grid-minor, which implies the grid theorem of Robertson and Seymour. This is joint work with Jim Geelen.
Title: Matchability of pairs of infinite matroids
Speaker: Jerzy Wojciechowski
Abstract: Let $(M,W)$ be a pair of matroids on the same ground set $E$. The pair is matchable iff there exists a subset of $E$ that is spanning in $M$ and independent in $W$. We define, by transfinite induction, a function $\mu$ on the set of all injective transfinite sequences of the elements of $E$ into the set of integers augmented with infinity and negative infinity. A necessary condition for matchability is that all values of $\mu$ are nonnegative. In general, this condition is not sufficient even when $M$ and $W$ are assumed to be finitary. In particular, it is sufficient when $M$ is cofinitary or a countable union of rank finite matroids and $W$ is finitary. It is also sufficient when $M$ and $W$ are the partition matroids on the set $E$ of edges of a bipartite graph such that each vertex of the side corresponding to $W$ has countable degree. We conjecture that our condition is sufficient when for each $e$ in $E$ the sets of circuits of $M^*$ (the dual of $M$) and of $W$ that contain e are both countable.
Title: Denser triangle-free binary matroids
Speaker: Rutger Campbell
Abstract: Bose and Burton showed that the maximum number of points in a rank-$r$ triangle-free binary matroid is $\frac{1}{2} 2^r$. We describe the structure of all rank-$r$ triangle-free binary matroids with more than $\frac{33}{128} 2^r$ points. This is joint work with Jim Geelen and Peter Nelson.