Independence system
An independence system is in combinatorics a generalization of the mathematical structure of the matroid. An independence system consists of a finite ground set and an empty set about undefined system that is closed under subset formation.
Can be described as a minimization or maximization problem in an independence system Many problems of combinatorial optimization.
Definitions
Be an arbitrary finite ground set and a system of subsets of (ie ), then the pair is an independence system if the following conditions are met:
1 equivalent to the request that is not empty.
By adding the so-called exchange property arises from an independence system is a matroid.
Regardless, depending
The items are called independent subsets of which are not included, it is called dependent.
Base
Is an independent set maximum, so they are called base (similar to the analogous concept in the context of linear independence).
Circle
Is a dependent quantity minimal, so they are called circle (similar to the circle concept from graph theory ).
Rank function
The ranking function is defined as for all subsets.
For the so defined rank function is:
- It follows from
Lower ranking function
The lower ranking function ( engl. lower rank ) is defined as for all subsets.
Rank quotient
The rank is defined as the quotient of
In an independence system of rank quotient is less equal to one and equal to one when the independence system is a matroid.
Closure operator
For a subset is the closure operator.
For this is true:
- (Extensive image )
- It follows from ( monotony )
- ( Idempotency )
Properties
Each independence system can be represented as the intersection of finitely many matroids.
Examples
- Be a vector space over a finite field and the set of all linearly independent subsets of. (This example motivates the name. One can generalize this example to non finite fields, but then many of the statements made here about independence systems are no longer applicable. )
- Be an arbitrary finite set is a natural number and the set of all subsets of at most.
- The pairing in a bipartite graph can be represented as the intersection of two matroids and is thus an independence system.
- The problem of a Salesman can be represented as the intersection of three matroids and is thus also a system independence.