Vámos matroid
The Vámos matroid
In mathematics, the Vámos matroid or Vámos cube is a matroid over a set of eight elements that cannot be represented as a matrix over any field. It is named after English mathematician Peter Vámos, who first described it in an unpublished manuscript in 1968.[1]
Definition
The Vámos matroid has eight elements, which may be thought of as the eight vertices of a cube or cuboid. The matroid has rank 4: all sets of three or fewer elements are independent, and 65 of the 70 possible sets of four elements are also independent. The five exceptions are four-element circuits in the matroid. Four of these five circuits are formed by faces of the cuboid (omitting two opposite faces). The fifth circuit connects two opposite edges of the cuboid, each of which is shared by two of the chosen four faces.
Another way of describing the same structure is that it has two elements for each vertex of the diamond graph, and a four-element circuit for each edge of the diamond graph.
Properties
- The Vámos matroid is a paving matroid, meaning that all of its circuits have size at least equal to its rank.[2]
- The Vámos matroid is isomorphic to its dual matroid, but it is not identically self-dual (the isomorphism requires a nontrivial permutation of the matroid elements).[2]
- The Vámos matroid cannot be represented over any field. That is, it is not possible to find a vector space, and a system of eight vectors within that space, such that the matroid of linear independence of these vectors is isomorphic to the Vámos matroid.[3] Indeed, it is one of the smallest non-representable matroids,[4] and served as a counterexample to a conjecture of Ingleton that the matroids on eight or fewer elements were all representable.[5]
- The Vámos matroid is a forbidden minor for the matroids representable over a field
, whenever has five or more elements.[6] However, it is not possible to test in polynomial time whether it is a minor of a given matroid 
, given access to through an independence oracle.[7] - The Vámos matroid is not algebraic. That is, there does not exist a field extension
, and a set of eight elements of 
, such that the transcendence degree of sets of these eight elements equals the rank function of the matroid.[8] - The Vámos matroid is not a secret-sharing matroid.[9] Secret-sharing matroids describe "ideal" secret sharing schemes in which any coalition of users who can gain any information about a secret key can learn the whole key (these coalitions are the dependent sets of the matroid), and in which the shared information contains no more information than is needed to represent the key.[10] These matroids also have applications in coding theory.[11]
- The Vámos matroid has no adjoint. This means that the dual lattice of the geometric lattice of the Vámos matroid cannot be order-embedded into another geometric lattice of the same rank.[12]
- The Vámos matroid can be oriented.[13] In oriented matroids, a form of the Hahn–Banach theorem follows from a certain intersection property of the flats of the matroid; the Vámos matroid provides an example of a matroid in which the intersection property is not true, but the Hahn–Banach theorem nevertheless holds.[14]
- The Tutte polynomial of the Vámos matroid is[15]
References
- ↑ Vámos, P. (1968), On the representation of independence structures.
- ↑ 2.0 2.1 Oxley, James G. (2006), "Example 2.1.22", Matroid Theory, Oxford Graduate Texts in Mathematics 3, Oxford University Press, p. 76, ISBN 9780199202508.
- ↑ Oxley (2006), pp. 170–172.
- ↑ Oxley (2006), Prop. 6.4.10, p. 196. A proof of representability for every matroid with fewer elements or the same number but smaller rank was given by Fournier, Jean-Claude (1970), "Sur la représentation sur un corps des matroïdes à sept et huit éléments", Comptes rendus de l'Académie des sciences, Sér. A-B 270: A810–A813, MR 0263665.
- ↑ Ingleton, A. W. (1959), "A note on independence functions and rank", Journal of the London Mathematical Society, Second Series 34: 49–56, doi:10.1112/jlms/s1-34.1.49, MR 0101848.
- ↑ Oxley (2006), p. 511.
- ↑ Seymour, P. D.; Walton, P. N. (1981), "Detecting matroid minors", Journal of the London Mathematical Society, Second Series 23 (2): 193–203, doi:10.1112/jlms/s2-23.2.193, MR 609098. Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing 11 (1): 184–190, doi:10.1137/0211014, MR 646772.
- ↑ Ingleton, A. W.; Main, R. A. (1975), "Non-algebraic matroids exist", Bulletin of the London Mathematical Society 7: 144–146, doi:10.1112/blms/7.2.144, MR 0369110.
- ↑ Seymour, P. D. (1992), "On secret-sharing matroids", Journal of Combinatorial Theory, Series B 56 (1): 69–73, doi:10.1016/0095-8956(92)90007-K, MR 1182458.
- ↑ Brickell, Ernest F.; Davenport, Daniel M. (1991), "On the classification of ideal secret sharing schemes", Journal of Cryptology 4 (2): 123–134, doi:10.1007/BF00196772.
- ↑ Simonis, Juriaan; Ashikhmin, Alexei (1998), "Almost affine codes", Designs, Codes and Cryptography 14 (2): 179–197, doi:10.1023/A:1008244215660, MR 1614357.
- ↑ Cheung, Alan L. C. (1974), "Adjoints of a geometry", Canadian Mathematical Bulletin 17 (3): 363–365; correction, ibid. 17 (1974), no. 4, 623, doi:10.4153/CMB-1974-066-5, MR 0373976.
- ↑ Bland, Robert G.; Las Vergnas, Michel (1978), "Orientability of matroids", Journal of Combinatorial Theory, Series B 24 (1): 94–123, doi:10.1016/0095-8956(78)90080-1, MR 0485461.
- ↑ Bachem, Achim; Wanka, Alfred (1988), "Separation theorems for oriented matroids", Discrete Mathematics 70 (3): 303–310, doi:10.1016/0012-365X(88)90006-4, MR 955127.
- ↑ Merino, Criel; Ramírez-Ibáñez, Marcelino; Sanchez, Guadalupe Rodríguez (2012), The Tutte polynomial of some matroids, arXiv:1203.0090.