Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-29T18:56:56.055Z Has data issue: false hasContentIssue false
  • English
  • Français

On sign-representable matroids

Published online by Cambridge University Press:  24 October 2008

James Oxley  and
Geoff Whittle
James Oxley
Affiliation:
Department of Mathematics, Louisiana State University, Baton Rouge, LA 70803-4918, U.S.A.
Geoff Whittle
Affiliation:
Department of Mathematics, Victoria University of Wellington, P.O. Box 600, Wellington, New Zealand
Get access Rights & Permissions [Opens in a new window]

Abstract

A matroid M will be called sign-representable if, for every basis B of M, there is a (0, 1, −l)-matrix [Ir|y] representing M over ℚ in which the first r columns correspond to the members of B. The class of sign-representable matroids, which is closely related to the important class of regular matroids, is easily seen to be closed under both duality and the taking of minors. This paper proves several characterizations of the class, including a constructive one, and shows that the excluded minors for the class are U2, 5, U3, 5, the Fano matroid and its dual, and the rank-3 whirl.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 113 , Issue 3 , May 1993 , pp. 499 - 506
Copyright
Copyright © Cambridge Philosophical Society 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bixby, R. E.. A strengthened form of Tutte's characterization of regular matroids. J. Combin. Theory Ser. B 20 (1976), 216–221.CrossRefGoogle Scholar
[2]Bixby, R. E.. On Reid's characterization of the ternary matroids. J. Combin. Theory Ser. B 26 (1979), 174–204.CrossRefGoogle Scholar
[3]Brylawski, T. H.. A combinatorial model for series-parallel networks. Trans. Amer. Math. Soc. 154 (1971), 1–22.CrossRefGoogle Scholar
[4]Brylawski, T. H.. A note on Tutte's unimodular representation theorem. Proc. Amer. Math. Soc. 52 (1975), 499–502.Google Scholar
[5]Brylawski, T. H. and Kelly, D. G.. Matroids and Combinatorial Geometries (Department of Mathematics, University of North Carolina, Chapel Hill, 1980).Google Scholar
[6]Brylawski, T. H. and Lucas, D.. Uniquely representable combinatorial geometries. In Teorie Combinatorie (Accademia Nazionale dei Lincei, Rome, 1976), pp. 83–104.Google Scholar
[7]Gerards, A. M. H.. A short proof of Tutte's characterization of totally unimodular matrices. Linear Algebra Appl. 114/115 (1989), 207–212.CrossRefGoogle Scholar
[8]Oxley, J. G.. Matroid Theory (Oxford University Press, 1992).Google Scholar
[9]Seymour, P. D.. Matroid representation over GF(3). J. Combin. Theory Ser. B 26 (1979), 159–173.CrossRefGoogle Scholar
[10]Seymour, P. D.. Decomposition of regular matroids. J. Combin. Theory Ser. B 28 (1980), 305–359.CrossRefGoogle Scholar
[11]Truemper, K.. Partial matroid representations. European J. Combin. 5 (1984), 377–394.CrossRefGoogle Scholar
[12]Truemper, K.. A decomposition theory for matroids. VI. Almost regular matroids. J. Combin. Theory Ser. B 55 (1992), 253–301.CrossRefGoogle Scholar
[13]Tutte, W. T.. A homotopy theorem for matroids, I, II. Trans. Amer. Math. Soc. 88 (1958), 144–174.Google Scholar
[14]Tutte, W. T.. Connectivity in matroids. Canad. J. Math. 18 (1966), 1301–1324.CrossRefGoogle Scholar
[15]White, N. (editor). Combinatorial Geometries (Cambridge University Press, 1987).CrossRefGoogle Scholar