BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let M be a 3-connected matroid, and let N be a 3-connected minor of M. A pair {x1,x2}⊆E(M) is N-detachable if one of the matroids M/x1/x2 or M\x1\x2 is both 3-connected and has an N-minor. This is the third and final paper in a series where we prove that if ∣E(M)∣−∣E(N)∣≥10, then either M has an N-detachable pair after possibly performing a single Δ-Y or Y-Δ exchange, or M is essentially N with a spike attached. Moreover, we describe the additional structures that arise if we require only that ∣E(M)∣−∣E(N)∣≥5.
Let M be a 3-connected matroid, and let N be a 3-connected minor of M. We say that a pair {x1,x2}⊆E(M) is N-detachable if one of the matroids M/x1/x2 or M\x1\x2 is both 3-connected and has an N-minor. This is the first in a series of three papers where we describe the structures that arise when it is not possible to find an N-detachable pair in M. In this paper, we prove that if M has no N-detachable pairs, then either M has a 3-separating set, which we call X, with certain strong structural properties, or M has one of three particular 3-separators that can appear in a matroid with no N-detachable pairs.
For a matroid M having m rank-one flats, the density d(M) is r(M)m unless m=0, in which case d(M)=0. A matroid is density-critical if all of its proper minors of non-zero rank have lower density. By a 1965 theorem of Edmonds, a matroid that is minor-minimal among simple matroids that cannot be covered by k independent sets is density-critical. It is straightforward to show that U1,k+1 is the only minor-minimal loopless matroid with no covering by k independent sets. We prove that there are exactly ten minor-minimal simple obstructions to a matroid being able to be covered by two independent sets. These ten matroids are precisely the density-critical matroids M such that d(M)>2 but d(N)≤2 for all proper minors N of M. All density-critical matroids of density less than 2 are series-parallel networks. For k≥2, although finding all density-critical matroids of density at most k does not seem straightforward, we do solve this problem for k=49.
Let M be an excluded minor for the class of P-representable matroids for some partial field P, and let N be a 3-connected strong P-stabilizer that is non-binary. We prove that either M is bounded relative to N, or, up to replacing M by a Δ-Y-equivalent excluded minor, we can choose a pair of elements {a,b} such that either M\{a,b} is N-fragile, or M∗\{a,b} is N∗-fragile.
We consider matroids with the property that every subset of the ground set of size t is contained in both an ℓ-element circuit and an ℓ-element cocircuit; we say that such a matroid has the (t,ℓ)-property. We show that for any positive integer t, there is a finite number of matroids with the (t,ℓ)-property for ℓ<2t; however, matroids with the (t,2t)-property form an infinite family. We say a matroid is a t-spike if there is a partition of the ground set into pairs such that the union of any t pairs is a circuit and a cocircuit. Our main result is that if a sufficiently large matroid has the (t,2t)-property, then it is a t-spike. Finally, we present some properties of t-spikes.
A {\em connectivity function on} a set E is a function λ:2E→R such that λ(∅)=0, that λ(X)=λ(E−X) for all X⊆E and that λ(X∩Y)+λ(X∪Y)≤λ(X)+λ(Y) for all X,Y⊆E. Graphs, matroids and, more generally, polymatroids have associated connectivity functions. We introduce a notion of duality for polymatroids and prove that every connectivity function is the connectivity function of a self-dual polymatroid. We also prove that every integral connectivity function is the connectivity function of a half-integral self-dual polymatroid.
We conjecture that it is not possible to finitely axiomatize matroid representability in monadic second-order logic for matroids, and we describe some partial progress towards this conjecture. We present a collection of sentences in monadic second-order logic and show that it is possible to finitely axiomatize matroids using only sentences in this collection. Moreover, we can also axiomatize representability over any fixed finite field (assuming Rota's conjecture holds). We prove that it is not possible to finitely axiomatize representability, or representability over any fixed infinite field, using sentences from the collection.
We prove that there is no polynomial p(⋅) with the property that a matroid M can be determined to be either a lifted-graphic or frame matroid using at most p(∣M∣) rank evaluations. This resolves two conjectures of Geelen, Gerards and Whittle (Quasi-graphic matroids, arXiv:1512.03005v1).
This technical report accompanies the following three papers. It contains the computations necessary to verify some of the results claimed in those papers. [1] Carolyn Chun, Deborah Chun, Dillon Mayhew, and Stefan H. M. van Zwam. Fan-extensions in fragile matroids. In preparation. [2] Carolyn Chun, Dillon Mayhew, Geoff Whittle, and Stefan H. M. van Zwam. The structure of binary Fano-fragile matroids. In preparation. [3] Ben Clark, Dillon Mayhew, Geoff Whittle, and Stefan H. M. van Zwam. The structure of {U2,5, U3,5}-fragile matroids. In preparation.
For any minor-closed class of matroids over a fixed finite field, we state an exact structural characterization for the sufficiently connected matroids in the class. We also state a number of conjectures that might be approachable using the structural characterization.
Let N be a set of matroids. A matroid M is strictly N-fragile if M has a member of N as minor and, for all e∈E(M), at least one of M\e and M/e has no minor in N. In this paper we give a structural description of the strictly {U2,5,U3,5}-fragile matroids that have six inequivalent representations over GF(5). Roughly speaking, these matroids fall into two classes. The matroids without an {X8,Y8,Y8∗}-minor are constructed, up to duality, from one of two matroids by gluing wheels onto specified triangles. On the other hand, those matroids with an {X8,Y8,Y8∗}-minor can be constructed from a matroid in {X8,Y8,Y8∗} by repeated application of elementary operations, and are shown to have path width 3. The characterization presented here will be crucial in finding the explicit list of excluded minors for two classes of matroids: the Hydra-5-representable matroids and the 2-regular matroids.
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 l. We prove that if E(M)−(Q∪R∪S∪T) is sufficiently large, then there is an element e of M such that, in one of M\e or M/e, both connectivities are preserved.
Seymour's Decomposition Theorem for regular matroids states that any matroid representable over both GF(2) and GF(3) can be obtained from matroids that are graphic, cographic, or isomorphic to R10 by 1-, 2-, and 3-sums. It is hoped that similar characterizations hold for other classes of matroids, notably for the class of near-regular matroids. Suppose that all near-regular matroids can be obtained from matroids that belong to a few basic classes through k-sums. Also suppose that these basic classes are such that, whenever a class contains all graphic matroids, it does not contain all cographic matroids. We show that in that case 3-sums will not suffice.
It is proved that, for a prime number p, showing that an n-element matroid is not representable over GF(p) requires only O(n2) rank evaluations.
It is proved that for each prime field GF(p), there is an integer f(p) such that a 4-connected matroid has at most f(p) inequivalent representations over GF(p). We also prove a stronger theorem that obtains the same conclusion for matroids satisfying a connectivity condition, intermediate between 3-connectivity and 4-connectivity that we term "k-coherence". We obtain a variety of other results on inequivalent representations including the following curious one. For a prime power q, let R(q) denote the set of matroids representable over all fields with at least q elements. Then there are infinitely many Mersenne primes if and only if, for each prime power q, there is an integer mq such that a 3-connected member of R(q) has at most mq inequivalent GF(7)-representations. The theorems on inequivalent representations of matroids are consequences of structural results that do not rely on representability. The bulk of this paper is devoted to proving such results.
Fix a matroid N. A matroid M is N-fragile if, for each element e of M, at least one of M\e and M/e has no N-minor. The Bounded Canopy Conjecture is that all GF(q)-representable matroids M that have an N-minor and are N-fragile have branch width bounded by a constant depending only on q and N. A matroid N stabilizes a class of matroids over a field F if, for every matroid M in the class with an N-minor, every F-representation of N extends to at most one F-representation of M. We prove that, if Rota's conjecture is false for GF(q), then either the Bounded Canopy Conjecture is false for GF(q) or there is an infinite chain of GF(q)-representable matroids, each not stabilized by the previous, each of which can be extended to an excluded minor. Our result implies the previously known result that Rota's conjecture holds for GF(4), and that the classes of near-regular and sixth-roots-of-unity have a finite number of excluded minors. However, the bound that we obtain on the size of such excluded minors is considerably larger than that obtained in previous proofs. For GF(5) we show that Rota's Conjecture reduces to the Bounded Canopy Conjecture.
A tangle of order k in a matroid or graph may be thought of as a "k-connected component". For a tangle of order k in a matroid or graph that satisfies a certain robustness condition, we describe a tree decomposition of the matroid or graph that displays, up to a certain natural equivalence, all of the k-separations of the matroid or graph that are non-trivial with respect to the tangle.
A linkage of order k of a graph G is a subgraph with k components, each of which is a path. A linkage is vital if it spans all vertices, and no other linkage connects the same pairs of end vertices. We give a characterization of the graphs with a vital linkage of order 2: they are certain minors of a family of highly structured graphs.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.