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

References

  1. Vámos, P. (1968), On the representation of independence structures.
  2. 1 2 Oxley, James G. (2006), "Example 2.1.22", Matroid Theory, Oxford Graduate Texts in Mathematics, 3, Oxford University Press, p. 76, ISBN 9780199202508.
  3. Oxley (2006), pp. 170–172.
  4. 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.
  5. Ingleton, A. W. (1959), "A note on independence functions and rank", Journal of the London Mathematical Society, Second Series, 34: 49–56, MR 0101848, doi:10.1112/jlms/s1-34.1.49.
  6. Oxley (2006), p. 511.
  7. Seymour, P. D.; Walton, P. N. (1981), "Detecting matroid minors", Journal of the London Mathematical Society, Second Series, 23 (2): 193–203, MR 609098, doi:10.1112/jlms/s2-23.2.193. Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing, 11 (1): 184–190, MR 646772, doi:10.1137/0211014.
  8. Ingleton, A. W.; Main, R. A. (1975), "Non-algebraic matroids exist", Bulletin of the London Mathematical Society, 7: 144–146, MR 0369110, doi:10.1112/blms/7.2.144.
  9. Seymour, P. D. (1992), "On secret-sharing matroids", Journal of Combinatorial Theory, Series B, 56 (1): 69–73, MR 1182458, doi:10.1016/0095-8956(92)90007-K.
  10. 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.
  11. Simonis, Juriaan; Ashikhmin, Alexei (1998), "Almost affine codes", Designs, Codes and Cryptography, 14 (2): 179–197, MR 1614357, doi:10.1023/A:1008244215660.
  12. Cheung, Alan L. C. (1974), "Adjoints of a geometry", Canadian Mathematical Bulletin, 17 (3): 363–365; correction, ibid. 17 (1974), no. 4, 623, MR 0373976, doi:10.4153/CMB-1974-066-5.
  13. Bland, Robert G.; Las Vergnas, Michel (1978), "Orientability of matroids", Journal of Combinatorial Theory, Series B, 24 (1): 94–123, MR 0485461, doi:10.1016/0095-8956(78)90080-1.
  14. Bachem, Achim; Wanka, Alfred (1988), "Separation theorems for oriented matroids", Discrete Mathematics, 70 (3): 303–310, MR 955127, doi:10.1016/0012-365X(88)90006-4.
  15. Merino, Criel; Ramírez-Ibáñez, Marcelino; Sanchez, Guadalupe Rodríguez (2012), The Tutte polynomial of some matroids, arXiv:1203.0090Freely accessible.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.