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.
Richard M. Karp
791442
de