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. The rank functions of matroids defined from certain other types of mathematical object such as undirected graphs, matrices, and field extensions are important within the study of those objects. In all examples, E is the base set of the matroid, and B is some subset of E. Let M be the free matroid, where the independent sets are all subsets of E. Then the rank function of M is simply: r(B) = |B|. Let M be a uniform matroid, where the independent sets are the subsets of E with at most k elements, for some integer k. Then the rank function of M is: r(B) = min(k, |B|). Let M be a partition matroid: the elements of E are partitioned into categories, each category c has capacity kc, and the independent sets are those containing at most kc elements of category c. Then the rank function of M is: r(B) = sumc min(kc, |Bc|) where Bc is the subset B contained in category c. Let M be a graphic matroid, where the independent sets are all the acyclic edge-sets (forests) of some fixed undirected graph G. Then the rank function r(B) is the number of vertices in the graph, minus the number of connected components of B (including single-vertex components). The rank function of a matroid obeys the following properties. (R1) The value of the rank function is always a non-negative integer and the rank of the empty set is 0. (R2) For any two subsets and of , . That is, the rank is a submodular set function. (R3) For any set and element , .

À 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 (13)

Personnes associées (2)

Unités associées (3)

Concepts associés (7)

Cours associés (1)

Séances de cours associées (5)

Indépendance algébrique

En algèbre, l'indépendance algébrique d'un ensemble de nombres, sur un corps commutatif, décrit le fait que ses éléments ne sont pas racines d'un polynôme en plusieurs indéterminées à coefficients dans ce corps. Soient L un corps commutatif, S un sous-ensemble de L et K un sous-corps de L. On dit que S est algébriquement libre sur K, ou que ses éléments sont algébriquement indépendants sur K si, pour tout suite finie (s, ... , s) d'éléments distincts de S et tout polynôme non nul P(X, ...

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.

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.

CS-450: Algorithms II

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

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

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

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

Maryam Kamgarpour, Orcun Karaca, Dániel Tihanyi

This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and ...

2021

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call o ...

2021

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

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

Couvre les bases de l'algèbre linéaire, y compris le rang, les applications différenciables et les submersions.