A new minor-closed class of transversal matroids
Gerry Toft · 2025
Read A new minor-closed class of transversal matroids by Gerry Toft (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-13089.txt.
Introduction
Gerry Toft characterizes when shrinking a transversal matroid keeps it transversal. Matroids abstract the idea of independence, and transversal matroids arise from matchings between a set and a family of subsets, a structure with uses in scheduling and assignment problems. Contraction is one of the basic ways to reduce a matroid, and knowing whether the result stays in the same family is a basic structural question. Toft answers it for single-element contractions of transversal matroids.
From that characterization he defines a new class, path-circular matroids, and proves it is closed under all minors, the combined operations of deletion and contraction that matroid theory uses to classify families. The class generalizes two known families, bicircular matroids and multi-path matroids, uniting them under one description. Minor-closed classes are the backbone of matroid theory.
Catalog record
| CREATOR | Gerry Toft |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-13089
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A new minor-closed class of transversal matroids Gerry Toft Abstract . We provide a characterisation of when a single-element contraction of a transversal matroid is itself transversal. Using this characterisation, we define a new class of transversal matroids closed under minors, which we call path-circular matroids. Path-circular matroids generalise both of the well-known classes of bicircular matroids and multi-path matroids. 1. Introduction Along with representable and graphic matroids, transversal matroids are one of the most common examples of naturally-arising matroids. With this in mind, it is perhaps surprising that many aspects of the class of transversal matroids remain mysterious. Unlike representable and graphic matroids, transversal matroids are not closed under minors, and it is not known when the contraction of a transversal matroid is itself transversal. A recent breakthrough concerning minors of transversal matroids was made by Bastida [ 1 ] , who found a polynomial-time algorithm to determine whether a single-element contraction of a transversal matroid M is also transversal, and to construct a presentation if so. We consider the same problem from a structural, rather than algorithmic, point of view. The aim is to provide a tool which can be used in proofs concerning minors of transversal matroids. The first main results of this paper are Theorems 1.1 and 1.2 . Theorem 1.1 is a characterisation for when a single-element contraction of a transversal matroid is transversal, and, if it is, Theorem 1.2 describes how to find a presentation. These theorems will require the following definitions. Let M be a transversal matroid with presentation \mathcal{A}=(A_{1},A_{2},\ldots,A_{r}) , and let e\in E(M) . A graph G is an (e,\mathcal{A}) -presenting graph if there is a bijection \phi:V(G)\rightarrow\{i\in\{1,2,\ldots,r\}:e\in A_{i}\} such that, for all distinct v_{1},v_{2}\in V(G) , the subgraph of G induced by the vertices \{u\in V(G):A_{\phi(u)}\subseteq\cl_{M}^{*}(A_{\phi(v_{1})}\cup A_{\phi(v_{2})})\} is connected. We call the bijection \phi an (e,\mathcal{A}) -presenting map of G . Furthermore, G is a minimal (e,\mathcal{A}) -presenting graph if it is an (e,\mathcal{A}) -presenting graph, and the deletion of each edge of G is not an (e,\mathcal{A}) -presenting graph. For instance, Figure 1 shows minimal (e,\mathcal{A}_{i}) -presenting graphs for \displaystyle\mathcal{A}_{1} \displaystyle=(\{e,u,v\},\{e,w,x\},\{w,y,z\})\,, \displaystyle\mathcal{A}_{2} \displaystyle=(\{e,s,t,u,v\},\{e,u,v,w,x\},\{e,w,x,y,z\})\,,\text{ and} \displaystyle\mathcal{A}_{3} \displaystyle=(\{e,w,x,y,z\},\{e,w,x,y,z\},\{e,w,x,y,z\},\{e,w,x,y,z\})\,. There is a unique minimal (e,\mathcal{A}_{1}) -presenting graph, and a unique minimal (e,\mathcal{A}_{2}) -presenting graph, while any tree on 4 vertices is a minimal (e,\mathcal{A}_{3}) -presenting graph. \{e{,}u{,}v\} \{e{,}w{,}x\} \{e{,}y{,}z\} (a) A minimal (e,\mathcal{A}_{1}) -presenting graph. \{e{,}s{,}t{,}u{,}v\} \{e{,}u{,}v{,}w{,}x\} \{e{,}w{,}x{,}y{,}z\} (b) A minimal (e,\mathcal{A}_{2}) -presenting graph. \{e{,}w{,}x{,}y{,}z\} \{e{,}w{,}x{,}y{,}z\} \{e{,}w{,}x{,}y{,}z\} \{e{,}w{,}x{,}y{,}z\} (c) A minimal (e,\mathcal{A}_{3}) -presenting graph. Figure 1 . Minimal (e,\mathcal{A}_{i}) -presenting graphs. Theorem 1.1 . Let M be a transversal matroid with presentation \mathcal{A} such that |\mathcal{A}|=r(M) , and let e\in E(M) . Let G be a minimal (e,\mathcal{A}) -presenting graph. Then M/e is transversal if and only if G is a tree. Theorem 1.2 . Let M be a transversal matroid, and let e\in E(M) . Let \mathcal{A}=(A_{1},A_{2},\ldots,A_{r}) be a presentation of M , with r=r(M) , such that e\in A_{i} for all i\leq k , and e\notin A_{j} for all j>k . Let G be a minimal (e,\mathcal{A}) -presenting graph which is a tree, and let \phi be an (e,\mathcal{A}) -presenting map of G . Suppose the edge set of G is E(G)=\{\{u_{1},v_{1}\},\{u_{2},v_{2}\},\ldots,\{u_{k-1},v_{k-1}\}\}\,. Then (A_{\phi(u_{1})}\cup A_{\phi(v_{1})}-e,A_{\phi(u_{2})}\cup A_{\phi(v_{2})}-e,\ldots,A_{\phi(u_{k-1})}\cup A_{\phi(v_{k-1})}-e,A_{k+1},A_{k+2},\ldots,A_{r}) is a presentation of M/e . This research was motivated by the problem of finding the maximal minor-closed class of transversal matroids. The largest known minor-closed classes of transversal matroids are bicircular matroids and multi-path matroids . Bicircular matroids were introduced by Simões-Pereira [ 12 ] as a matroid whose elements are the edges of a graph, and whose circuits are minimal, connected subgraphs containing at least two cycles. Matthews [ 10 ] showed that a bicircular matroid can also be viewed as a transversal matroid that has a presentation in which every element is contained in at most two sets. To construct such a presentation \mathcal{A} , add a set to \mathcal{A} , for each vertex of the graph, consisting of the edges incident to that vertex. Multi-path matroids, introduced by Bonin and Giménez [ 3 ] , are transversal matroids with a cyclic ordering \sigma of their elements, and a presentation \mathcal{B} such that each set of \mathcal{B} is a cyclic interval of \sigma , and no set of \mathcal{B} contains another. Theorem 1.1 implies that a necessary condition for a transversal matroid M[\mathcal{A}] to be a member of the maximal minor-closed class of transversal matroids is that, for all e\in E(M[\mathcal{A}]) , each minimal (e,\mathcal{A}) -presenting graph is a tree. We define a class of transversal matroids which satisfy a stronger condition, that these graphs are paths, and show that this class is closed under minors. Let G be a simple graph. A path-circular collection \mathcal{P} of G is a collection of (not necessarily distinct) paths of G such that, if u_{1},u_{2},\ldots,u_{k} are the vertices (in order) of a path in \mathcal{P} and i\in\{2,3,\ldots,k-1\} , then (i) the degree of u_{i} in G is 2 , and (ii) every path of \mathcal{P} which contains u_{i} also contains at least one of u_{1} and u_{k} . Note that a path-circular collection may contain “null paths” consisting of zero vertices. These will correspond to loops in the resulting matroid. Suppose V(G)=\{v_{1},v_{2},\ldots,v_{r}\} . For all i\in\{1,2,\ldots,r\} , let N(v_{i})=\{p\in\mathcal{P}:v_{i}\text{ is a vertex of }p\} . Denote by M(\mathcal{P}) the transversal matroid on groundset \mathcal{P} with presentation (N(v_{1}),N(v_{2}),\ldots,N(v_{r})) . We call such a matroid a path-circular matroid . The definition of path-circular matroids is a generalisation of the definition of bicircular matroids: the elements of a bicircular matroid correspond to edges of a graph, while the elements of a path-circular matroid correspond to paths. Thus, a bicircular matroid is a path-circular matroid in which every path of \mathcal{P} contains at most one edge. Note that, in this case, the conditions (i) and (ii) of a path-circular collection are satisfied trivially. Path-circular matroids also generalise multi-path matroids: a multipath matroid is a path-circular matroid in which the graph G is a cycle. This is illustrated in Figure 2 . In the image of a path-circular matroid in Figure 2 , the paths of \mathcal{P} are unbroken lines, with loops representing paths consisting of a single vertex, and the edges of the graph G are the non-loop edges implied by the paths. (a) (b) Figure 2 . A multi-path matroid with ground set given by the black vertices (A), and an isomorphic path-circular matroid (B). Theorem 1.3 . Let M be a path-circular matroid. Then M\backslash e and M/e are both path-circular matroids. Section 2 contains some required preliminaries and basic results concerning transversal matroids and their duals. In Section 3 , we prove Theorem 1.1 and Theorem 1.2 . Finally, in Section 4 , we use Theorem 1.2 to prove Theorem 1.3 , and thus show that the class of path-circular matroids is closed under minors. 2. Preliminaries and Basic Results Our notation and terminology follows [ 11 ] unless specified otherwise. We will use [n] to represent the set \{1,2,\ldots,n\} . Let G be a graph, and U a set of vertices of G . The subgraph of G induced by U is the graph obtained from G by deleting every vertex not in