Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Matroid
Summary
In combinatorics, a branch of mathematics, a matroid ˈmeɪtrɔɪd is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.
Matroid theory borrows extensively from the terminology of both linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications in geometry, topology, combinatorial optimization, network theory and coding theory.
There are many equivalent ways to define a (finite) matroid.
In terms of independence, a finite matroid is a pair , where is a finite set (called the ground set) and is a family of subsets of (called the independent sets) with the following properties:
(I1) The empty set is independent, i.e., .
(I2) Every subset of an independent set is independent, i.e., for each , if then . This is sometimes called the hereditary property, or the downward-closed property.
(I3) If and are two independent sets (i.e., each set is independent) and has more elements than , then there exists such that is in . This is sometimes called the augmentation property or the independent set exchange property.
The first two properties define a combinatorial structure known as an independence system (or abstract simplicial complex). Actually, assuming (I2), property (I1) is equivalent to the fact that at least one subset of is independent, i.e., .
Basis of a matroid
A subset of the ground set that is not independent is called dependent. A maximal independent set—that is, an independent set that becomes dependent upon adding any element of —is called a basis for the matroid. A circuit in a matroid is a minimal dependent subset of —that is, a dependent set whose proper subsets are all independent.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.