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. 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. The Vámos matroid is a paving matroid, meaning that all of its circuits have size at least equal to its rank. 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). 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. 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 for the matroids representable over a field , whenever has five or more elements. 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. The Vámos matroid is not algebraic.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (10)

Personnes associées (1)

Unités associées (2)

Concepts associés (3)

Cours associés (1)

Séances de cours associées (3)

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

Entropic Matroids and Their Representation

Emmanuel Abbé

This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have support of cardinality p. We draw ...

2019

An Improved Analysis of Local Search for Max-Sum Diversification

Friedrich Eisenbrand, Rico Zenklusen, Alfonso Bolívar Cevallos Manzano

We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so th ...

INFORMS2019

Matroid rank

In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks. The rank function is one of the fundamental concepts of matroid theory via which matroids may be axiomatized. Matroid rank functions form an important subclass of the submodular set functions.

Matroid representation

In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of representation provide abstract algebraic structures (matroids and groups respectively) with concrete descriptions in terms of linear algebra. A linear matroid is a matroid that has a representation, and an F-linear matroid (for a field F) is a matroid that has a representation using a vector space over F.

Matroïde

En mathématiques, et plus particulièrement en combinatoire, un matroïde est une structure introduite comme un cadre général pour le concept d'indépendance linéaire. Elle est donc naturellement liée à l'algèbre linéaire (déjà au niveau du vocabulaire : indépendant, base, rang), mais aussi à la théorie des graphes (circuit, cycle), à l'algorithmique (algorithme glouton), et à la géométrie (pour diverses questions liées à la représentation). La notion a été introduite en 1935 par Whitney. Le mot matroïde provient du mot matrice.

Matroids: Intersection matroid CS-450: Algorithms II

Couvre le concept de matroids, se concentrant sur l'intersection matroid et les propriétés des sous-ensembles d'un ensemble de sol.

Algorithmes Greedy & Matroids CS-450: Algorithms II

Introduit des algorithmes et des matroids gourmands, soulignant leur efficacité dans la résolution de problèmes d'optimisation.

Minimisation des fonctions submodulaires CS-450: Algorithms II

Couvre les fonctions sous-modulaires et leur minimisation, en mettant l'accent sur les rendements décroissants et l'extension Lovsz.

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper