On Reid's characterization of the ternary matroids |
| |
Authors: | Robert E Bixby |
| |
Affiliation: | Department of Industrial Engineering and Management Science, Northwestern University, Evanston, Illinois, 60091 USA |
| |
Abstract: | In this paper we prove a stronger version of a result of Ralph Reid characterizing the ternary matroids (i.e., the matroids representable over the field of 3 elements, GF(3)). In particular, we prove that a matroid is ternary if it has no seriesminor of type Ln for n ≥ 5 (n cells and n circuits, each of size n ? 1), and no series-minor of type (dual of L5), BII (Fano matroid) or BI (dual of type BII). The proof we give does not assume Reid's theorem. Rather we give a direct proof based on the methods (notably the homotopy theorem) developed by Tutte for proving his characterization of regular matroids. Indeed, the steps involved in our proof closely parallel Tutte's proof, but carrying out these steps now becomes much more complicated. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|