A logical approach to matroid decomposition
106
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
106
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- following axioms
- equipe de logique mathematique
- i1 ?
- matroid must
- abstract construction
- decomposition
- branch-width decomposition
A logical approach to matroid decomposition
A logical approach to matroid decomposition
Yann Strozecki
Equipe de Logique Mathematique, Paris 7A logical approach to matroid decomposition
Introduction to Matroids
1 Introduction to Matroids
2 Branch-Width Decomposition
3 MSO and reduction to MSO on treesM
4 Applications and an example
5 Abstract construction of matroids1 ?2I
0 02 If I2I and I I , then I 2I
3 If I and I are inI andjIj<jIj, then there is an element e1 2 1 2
of I I such that I [ e2I.2 1 1
A logical approach to matroid decomposition
Introduction to Matroids
De nition
Matroids have been design to abstract the notion of dependence.
De nition
A matroid is a pair (E;I), E is a nite set and I is included in the
power set of E . Elements ofI are said to be independent sets, the
others are dependent sets.
A matroid must satisfy the following axioms:0 02 If I2I and I I , then I 2I
3 If I and I are inI andjIj<jIj, then there is an element e1 2 1 2
of I I such that I [ e2I.2 1 1
A logical approach to matroid decomposition
Introduction to Matroids
De nition
Matroids have been design to abstract the notion of dependence.
De nition
A matroid is a pair (E;I), E is a nite set and I is included in the
power set of E . Elements ofI are said to be independent sets, the
others are dependent sets.
A matroid must satisfy the following axioms:
1 ?2I3 If I and I are inI andjIj<jIj, then there is an element e1 2 1 2
of I I such that I [ e2I.2 1 1
A logical approach to matroid decomposition
Introduction to Matroids
De nition
Matroids have been design to abstract the notion of dependence.
De nition
A matroid is a pair (E;I), E is a nite set and I is included in the
power set of E . Elements ofI are said to be independent sets, the
others are dependent sets.
A matroid must satisfy the following axioms:
1 ?2I
0 02 If I2I and I I , then I 2IA logical approach to matroid decomposition
Introduction to Matroids
De nition
Matroids have been design to abstract the notion of dependence.
De nition
A matroid is a pair (E;I), E is a nite set and I is included in the
power set of E . Elements ofI are said to be independent sets, the
others are dependent sets.
A matroid must satisfy the following axioms:
1 ?2I
0 02 If I2I and I I , then I 2I
3 If I and I are inI andjIj<jIj, then there is an element e1 2 1 2
of I I such that I [ e2I.2 1 10 1
1 0 1 0 1
@ AA = 1 1 0 0 1
0 1 1 1 1
Here the setf1; 2; 4g is independent andf1; 2; 3g is dependent.
A logical approach to matroid decomposition
Introduction to Matroids
Vector matroid
The rst concrete example of matroid is the vector matroid.
Let A be a matrix, the ground set E is the set of the columns and
a set of columns is independent if the vectors are linearly
independent.A logical approach to matroid decomposition
Introduction to Matroids
Vector matroid
The rst concrete example of matroid is the vector matroid.
Let A be a matrix, the ground set E is the set of the columns and
a set of columns is independent if the vectors are linearly
independent.
0 1
1 0 1 0 1
@ AA = 1 1 0 0 1
0 1 1 1 1
Here the setf1; 2; 4g is independent andf1; 2; 3g is dependent.1
5
42
3
Here the setf1; 2; 4g is independent whereasf1; 2; 3; 4g and
f1; 2; 5g are dependent.
A logical approach to matroid decomposition
Introduction to Matroids
Cycle matroid
The second example is the cycle matroid of a graph.
Let G be a graph, the ground set of his cycle matroid is E the set
of his edges.
A set is said to be dependent if it contains a cycle.A logical approach to matroid decomposition
Introduction to Matroids
Cycle matroid
The second example is the cycle matroid of a graph.
Let G be a graph, the ground set of his cycle matroid is E the set
of his edges.
A set is said to be dependent if it contains a cycle.
1
5
42
3
Here the setf1; 2; 4g is independent whereasf1; 2; 3; 4g and
f1; 2; 5g are dependent.
