×

zbMATH — the first resource for mathematics

Inequivalent representations of matroids over prime fields. (English) Zbl 1281.05041
Summary: It is proved that for each prime field \(\mathrm{GF}(p)\), there is an integer \(n_p\) such that a 4-connected matroid has at most \(n_p\) inequivalent representations over \(\mathrm{GF}(p)\). We also prove a stronger theorem that obtains the same conclusion for matroids satisfying a connectivity condition, intermediate between 3-connectivity and 4-connectivity that we term “\(k\)-coherence”.
We obtain a variety of other results on inequivalent representations including the following curious one. For a prime power \(q\), let \(\mathcal{R}(q)\) denote the set of matroids representable over all fields with at least \(q\) elements. Then there are infinitely many Mersenne primes if and only if, for each prime power \(q\), there is an integer \(m_q\) such that a 3-connected member of \(\mathcal{R}(q)\) has at most \(m_q\) inequivalent \(\mathrm{GF}(7)\)-representations.
The theorems on inequivalent representations of matroids are consequences of structural results that do not rely on representability. The bulk of this paper is devoted to proving such results.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aikin, J.; Oxley, J., The structure of crossing separations in matroids, Adv. in Appl. Math., 41, 10-26, (2008) · Zbl 1139.05010
[2] B.D. Beavers, Circuits and structure in matroids and graphs, PhD Thesis, Louisiana State University, 2006.
[3] Bixby, R. E., A simple theorem on 3-connectivity, Linear Algebra Appl., 45, 123-126, (1982) · Zbl 0499.05020
[4] Ding, G.; Oporowski, B.; Oxley, J.; Vertigan, D., Unavoidable minors of large 3-connected binary matroids, J. Combin. Theory Ser. B, 66, 334-360, (1996) · Zbl 0856.05022
[5] Ding, G.; Oporowski, B.; Oxley, J.; Vertigan, D., Unavoidable minors of large 3-connected matroids, J. Combin. Theory Ser. B, 71, 244-293, (1997) · Zbl 0897.05020
[6] Duke, R., Freedom in matroids, Ars Combin., 26B, 191-216, (1988) · Zbl 0665.05004
[7] Geelen, J.; Gerards, B.; Kapoor, A., The excluded minors for \(\mathit{GF}(4)\)-representable matroids, J. Combin. Theory Ser. B, 79, 247-299, (2000) · Zbl 1024.05015
[8] Geelen, J.; Gerards, B.; Whittle, G., Matroid T-connectivity, SIAM J. Discrete Math., 20, 588-596, (2006) · Zbl 1122.05023
[9] Geelen, J.; Gerards, B.; Whittle, G., Tangles, tree-decompositions and grids in matroids, J. Combin. Theory Ser. B, 99, 657-667, (2009) · Zbl 1229.05070
[10] Geelen, J.; Gerards, B.; Whittle, G., On inequivalent representations of matroids over non-prime fields, J. Combin. Theory Ser. B, 100, 740-743, (2010) · Zbl 1230.05087
[11] Geelen, J.; Hliněný, P.; Whittle, G., Bridging separations in matroids, SIAM J. Discrete Math., 18, 638-646, (2004) · Zbl 1069.05017
[12] Geelen, J.; Oxley, J. G.; Vertigan, D.; Whittle, G., Totally free expansions of matroids, J. Combin. Theory Ser. B, 84, 130-179, (2002) · Zbl 1048.05020
[13] Geelen, J.; Oxley, J. G.; Vertigan, D.; Whittle, G., A short proof of non-\(\mathit{GF}(5)\)-representability of matroids, J. Combin. Theory Ser. B, 91, 105-121, (2004) · Zbl 1050.05024
[14] J. Geelen, G. Whittle, Certifying non-representability of matroids over prime fields, submitted for publication. · Zbl 1330.05032
[15] Kahn, J., On the uniqueness of matroid representations over \(\mathit{GF}(4)\), Bull. Lond. Math. Soc., 20, 5-10, (1988) · Zbl 0609.05028
[16] Kung, J. P.S., Extremal matroid theory, (Robertson, N.; Seymour, P. D., Graph Structure Theory, (1993), Amer. Math. Soc. Providence, RI), 21-62 · Zbl 0791.05018
[17] Lemos, M.; Oxley, J., A sharp bound on the size of a connected matroid, Trans. Amer. Math. Soc., 353, 4039-4056, (2001) · Zbl 0971.05034
[18] Lemos, M.; Oxley, J., On the minor-minimal 3-connected matroids having a fixed minor, European J. Combin., 24, 1097-1123, (2003) · Zbl 1057.05022
[19] Oxley, J., Matroid theory, (2011), Oxford University Press New York · Zbl 1254.05002
[20] Oxley, J.; Semple, C.; Whittle, G., The structure of the 3-separations of 3-connected matroids, J. Combin. Theory Ser. B, 92, 257-293, (2004) · Zbl 1059.05032
[21] Oxley, J.; Semple, C.; Whittle, G., The structure of the 3-separations of 3-connected matroids II, European J. Combin., 28, 1239-1261, (2007) · Zbl 1118.05012
[22] Oxley, J.; Semple, C.; Whittle, G., Wild triangles in 3-connected matroids, J. Combin. Theory Ser. B, 98, 291-323, (2008) · Zbl 1138.05011
[23] Oxley, J.; Semple, C.; Whittle, G., Exposing 3-separations in 3-connected matroids, Adv. in Appl. Math., 47, 463-508, (2011) · Zbl 1233.05080
[24] Oxley, J.; Semple, C.; Whittle, G., An upgraded wheels and whirls theorem for 3-connected matroids, J. Combin. Theory Ser. B, 102, 610-637, (2012) · Zbl 1241.05014
[25] Oxley, J.; Vertigan, D.; Whittle, G., On inequivalent representations of matroids over finite fields, J. Combin. Theory Ser. B, 67, 325-343, (1996) · Zbl 0856.05021
[26] Oxley, J.; Wu, H., On the structure of 3-connected matroids and graphs, European J. Combin., 21, 667-688, (2000) · Zbl 0973.05016
[27] Seymour, P. D., Decomposition of regular matroids, J. Combin. Theory Ser. B, 28, 305-359, (1980) · Zbl 0443.05027
[28] Seymour, P. D., Recognising graphic matroids, Combinatorica, 1, 75-78, (1981) · Zbl 0501.05022
[29] Tutte, W. T., Mengerʼs theorem for matroids, J. Res. Natl. Bur. Stand. Sec. B, 69, 49-53, (1965) · Zbl 0151.33802
[30] Tutte, W. T., Connectivity in matroids, Canad. J. Math., 18, 1301-1324, (1966) · Zbl 0149.21501
[31] Zaslavsky, T., Biased graphs. II. the three matroids, J. Combin. Theory Ser. B, 51, 46-72, (1991) · Zbl 0763.05096
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.