Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Topics in matroid union
View through CrossRef
The operation of matroid union was introduced by Nash-Williams in 1966. A
matroid is indecomposable if it cannot be written in the form M = M1 V
M2, where r(M1),r(M2) > 0. In 1971 Welsh posed the problem of
characterizing indecomposable matroids, this problem has turned out to
be extremely difficult. As a partial solution towards its progress,
Cunningham characterized binary indecomposable matroids in 1977. In this
thesis we present numerous results in topics of matroid union. Those
include a link between matroid connectivity and matroid union, such as
the implication of having a 2-separation in the matroid union, and under
what conditions is the union 3-connected. We also identify which
elements in binary and ternary matroids are non-fixed. Then we create a
link between having non-fixed elements in binary and ternary matroids
and the decomposability of such matroids, and the effect of removing
non-fixed elements from binary and ternary matroids. Moreover, we show
results concerning decomposable 3-connected ternary matroids, such as
what essential property every decomposable 3-connected ternary matroid
must have, how to compose a ternary matroid, and what a 3-connected
ternary matroid decomposes into. We also give an alternative statement
and an alternative proof of Cunningham's theorem from the perspective of
fixed and non-fixed elements.
Title: Topics in matroid union
Description:
The operation of matroid union was introduced by Nash-Williams in 1966.
A
matroid is indecomposable if it cannot be written in the form M = M1 V
M2, where r(M1),r(M2) > 0.
In 1971 Welsh posed the problem of
characterizing indecomposable matroids, this problem has turned out to
be extremely difficult.
As a partial solution towards its progress,
Cunningham characterized binary indecomposable matroids in 1977.
In this
thesis we present numerous results in topics of matroid union.
Those
include a link between matroid connectivity and matroid union, such as
the implication of having a 2-separation in the matroid union, and under
what conditions is the union 3-connected.
We also identify which
elements in binary and ternary matroids are non-fixed.
Then we create a
link between having non-fixed elements in binary and ternary matroids
and the decomposability of such matroids, and the effect of removing
non-fixed elements from binary and ternary matroids.
Moreover, we show
results concerning decomposable 3-connected ternary matroids, such as
what essential property every decomposable 3-connected ternary matroid
must have, how to compose a ternary matroid, and what a 3-connected
ternary matroid decomposes into.
We also give an alternative statement
and an alternative proof of Cunningham's theorem from the perspective of
fixed and non-fixed elements.
Related Results
Parallel algorithms for matroid intersection and matroid parity
Parallel algorithms for matroid intersection and matroid parity
A maximum linear matroid parity set is called a basic matroid parity set, if its size is the rank of the matroid. We show that determining the existence of a common base (basic mat...
Covering Cycle Matroid
Covering Cycle Matroid
Covering is a type of widespread data representation while covering-based rough sets provide an efficient and systematic theory to deal with this type of data. Matroids are based o...
Faster Matroid Partition Algorithms
Faster Matroid Partition Algorithms
In the matroid partitioning problem, we are given
\(k\)
matroids
\(\mathcal{M}_{1}=(V,\mathcal{I}_{1}...
Matroids, Cyclic Flats, and Polyhedra
Matroids, Cyclic Flats, and Polyhedra
<p>Matroids have a wide variety of distinct, cryptomorphic axiom systems that are capable of defining them. A common feature of these is that they are able to be efficiently ...
On Density-Critical Matroids
On Density-Critical Matroids
For a matroid $M$ having $m$ rank-one flats, the density $d(M)$ is $\tfrac{m}{r(M)}$ unless $m = 0$, in which case $d(M)= 0$. A matroid is density-critical if all of its proper min...
On analogs of Cremona automorphisms for matroid fans
On analogs of Cremona automorphisms for matroid fans
Matroids are combinatorial objects that generalize linear independence. A matroid can be represented geometrically by its Bergman fan and we compare the symmetries of these two obj...
K-Regular Matroids
K-Regular Matroids
<p>The class of matroids representable over all fields is the class of regular matroids. The class of matroids representable over all fields except perhaps GF(2) is the class...
Matroid Applications and Algorithms
Matroid Applications and Algorithms
Matroid theory provides a set of modeling tools with which many combinatorial and algebraic problems may be treated. Generic algorithms for the resulting matroid problems can be us...