Connections between graphs and matroids

OData support
Supervisor:
Dr. Recski András
Department of Computer Science and Information Theory

Matroids, in a way, can be considered as a common generalization of graphs and matrices. What they really represent is instead an extended notion of linear (in)dependency regarding families of subsets defined by a specific axiom set. Research in the field of matroids can lead to deep results in may branch of mathematics: from generalization of linear algebra through combinatorical optimization tasks to graph theory proofs and algorithms.

The purpose of this paper is to give a survey on the most important concepts of matroid theory in order to reach our goal of being able to thoroughly analyse a specific field within matroid theory in the future: the matroids whose definition can be given through different kinds of graphs. At the end of this paper do we reach the point when we are able to define the most known case of a matroid induced by a graph: the transversal matroids, arising from bipartite graphs. Still, it is a long way there, as only the precise understanding of notions and concepts can lead to perceive the meaning, importance of matroids, and their relation or correspondence to well-known concepts within linear algebra, combinatorics and graph theory.

Downloads

Please sign in to download the files of this thesis.