On Matroids Representable over $GF(3)$ and Other Fields
HTML articles powered by AMS MathViewer
- by Geoff Whittle
- Trans. Amer. Math. Soc. 349 (1997), 579-603
- DOI: https://doi.org/10.1090/S0002-9947-97-01893-X
- PDF | Request permission
Abstract:
The matroids that are representable over $GF(3)$ and some other fields depend on the choice of field. This paper gives matrix characterisations of the classes that arise. These characterisations are analogues of the characterisation of regular matroids as the ones that can be represented over the rationals by a totally-unimodular matrix. Some consequences of the theory are as follows. A matroid is representable over $GF(3)$ and $GF(5)$ if and only if it is representable over $GF(3)$ and the rationals, and this holds if and only if it is representable over $GF(p)$ for all odd primes $p$. A matroid is representable over $GF(3)$ and the complex numbers if and only if it is representable over $GF(3)$ and $GF(7)$. A matroid is representable over $GF(3)$, $GF(4)$ and $GF(5)$ if and only if it is representable over every field except possibly $GF(2)$. If a matroid is representable over $GF(p)$ for all odd primes $p$, then it is representable over the rationals.References
- Brylawski, T. H., and Kelly, D., Matroids and combinatorial geometries. Department of Mathematics, University of North Carolina, Chapel Hill, 1980.
- Brylawski, T. H., and Lucas, D., Uniquely representable combinatorial geometries, in Teorie Combinatorie (Proc. 1973 Internat. Colloq.), pp. 83–104, Accademia Nazionale del Lincei, Rome, 1976.
- A. M. H. Gerards, A short proof of Tutte’s characterization of totally unimodular matrices, Linear Algebra Appl. 114/115 (1989), 207–212. MR 986875, DOI 10.1016/0024-3795(89)90461-8
- Joseph P. S. Kung, Combinatorial geometries representable over $\textrm {GF}(3)$ and $\textrm {GF}(q)$. I. The number of points, Discrete Comput. Geom. 5 (1990), no. 1, 83–95. MR 1018017, DOI 10.1007/BF02187781
- Kung, J. P. S. and Nguyen, H. Q., Weak Maps, in Theory of Matroids (ed. N. White), pp. 254–271, Cambridge University Press, Cambridge, 1986.
- Joseph P. S. Kung and James G. Oxley, Combinatorial geometries representable over $\textrm {GF}(3)$ and $\textrm {GF}(q)$. II. Dowling geometries, Graphs Combin. 4 (1988), no. 4, 323–332. MR 965387, DOI 10.1007/BF01864171
- Jon Lee, Subspaces with well-scaled frames, Linear Algebra Appl. 114/115 (1989), 21–56. MR 986864, DOI 10.1016/0024-3795(89)90450-3
- Jon Lee, The incidence structure of subspaces with well-scaled frames, J. Combin. Theory Ser. B 50 (1990), no. 2, 265–287. MR 1081231, DOI 10.1016/0095-8956(90)90082-B
- Dean Lucas, Weak maps of combinatorial geometries, Trans. Amer. Math. Soc. 206 (1975), 247–279. MR 371693, DOI 10.1090/S0002-9947-1975-0371693-2
- James G. Oxley, A characterization of the ternary matroids with no $M(K_4)$-minor, J. Combin. Theory Ser. B 42 (1987), no. 2, 212–249. MR 884255, DOI 10.1016/0095-8956(87)90041-4
- James G. Oxley, A characterization of certain excluded-minor classes of matroids, European J. Combin. 10 (1989), no. 3, 275–279. MR 1029175, DOI 10.1016/S0195-6698(89)80063-0
- James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1207587
- Oxley, J. G. and Whittle, G. P., On weak maps of ternary matroids, Europ. J. Combin. (to appear).
- 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
- 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
- W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1–47. MR 179781, DOI 10.6028/jres.069B.001
- Whittle, G. P., Inequivalent representations of ternary matroids, Discrete Math. 149 (1996), 233–238.
- Whittle, G. P., A characterisation of the matroids representable over $GF(3)$ and the rationals, J. Combin. Theory Ser. B. 65 (1995), 222–261.
- Thomas Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982), no. 1, 47–74. MR 676405, DOI 10.1016/0166-218X(82)90033-6
Bibliographic Information
- Geoff Whittle
- Affiliation: Department of Mathematics, Victoria University, PO Box 600 Wellington, New Zealand
- MR Author ID: 182520
- Email: whittle@kauri.vuw.ac.nz
- Received by editor(s): August 20, 1994
- © Copyright 1997 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 349 (1997), 579-603
- MSC (1991): Primary 05B35
- DOI: https://doi.org/10.1090/S0002-9947-97-01893-X
- MathSciNet review: 1407504