Independence system

In combinatorics, an independence system is a generalization of the mathematical structure of the matroid . An independence system consists of a finite ground set and it defined non-empty set system , the terms of subsets formation completed is. ${\displaystyle (E,U)}$ ${\displaystyle E}$ ${\displaystyle U}$

Many problems of combinatorial optimization can be described as minimization or maximization problems in an independence system.

Definitions

Let be any finite basic set and a system of subsets of (thus ), then the pair is an independence system if the following conditions are met: ${\displaystyle E}$ ${\displaystyle {\mathcal {U}}}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {U}}\subseteq {\mathcal {P}}(E)}$ ${\displaystyle (E,{\mathcal {U}})}$

1. ${\displaystyle \emptyset \in {\mathcal {U}}}$(Not to be confused with what would be trivial, since the empty set is a subset of any set.) ${\displaystyle \emptyset \subseteq {\mathcal {U}}}$
2. ${\displaystyle A\subseteq B,B\in {\mathcal {U}}\Rightarrow A\in {\mathcal {U}}}$( is closed at the bottom .) ${\displaystyle {\mathcal {U}}}$ ${\displaystyle \subseteq }$

1. is equivalent to the requirement that is not empty. ${\displaystyle {\mathcal {U}}}$

Adding the so-called exchange property turns an independence system into a matroid .

Independent, dependent

The elements from are called independent, the subsets of that are not contained in are called dependent. ${\displaystyle {\mathcal {U}}}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {U}}}$

Base

If an independent set is maximal, then it is called the base (based on the analogous term in connection with linear independence ). ${\displaystyle B\in {\mathcal {U}}}$

circle

If a dependent set is minimal (i.e. all real subsets of are independent), it is called a circle (based on the concept of circle from graph theory). ${\displaystyle K\in {\mathcal {P}}(E)\setminus {\mathcal {U}}}$ ${\displaystyle K}$

Rank function

The rank function is defined as for all subsets . ${\displaystyle r\colon {\mathcal {P}}(E)\to \mathbb {N} _{0}}$ ${\displaystyle r(F)=\max\{|A|\mid A\in {\mathcal {U}},\ A\subseteq F\}}$ ${\displaystyle F\subset E}$

The following applies to the ranking function defined in this way : ${\displaystyle r\colon {\mathcal {P}}(E)\to \mathbb {N} _{0}}$

• ${\displaystyle 0\leq r(A)\leq |A|}$
• From follows ${\displaystyle A\subseteq B}$ ${\displaystyle r(A)\leq r(B)}$

Lower rank function

The lower rank function is defined as for all subsets . ${\displaystyle \rho \colon {\mathcal {P}}(E)\to \mathbb {N} _{0}}$ ${\displaystyle \rho (F)=\min\{|A|\mid A\subseteq F,A\in {\mathcal {U}}{\text{ und }}A\cup \{x\}\not \in {\mathcal {U}}\ \forall x\in F\setminus A\}}$ ${\displaystyle F\subset E}$

Rank quotient

The rank quotient of is defined as ${\displaystyle (E,{\mathcal {U}})}$

${\displaystyle q(E,{\mathcal {U}}):=\min _{F\subseteq E}{\frac {\rho (F)}{r(F)}}.}$

In an independence system, the rank quotient is less than or equal to one and equal to one if the independence system is a matroid.

Hull operator

For a subset is the envelope operator . ${\displaystyle A\subseteq E}$ ${\displaystyle s(A)=\{x\in E\mid r(A\cup \{x\})=r(A)\}}$

For this applies:

• ${\displaystyle A\subseteq s(A)}$( Extensive figure )
• From it follows ( monotony ) ${\displaystyle A\subseteq B}$ ${\displaystyle s(A)\subseteq s(B)}$
• ${\displaystyle s(A)=s(s(A))}$( Idempotence )

properties

Every independence system can be represented as the average of a finite number of matroids.

Examples

• Let be a vector space over a finite field and the set of all linearly independent subsets of . (This example motivates the designation. One can generalize this example to non-finite fields, but then many of the statements made here about independence systems no longer apply.) ${\displaystyle E}$ ${\displaystyle {\mathcal {U}}}$ ${\displaystyle E}$
• Let be an arbitrary finite set, a natural number and the set of all subsets of at most -element . ${\displaystyle E}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {U}}}$ ${\displaystyle n}$ ${\displaystyle E}$
• The pairing in a bipartite graph can be represented as the intersection of two matroids and is therefore an independence system.
• The traveling salesman problem can be represented as the average of three matroids and is therefore also an independence system.

literature

• James Oxley: Matroid Theory . Oxford Mathematics, 1992, ISBN 0-19-920250-8 .
• Bernhardt Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. 4th edition. Springer, 2007, ISBN 978-3-540-71843-7 .
• Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization. Algorithms and Complexity. Prentice Hall, 1982, ISBN 0-13-152462-3 .
• Jon Lee: A First Course in Combinatorial Optimization . Cambridge Texts in Applied Mathematics, 2004, ISBN 0-521-01012-8 .
• Sven Oliver Krumke, Hartmut Noltemeier: Graph theory concepts and algorithms . 2nd Edition. Vieweg-Teubner, 2009, ISBN 978-3-8348-0629-1 .

Individual evidence

1. ^ Idea of ​​proof in Bernhardt Korte and Jens Vygen: Combinatorial Optimization. 4th edition. P. 323.
2. ↑ Detailed proof using the rank quotient in you, Ding-zhu: Design and Analysis of Computer Algorithms ( Lecture Notes 2008  ( page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and remove it then this note. ( ppt ; 373 kB)). P. 24.  
3. ^ Korte and Vygen: Combinatorial Optimization 4th Edition. P. 323.
4. ↑ First mentioned in Michael Held, Richard M. Karp : The traveling-salesman problem and minimum spanning trees . ( pdf ). 1969, p. 24.
5. ↑ General definition of the independence system and proof of the third matroid in Jon Lee: A First Course in Combinatorial Optimization . 2004, p. 89.
6. ^ Proof of the first two matroids in Korte and Vygen: Combinatorial Optimization. 4th edition. P. 307.