AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
The Internally $4$-Connected Binary Matroids With No $M(K_{3,3})$-Minor.
About this Title
Dillon Mayhew, School of Mathematics, Statistics, and Operations Research, Victoria University of Wellington, P.O. BOX 600, Wellington, New Zealand., Gordon Royle, School of Mathematics and Statistics, The University of Western Australia, 35 Stirling Highway, Crawley 6009, Western Australia. and Geoff Whittle, School of Mathematics, Statistics, and Operations Research, Victoria University of Wellington, P.O. BOX 600, Wellington, New Zealand.
Publication: Memoirs of the American Mathematical Society
Publication Year:
2010; Volume 208, Number 981
ISBNs: 978-0-8218-4826-5 (print); 978-1-4704-0595-3 (online)
DOI: https://doi.org/10.1090/S0065-9266-10-00600-9
Published electronically: June 8, 2010
Keywords: Binary matroids,
excluded minors,
structural decomposition
MSC: Primary 05B35
Table of Contents
Chapters
- 1. Introduction
- 2. Preliminaries
- 3. Mรถbius matroids
- 4. From internal to vertical connectivity
- 5. An $R_{12}$-type matroid
- 6. A connectivity lemma
- 7. Proof of the main result
- A. Case-checking
- B. Sporadic matroids
- C. Allowable triangles
Abstract
We give a characterization of the internally $4$-connected binary matroids that have no minor isomorphic to $M(K_{3,3})$. Any such matroid is either cographic, or is isomorphic to a particular single-element extension of the bond matroid of a cubic or quartic Mรถbius ladder, or is isomorphic to one of eighteen sporadic matroids.- Safwan Akkari and James Oxley, Some local extremal connectivity results for matroids, Combin. Probab. Comput. 2 (1993), no.ย 4, 367โ384. MR 1264712, DOI 10.1017/S0963548300000766
- Andrรฉ Bouchet, W. H. Cunningham, and J. F. Geelen, Principally unimodular skew-symmetric matrices, Combinatorica 18 (1998), no.ย 4, 461โ486. MR 1722253, DOI 10.1007/s004930050033
- Robert E. Bixby, A simple theorem on $3$-connectivity, Linear Algebra Appl. 45 (1982), 123โ126. MR 660982, DOI 10.1016/0024-3795(82)90214-2
- Tom Brylawski, Modular constructions for combinatorial geometries, Trans. Amer. Math. Soc. 203 (1975), 1โ44. MR 357163, DOI 10.1090/S0002-9947-1975-0357163-6
- J. F. Geelen, A. M. H. Gerards, and A. Kapoor, The excluded minors for $\textrm {GF}(4)$-representable matroids, J. Combin. Theory Ser. B 79 (2000), no.ย 2, 247โ299. MR 1769191, DOI 10.1006/jctb.2000.1963
- Jim Geelen and Xiangqian Zhou, A splitter theorem for internally 4-connected binary matroids, SIAM J. Discrete Math. 20 (2006), no.ย 3, 578โ587. MR 2272214, DOI 10.1137/050629124
- Dick Wick Hall, A note on primitive skew curves, Bull. Amer. Math. Soc. 49 (1943), 935โ936. MR 9442, DOI 10.1090/S0002-9904-1943-08065-2
- Matthew Halfan, Matroid decomposition, Masterโs essay, University of Waterloo, 2002.
- S. R. Kingan, A generalization of a graph result of D. W. Hall, Discrete Math. 173 (1997), no.ย 1-3, 129โ135. MR 1468845, DOI 10.1016/S0012-365X(96)00100-8
- S. R. Kingan and Manoel Lemos, Almost-graphic matroids, Adv. in Appl. Math. 28 (2002), no.ย 3-4, 438โ477. Special issue in memory of Rodica Simion. MR 1900004, DOI 10.1006/aama.2001.0791
- Joseph P. S. Kung, Growth rates and critical exponents of classes of binary combinatorial geometries, Trans. Amer. Math. Soc. 293 (1986), no.ย 2, 837โ859. MR 816330, DOI 10.1090/S0002-9947-1986-0816330-2
- Dillon Mayhew, Gordon Royle, and Geoff Whittle, Excluding Kuratowski graphs and their duals from binary matroids, submitted. Available at arXiv:0902.0198v1 [math.CO].
- James Oxley, Charles Semple, and Dirk Vertigan, Generalized $\Delta \text {-}Y$ exchange and $k$-regular matroids, J. Combin. Theory Ser. B 79 (2000), no.ย 1, 1โ65. MR 1757022, DOI 10.1006/jctb.1999.1947
- James Oxley, Charles Semple, and Geoff Whittle, The structure of the 3-separations of 3-connected matroids, J. Combin. Theory Ser. B 92 (2004), no.ย 2, 257โ293. MR 2099144, DOI 10.1016/j.jctb.2004.03.006
- James G. Oxley, On nonbinary $3$-connected matroids, Trans. Amer. Math. Soc. 300 (1987), no.ย 2, 663โ679. MR 876471, DOI 10.1090/S0002-9947-1987-0876471-1
- James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1207587
- Hongxun Qin and Xiangqian Zhou, The class of binary matroids with no $M(K_{3,3})$-, $M^*(K_{3,3})$-, $M(K_5)$- or $M^*(K_5)$-minor, J. Combin. Theory Ser. B 90 (2004), no.ย 1, 173โ184. Dedicated to Adrian Bondy and U. S. R. Murty. MR 2041325, DOI 10.1016/S0095-8956(03)00083-2
- P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), no.ย 3, 305โ359. MR 579077, DOI 10.1016/0095-8956(80)90075-1
- K. Truemper, A decomposition theory for matroids. III. Decomposition conditions, J. Combin. Theory Ser. B 41 (1986), no.ย 3, 275โ305. MR 864578, DOI 10.1016/0095-8956(86)90052-3
- W. T. Tutte, A homotopy theorem for matroids. I, II, Trans. Amer. Math. Soc. 88 (1958), 144โ174. MR 101526, DOI 10.1090/S0002-9947-1958-0101526-0
- K. Wagner, รber eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), no.ย 1, 570โ590 (German). MR 1513158, DOI 10.1007/BF01594196
- P. N. Walton and D. J. A. Welsh, On the chromatic number of binary matroids, Mathematika 27 (1980), no.ย 1, 1โ9. MR 581990, DOI 10.1112/S0025579300009876
- Xiangqian Zhou, On internally 4-connected non-regular binary matroids, J. Combin. Theory Ser. B 91 (2004), no.ย 2, 327โ343. MR 2064874, DOI 10.1016/j.jctb.2004.03.001
- Xiangqian Zhou, A note on binary matroid with no $M(K_{3,3})$-minor, J. Combin. Theory Ser. B 98 (2008), no.ย 1, 235โ238. MR 2368034, DOI 10.1016/j.jctb.2007.03.003