Matroid

Matroid is a classification of subsets of a certain set , which is a generalization of the idea of independence of elements, similar to the independence of elements of linear space , on an arbitrary set.

Content

1 Axiomatic definition
2 Definition in terms of cycles
3 Definition in terms of correct closure
4 Examples
5 Additional concepts
6 Matroid Fano
7 Theorems
8 Application
9 Literature
10 References and notes

Axiomatic definition

Matroid - pair $(X,I)$ ${\ displaystyle (X, I)}$ where $X$ ${\ displaystyle X}$ - a finite set called the carrier of the matroid , and $I$ ${\ displaystyle I}$ - some set of subsets $X$ ${\ displaystyle X}$ called a family of independent sets , i.e. $I\subset$ ${\ displaystyle I \ subset}$ $2^{X}$ ${\ displaystyle 2 ^ {X}}$ . The following conditions must be met:

$\varnothing \in I$ ${\ displaystyle \ varnothing \ in I}$ .
If $A\in I$ ${\ displaystyle A \ in I}$ and $B\subset A$ ${\ displaystyle B \ subset A}$ then $B\in I$ ${\ displaystyle B \ in I}$ .
If $A,B\in I$ ${\ displaystyle A, B \ in I}$ and power A is greater than power B, then there $x\in A\setminus B$ ${\ displaystyle x \ in A \ setminus B}$ such that $B\cup \{x\}\in I$ ${\ displaystyle B \ cup \ {x \} \ in I}$ .

Matroid bases are called independent maximum sets with respect to inclusion. Subsets $X$ ${\ displaystyle X}$ not owned $I$ ${\ displaystyle I}$ are called dependent sets . Minimum inclusion dependent sets are called matroid cycles . This concept is used in an alternative definition of a matroid.

Definition in terms of loops

Matroid - pair $(X,C)$ ${\ displaystyle (X, C)}$ where $X$ ${\ displaystyle X}$ - the carrier of the matroid, and $C$ ${\ displaystyle C}$ - a family of nonempty subsets $X$ ${\ displaystyle X}$ , called the set of cycles of the matroid , for which the following conditions are true: ^[1]

No cycle is a subset of another
If $x\in C_{1}\cap C_{2}$ ${\ displaystyle x \ in C_ {1} \ cap C_ {2}}$ then $C_{1}\cup C_{2}\setminus \{x\}$ ${\ displaystyle C_ {1} \ cup C_ {2} \ setminus \ {x \}}$ contains a loop

Definition in terms of correct closure

Let be $(P,\leq )$ ${\ displaystyle (P, \ leq)}$ - partially ordered set . $H:P\to P$ ${\ displaystyle H: P \ to P}$ - circuit in $(P,\leq )$ ${\ displaystyle (P, \ leq)}$ , if

For any x from P : $H(x)\geq x$ ${\ displaystyle H (x) \ geq x}$ .
For any x , y from P : $x\leq y\Rightarrow H(x)\leq H(y)$ ${\ displaystyle x \ leq y \ Rightarrow H (x) \ leq H (y)}$ .
For any x from P : $H{\big (}H(x){\big )}=H(x)$ ${\ displaystyle H {\ big (} H (x) {\ big)} = H (x)}$ .

Consider $(P,\leq )=(2^{S},\leq )$ ${\ displaystyle (P, \ leq) = (2 ^ {S}, \ leq)}$ case when a partially ordered set is a Boolean algebra . Let be $A\to H(A)$ ${\ displaystyle A \ to H (A)}$ - closure $A\subset S$ ${\ displaystyle A \ subset S}$ .

A closure is correct (axiom of correct closure) if $(p\not \in A,p\in H(A\cup \{q\}))\Rightarrow q\in H(A\cup \{p\})$ ${\ displaystyle (p \ not \ in A, p \ in H (A \ cup \ {q \})) \ Rightarrow q \ in H (A \ cup \ {p \})}$
for anyone $A$ $\subset$ $S$ {\ displaystyle A \ subset S} there is such $B$ $\subset$ $A$ {\ displaystyle B \ subset A} , what
1. $|B|<+\infty$ ${\ displaystyle | B | <+ \ infty}$
2. $H\left(B\right)=H\left(A\right)$ ${\ displaystyle H \ left (B \ right) = H \ left (A \ right)}$

Couple $(S,A\to H(A))$ ${\ displaystyle (S, A \ to H (A))}$ where $A\to H(A)$ ${\ displaystyle A \ to H (A)}$ - correct short circuit to $(2^{S},\leq )$ ${\ displaystyle (2 ^ {S}, \ leq)}$ is called a matroid .

Examples

Universal Matroid U _nk . The set X has cardinality n, the independent sets are the subsets with cardinality no greater than k. Bases are subsets of cardinality k.
Matroid cycles graph. The set X is the set of edges of the graph , the independent sets are the acyclic subsets of these edges, the cycles are simple cycles of the graph. The bases are the spanning forests of the count. A matroid is called graphical if it is a matroid of cycles of some graph. ^[2]
A matroid of subsets of the set of edges of a graph, such that removing the subset leaves the graph connected.
Matroid of cocycle graph. The set X is the set of edges, cocycles are minimal sets, the removal of which leads to the loss of graph connectivity. A matroid is called cographic if it is a matroid of cocycles of some graph. ^[2]
Matrix Matroid. The family of all linearly independent subsets of any finite set of vectors of an arbitrary nonempty vector space is a matroid.

We define the set E as the set consisting of {1, 2, 3, .., n } - column numbers of some matrix , and the set I as the set consisting of subsets of E such that the vectors defined by them are linearly independent over the field of real numbers R. Let us ask ourselves - what properties does the constructed set I have?

The set I is nonempty. Even if the original set E was empty - E = ∅, then I will consist of one element - a set containing empty. I = {{∅}}.
Any subset of any element of the set I will also be an element of this set. This property is understandable - if a certain set of vectors is linearly independent over the field, then any subset of it will also be linearly independent.
If A, B ∈ I, and | A | = | B | + 1, then there exists an element x ∈ A - B such that B ∪ {x} ∈ I.

Let us prove that in the considered example, the set of linearly independent columns is indeed a matroid. To do this, it is enough to prove the third property from the definition of a matroid. We carry out the proof by contradiction.

Evidence. Let A, B ∈ I and | A | = | B | + 1. Let W be the space of vectors spanned by A ∪ B. It is clear that its dimension will be no less than | A |. Suppose that B ∪ {x} is linearly dependent for all x ∈ A - B (that is, the third property will not hold). Then B forms a basis in the space W. It follows that | A | ≤ dim W ≤ | B |. But since, by hypothesis, A and B consist of linearly independent vectors and | A | > | B |, we obtain a contradiction. So many vectors will be a matroid.

Additional concepts

Dual to this matroid is called a matroid, the carrier of which coincides with the carrier of the given matroid, and the base is the complement of the bases of this matroid to the carrier. That is, X ^* = X, and the set of bases of the dual matroid is the set of B ^* such that B ^* = X \ B, where B is the base of the given matroid.
A cycle (or chain ) in a matroid is a set A ⊂ X such that A ∉ I, and for any B ⊂ A, if B ≠ A, then B ∈ I
The rank of a matroid is the power of its bases. The rank of the trivial matroid is zero.

Matroid Fano

Matroids with a small number of elements are often depicted in the form of diagrams. Points are elements of the main set, and the curves are “stretched” through each three-element chain. The diagram shows a 3-ranked matroid, called the Fano matroid, an example that appeared in a 1935 article by Whitney .

The name came from the fact that the Fano matroid is a second-order projective plane , known as the Fano plane , whose coordinate field is a two-element field. This means that the Fano matroid is a vector matroid connected with seven nonzero vectors in three-dimensional vector space above the field of two elements.

It is known from projective geometry that a Fano matroid is not representable by an arbitrary set of vectors in a real or complex vector space (or in any vector space above a field whose characteristics differ from 2).

Theorems

All matroid bases have the same power .
The matroid is uniquely defined by the carrier and the bases.
A cycle cannot be a subset of another cycle.
If $C_{1}$ ${\ displaystyle C_ {1}}$ and $C_{2}$ ${\ displaystyle C_ {2}}$ - cycles then for any $x\in C_{1}\cap C_{2}:C_{1}\cup C_{2}\setminus \{x\}$ ${\ displaystyle x \ in C_ {1} \ cap C_ {2}: C_ {1} \ cup C_ {2} \ setminus \ {x \}}$ contains a loop.
If $B$ ${\ displaystyle B}$ - base and $x\notin B$ ${\ displaystyle x \ notin B}$ then $B\cup \{x\}$ ${\ displaystyle B \ cup \ {x \}}$ contains exactly one cycle.

Application

Matroids well describe the class of problems that allow a "greedy" solution. See the greedy Rado - Edmonds algorithm
Matroids in combinatorial optimization

Literature

Asanov M. O. et al. Discrete mathematics: graphs, matroids, algorithms. - Izhevsk: NSC “Regular and chaotic dynamics”, 2001. - P. 288.
F. Harari. Graph theory. - Moscow: URSS , 2003. - S. 300. ISBN 5-354-00301-6
Novikov F.A. Discrete mathematics for programmers. - 3rd. - SPb. : Peter , 2008 .-- S. 101-105. - 384 p. - ISBN 978-5-91180-759-7 .

References and notes

http://rain.ifmo.ru/cat/view.php/theory/unsorted/matroids-2004/

↑ F. Harari. Graph Theory , p. 57.
↑ ¹ ² F. Harari. Graph Theory , p. 186.

[Harary_57-1] F. Harari. Graph Theory , p. 57.

[Harary_186-2] ¹ ² F. Harari. Graph Theory , p. 186.