Vámos Matroid
   HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the Vámos matroid or Vámos cube is a
matroid In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...
over a set of eight elements that cannot be represented as a matrix over any
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
. It is named after English mathematician
Peter Vámos Peter may refer to: People * List of people named Peter, a list of people and fictional characters with the given name * Peter (given name) ** Saint Peter (died 60s), apostle of Jesus, leader of the early Christian Church * Peter (surname), a sur ...
, who first described it in an unpublished manuscript in 1968.


Definition

The Vámos matroid has eight elements, which may be thought of as the eight vertices of a
cube A cube or regular hexahedron is a three-dimensional space, three-dimensional solid object in geometry, which is bounded by six congruent square (geometry), square faces, a type of polyhedron. It has twelve congruent edges and eight vertices. It i ...
or
cuboid In geometry, a cuboid is a hexahedron with quadrilateral faces, meaning it is a polyhedron with six Face (geometry), faces; it has eight Vertex (geometry), vertices and twelve Edge (geometry), edges. A ''rectangular cuboid'' (sometimes also calle ...
. 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 In the mathematical field of graph theory, the diamond graph is a planar, undirected graph with 4 vertices and 5 edges. It consists of a complete graph minus one edge. The diamond graph has radius 1, diameter 2, girth 3, chroma ...
, and a four-element circuit for each edge of the diamond graph.


Properties

*The Vámos matroid is a
paving matroid In the mathematical theory of matroids, a paving matroid is a matroid in which every circuit has size at least as large as the matroid's rank. In a matroid of rank r every circuit has size at most r+1, so it is equivalent to define paving matroids ...
, meaning that all of its circuits have size at least equal to its
rank A rank is a position in a hierarchy. It can be formally recognized—for example, cardinal, chief executive officer, general, professor—or unofficial. People Formal ranks * Academic rank * Corporate title * Diplomatic rank * Hierarchy ...
.. *The Vámos matroid is isomorphic to its
dual matroid Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual number, a ...
, but it is not identically self-dual (the isomorphism requires a nontrivial permutation of the matroid elements). *The Vámos matroid cannot be represented over any field. That is, it is not possible to find a
vector space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
, and a system of eight vectors within that space, such that the matroid of
linear independence In the theory of vector spaces, a set (mathematics), set of vector (mathematics), vectors is said to be if there exists no nontrivial linear combination of the vectors that equals the zero vector. If such a linear combination exists, then th ...
of these vectors is isomorphic to the Vámos matroid. Indeed, it is one of the smallest non-representable matroids, and served as a counterexample to a conjecture of Ingleton that the matroids on eight or fewer elements were all representable. *The Vámos matroid is a
forbidden minor Forbidden may refer to: Science * Forbidden mechanism, a spectral line associated with absorption or emission of photons Films * ''Forbidden'' (1919 film), directed by Phillips Smalley and Lois Weber * ''Forbidden'' (1932 film), directed by Fra ...
for the matroids representable over a field F, whenever F has five or more elements., p. 511. However, it is not possible to test in
polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
whether it is a minor of a given matroid M, given access to M through an independence oracle. *The Vámos matroid is not algebraic. That is, there do not exist a
field extension In mathematics, particularly in algebra, a field extension is a pair of fields K \subseteq L, such that the operations of ''K'' are those of ''L'' restricted to ''K''. In this case, ''L'' is an extension field of ''K'' and ''K'' is a subfield of ...
L/K and a set of eight elements of L, such that the
transcendence degree In mathematics, a transcendental extension L/K is a field extension such that there exists an element in the field L that is transcendental over the field K; that is, an element that is not a root of any univariate polynomial with coefficients ...
of sets of these eight elements equals the rank function of the matroid. *The Vámos matroid is not a secret-sharing matroid. Secret-sharing matroids describe "ideal"
secret sharing Secret sharing (also called secret splitting) refers to methods for distributing a secrecy, secret among a group, in such a way that no individual holds any intelligible information about the secret, but when a sufficient number of individuals c ...
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. These matroids also have applications in
coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and computer data storage, data sto ...
. *The Vámos matroid has no adjoint. This means that the
dual lattice In the theory of lattices, the dual lattice is a construction analogous to that of a dual vector space. In certain respects, the geometry of the dual lattice of a lattice L is the reciprocal of the geometry of L , a perspective which underl ...
of the
geometric lattice In the mathematics of matroids and lattices, a geometric lattice is a finite atomistic semimodular lattice, and a matroid lattice is an atomistic semimodular lattice without the assumption of finiteness. Geometric lattices and matroid lattices, ...
of the Vámos matroid cannot be order-embedded into another geometric lattice of the same rank. *The Vámos matroid can be
oriented In mathematics, orientability is a property of some topological spaces such as real vector spaces, Euclidean spaces, surfaces, and more generally manifolds that allows a consistent definition of "clockwise" and "anticlockwise". A space is ori ...
. In oriented matroids, a form of the
Hahn–Banach theorem In functional analysis, the Hahn–Banach theorem is a central result that allows the extension of bounded linear functionals defined on a vector subspace of some vector space to the whole space. The theorem also shows that there are sufficient ...
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. *The
Tutte polynomial The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...
of the Vámos matroid is. *:x^4+4x^3+10x^2+15x+5xy+15y+10y^2+4y^3+y^4.


References

{{DEFAULTSORT:Vamos matroid Matroid theory