Source author record

Stefan H. M. van Zwam

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Information Theory math.IT

Catalog footprint

Research overview

13works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2018arXiv

On perturbations of highly connected dyadic matroids

Geelen, Gerards, and Whittle [3] announced the following result: let $q = p^k$ be a prime power, and let $\mathcal{M}$ be a proper minor-closed class of $\mathrm{GF}(q)$ -representable matroids, which does not contain $\mathrm{PG}(r-1,p)$ for sufficiently high $r$ . There exist integers $k, t$ such that every vertically $k$ -connected matroid in $\mathcal{M}$ is a rank- $(\leq t)$ perturbation of a frame matroid or the dual of a frame matroid over $\mathrm{GF}(q)$ . They further announced a characterization of the perturbations through the introduction of subfield templates and frame templates. We show a family of dyadic matroids that form a counterexample to this result. We offer several weaker conjectures to replace the ones in [3], discuss consequences for some published papers, and discuss the impact of these new conjectures on the structure of frame templates.

preprint2018arXiv

The highly connected even-cycle and even-cut matroids

The classes of even-cycle matroids, even-cycle matroids with a blocking pair, and even-cut matroids each have hundreds of excluded minors. We show that the number of excluded minors for these classes can be drastically reduced if we consider in each class only the highly connected matroids of sufficient size.

preprint2016arXiv

Templates for Binary Matroids

A binary frame template is a device for creating binary matroids from graphic or cographic matroids. Such matroids are said to conform or coconform to the template. We introduce a preorder on these templates and determine the nontrivial templates that are minimal with respect to this order. As an application of our main result, we determine the eventual growth rates of certain minor-closed classes of binary matroids, including the class of binary matroids with no minor isomorphic to PG(3,2). Our main result applies to all highly-connected matroids in a class, not just those of maximum size. As a second application, we characterize the highly-connected 1-flowing matroids.

preprint2016arXiv

The maximum-likelihood decoding threshold for graphic codes

For a class $\mathcal{C}$ of binary linear codes, we write $θ_{\mathcal{C}}\colon (0,1) \to [0,\frac{1}{2}]$ for the maximum-likelihood decoding threshold function of $\mathcal{C}$ , the function whose value at $R \in (0,1)$ is the largest bit-error rate $p$ that codes in $\mathcal{C}$ can tolerate with a negligible probability of maximum-likelihood decoding error across a binary symmetric channel. We show that, if $\mathcal{C}$ is the class of cycle codes of graphs, then $θ_{\mathcal{C}}(R) \le \frac{(1-\sqrt{R})^2}{2(1+R)}$ for each $R$ , and show that equality holds only when $R$ is asymptotically achieved by cycle codes of regular graphs.

preprint2015arXiv

Computer-verification of the structure of some classes of fragile matroids

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.

preprint2015arXiv

Fan-extensions in fragile matroids

If S is a set of matroids, then the matroid M is S-fragile if, for every element e in E(M), either M\e or M/e has no minor isomorphic to a member of S. Excluded-minor characterizations often depend, implicitly or explicitly, on understanding classes of fragile matroids. In certain cases, when F is a minor-closed class of S-fragile matroids, and N is in F, the only members of F that contain N as a minor are obtained from N by increasing the length of fans. We prove that if this is the case, then we can certify it with a finite case-analysis. The analysis involves examining matroids that are at most two elements larger than N.

preprint2014arXiv

Matroid 3-connectivity and branch width

We prove that, for each nonnegative integer k and each matroid N, if M is a 3-connected matroid containing N as a minor, and the the branch width of M is sufficiently large, then there is a k-element subset X of E(M) such that one of M\X and M/X is 3-connected and contains N as a minor.

preprint2014arXiv

Matroids representable over fields with a common subfield

A matroid is $\text{GF}(q)$ -regular if it is representable over all proper superfields of the field $\text{GF}(q)$ . We show that, for highly connected matroids having a large projective geometry over $\text{GF}(q)$ as a minor, the property of $\text{GF}(q)$ -regularity is equivalent to representability over both $\text{GF}(q^2)$ and $\text{GF}(q^t)$ for some odd integer $t \geq 3$ . We do this by means of an exact structural description of all such matroids.

preprint2014arXiv

On the existence of asymptotically good linear codes in minor-closed classes

Let $\mathcal{C} = (C_1, C_2, \ldots)$ be a sequence of codes such that each $C_i$ is a linear $[n_i,k_i,d_i]$ -code over some fixed finite field $\mathbb{F}$ , where $n_i$ is the length of the codewords, $k_i$ is the dimension, and $d_i$ is the minimum distance. We say that $\mathcal{C}$ is asymptotically good if, for some $\varepsilon > 0$ and for all $i$ , $n_i \geq i$ , $k_i/n_i \geq \varepsilon$ , and $d_i/n_i \geq \varepsilon$ . Sequences of asymptotically good codes exist. We prove that if $\mathcal{C}$ is a class of GF $(p^n)$ -linear codes (where $p$ is prime and $n \geq 1$ ), closed under puncturing and shortening, and if $\mathcal{C}$ contains an asymptotically good sequence, then $\mathcal{C}$ must contain all GF $(p)$ -linear codes. Our proof relies on a powerful new result from matroid structure theory.

preprint2011arXiv

An obstacle to a decomposition theorem for near-regular matroids

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.

preprint2011arXiv

On the relative importance of excluded minors

If EE is a set of matroids, then ex(EE) denotes the set of matroids that have no minor isomorphic to a member of EE. If EE' is a subset of EE, we say that EE' is /superfluous/ if ex(EE - EE') - ex(EE) contains only finitely many 3-connected matroids. We characterize the superfluous subsets of six well-known collections of excluded minors.

preprint2011arXiv

Stability, fragility, and Rota's Conjecture

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.

preprint2011arXiv

The structure of graphs with a vital linkage of order 2

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Stefan H. M. van Zwam

Research overview

Is this your work?

13 publications

On perturbations of highly connected dyadic matroids

The highly connected even-cycle and even-cut matroids

Templates for Binary Matroids

The maximum-likelihood decoding threshold for graphic codes

Computer-verification of the structure of some classes of fragile matroids

Fan-extensions in fragile matroids

Matroid 3-connectivity and branch width

Matroids representable over fields with a common subfield

On the existence of asymptotically good linear codes in minor-closed classes

An obstacle to a decomposition theorem for near-regular matroids

On the relative importance of excluded minors

Stability, fragility, and Rota's Conjecture

The structure of graphs with a vital linkage of order 2

See the researcher in context

Building this map preview