Köln, Universiẗat, Diss., 2003.

Matroids capture an abstraction of independence in mathematics, and in doing so, connect discrete mathematical structures that arise in a variety of contexts. A matroid can be defined in several cryptomorphic ways depending on which perspective of a matroid is most applicable to the given context. Among the many important concepts in matroid theory, the concept of matroid duality provides a powerful tool when addressing difficult problems. The usefulness of matroid duality stems from the fact that the dual of a matroid is itself a matroid. In this thesis, we explore a matroid-like object called a flag matroid. In particular, we suggest a notion of duality for flag matroids and we investigate the implications of this notion.

In this thesis we will present two main theorems that can be used to study minor minimal non even cut matroids. Given any signed graph we can associate an even cut matroid. However, given an even cut matroid, there are in general, several signed graphs which represent that matroid. This is in contrast to, for instance graphic (or cographic) matroids, where all graphs corresponding to a particular graphic matroid are essentially equivalent. To tackle the multiple non equivalent representations of even cut matroids we use the concept of Stabilizer first introduced by Wittle. Namely, we show the following: given a "substantial" signed graph, which represents a matroid N that is a minor of a matroid M, then if the signed graph extends to a signed graph which represents M then it does so uniquely. Thus the representations of the small matroid determine the representations of the larger matroid containing it. This allows us to consider each representation of an even cut matroid essentially independently. Consider a small even cut matroid N that is a minor of a matroid M that is not an even cut matroid. We would like to prove that there exists a matroid N' which contains N and is contained in M such that the size of N' is small and such that N' is not an even cut matroid (this would imply in particular that there are only finitely many minimally non even cut matroids containing N). Clearly, none of the representations of N extends to M. We will show that (under certain technical conditions) starting from a fixed representation of N, there exists a matroid N' which contains N and is contained in M such that the size of N' is small and such that the representation of N does not extend to N'.

In this thesis we will present two main theorems that can be used to study minor minimal non even cut matroids. Given any signed graph we can associate an even cut matroid. However, given an even cut matroid, there are in general, several signed graphs which represent that matroid. This is in contrast to, for instance graphic (or cographic) matroids, where all graphs corresponding to a particular graphic matroid are essentially equivalent. To tackle the multiple non equivalent representations of even cut matroids we use the concept of Stabilizer first introduced by Wittle. Namely, we show the following: given a "substantial" signed graph, which represents a matroid N that is a minor of a matroid M, then if the signed graph extends to a signed graph which represents M then it does so uniquely. Thus the representations of the small matroid determine the representations of the larger matroid containing it. This allows us to consider each representation of an even cut matroid essentially independently. Consider a small even cut matroid N that is a minor of a matroid M that is not an even cut matroid. We would like to prove that there exists a matroid N' which contains N and is contained in M such that the size of N' is small and such that N' is not an even cut matroid (this would imply in particular that there are only finitely many minimally non even cut matroids containing N). Clearly, none of the representations of N extends to M. We will show that (under certain technical conditions) starting from a fixed representation of N, there exists a matroid N' which contains N and is contained in M such that the size of N' is small and such that the representation of N does not extend to N'.

This thesis deals with questions relating to the maximum density of rank-n matroids in a minor-closed class. Consider a minor-closed class M of matroids that does not contain a given rank-2 uniform matroid. The growth rate function is defined by h_M(n) = max(|N| : N ∈ M simple, r(N) ≤ n). The Growth Rate Theorem, due to Geelen, Kabell, Kung, and Whittle, shows that the growth rate function is either linear, quadratic, or exponential in n. In the case of exponentially dense classes, we conjecture that, for sufficiently large n, h_M(n) = (q^(n+k) − 1)/(q-1) − c, where q is a prime power, and k and c are non-negative integers depending only on M. We show that this holds for several interesting classes, including the class of all matroids with no U_{2,t}-minor. We also consider more general minor-closed classes that exclude an arbitrary uniform matroid. Here the growth rate, as defined above, can be infinite. We define a more suitable notion of density, and prove a growth rate theorem for this more general notion, dividing minor-closed classes into those that are at most polynomially dense, and those that are exponentially dense.

This thesis deals with questions relating to the maximum density of rank-n matroids in a minor-closed class. Consider a minor-closed class M of matroids that does not contain a given rank-2 uniform matroid. The growth rate function is defined by h_M(n) = max(|N| : N ∈ M simple, r(N) ≤ n). The Growth Rate Theorem, due to Geelen, Kabell, Kung, and Whittle, shows that the growth rate function is either linear, quadratic, or exponential in n. In the case of exponentially dense classes, we conjecture that, for sufficiently large n, h_M(n) = (q^(n+k) − 1)/(q-1) − c, where q is a prime power, and k and c are non-negative integers depending only on M. We show that this holds for several interesting classes, including the class of all matroids with no U_{2,t}-minor. We also consider more general minor-closed classes that exclude an arbitrary uniform matroid. Here the growth rate, as defined above, can be infinite. We define a more suitable notion of density, and prove a growth rate theorem for this more general notion, dividing minor-closed classes into those that are at most polynomially dense, and those that are exponentially dense.

Let M be the class of simple matroids which do not contain the 5-point line U2,5 , the Fano plane F7 , the non-Fano plane F7- , or the matroid P7 , as minors. Let h(n) be the maximum number of points in a rank-n matroid in M. We show that h(2)=4, h(3)=7, and h(n)=n(n+1)/2 for n>3, and we also find all the maximum-sized matroids for each rank.

Matroidal networks are useful tools in furthering research in network coding. They have been used to show the limitations of linear coding solutions. In this paper we examine the basic information on network coding and matroid theory. We then go over the method of creating matroidal networks. Finally we construct matroidal networks from the dual of the fano matroid and the dual of the non-fano matroid, and breifly discuss some coding solutions.

The central theme of this thesis is to prove results about infinite mathematical objects by studying the behaviour of their finite substructures. In particular, we study B-matroids, which are an infinite generalization of matroids introduced by Higgs \cite{higgs}, and graph-like spaces, which are topological spaces resembling graphs, introduced by Thomassen and Vella \cite{thomassenvella}. Recall that the circuit matroid of a finite graph is a matroid defined on the edges of the graph, with a set of edges being independent if it contains no circuit. It turns out that graph-like continua and infinite graphs both have circuit B-matroids. The first main result of this thesis is a generalization of Whitney's Theorem that a graph has an abstract dual if and only if it is planar. We show that an infinite graph has an abstract dual (which is a graph-like continuum) if and only if it is planar, and also that a graph-like continuum has an abstract dual (which is an infinite graph) if and only if it is planar. This generalizes theorems of Thomassen (\cite{thomassendual}) and Bruhn and Diestel (\cite{bruhndiestel}). The difficult part of the proof is extending Tutte's characterization of graphic matroids (\cite{tutte2}) to finitary or co-finitary B-matroids. In order to prove this characterization, we introduce a technique for obtaining these B-matroids as the limit of a sequence of finite minors. In \cite{tutte}, Tutte proved important theorems about the peripheral (induced and non-separating) circuits of a $3$-connected graph. He showed that for any two edges of a $3$-connected graph there is a peripheral circuit containing one but not the other, and that the peripheral circuits of a $3$-connected graph generate its cycle space. These theorems were generalized to $3$-connected binary matroids by Bixby and Cunningham (\cite{bixbycunningham}). We generalize both of these theorems to $3$-connected binary co-finitary B-matroids. Richter, Rooney and Thomassen \cite{richterrooneythomassen} showed that a locally connected, compact metric space has an embedding in the sphere unless it contains a subspace homeomorphic to $K_5$ or $K_{3,3}$, or one of a small number of other obstructions. We are able to extend this result to an arbitrary surface $\Sigma$; a locally connected, compact metric space embeds in $\Sigma$ unless it contains a subspace homeomorphic to a finite graph which does not embed in $\Sigma$, or one of a small number of other obstructions.

Since its introduction in the year 2000 by Ahlswede et al., the network coding paradigm has revolutionized the way we understand information flows in networks. Traditionally, information transmitted in a communication network was treated as a commodity in a transportation network, much like cars on highways or fluids in pipes. This approach, however, fails to capture the very nature of information, which in contrast to material goods, can be coded and decoded. The network coding techniques take full advantage of the inherent properties of information, and allow the nodes in a network, not only to store and forward, but also to "mix", i.e., encode, their received data. This approach was shown to result in a substantial throughput gain over the traditional routing and tree packing techniques. In this dissertation, we study applications of network coding for guarantying reliable and secure information transmission in networks with compromised edges. First, we investigate the construction of robust network codes for achieving network resilience against link failures. We focus on the practical important case of unicast networks with non-uniform edge capacities where a single link can fail at a time. We demonstrate that these networks exhibit unique structural properties when they are minimal, i.e., when they do not contain redundant edges. Based on this structure, we prove that robust linear network codes exist for these networks over GF(2), and devise an efficient algorithm to construct them. Second, we consider the problem of securing a multicast network against an eavesdropper that can intercept the packets on a limited number of network links. We recast this problem as a network generalization of the classical wiretap channel of Type II introduced by Ozarow and Wyner in 1984. In particular, we demonstrate that perfect secrecy can be achieved by using the Ozarow-Wyner scheme of coset coding at the source, on top of the implemented network code. Consequently, we transparently recover important results available in the literature on secure network coding. We also derive new bounds on the required secure code alphabet size and an algorithm for code construction. In the last part of this dissertation, we study the connection between index coding, network coding, and matroid linear representation. We devise a reduction from the index coding problem to the network coding problem, implying that in the linear case these two problems are equivalent. We also present a second reduction from the matroid linear representability problem to index coding, and therefore, to network coding. The latter reduction establishes a strong connection between matroid theory and network coding theory. These two reductions are then used to construct special instances of the index coding problem where vector linear codes outperform scalar linear ones, and where non-linear encoding is needed to achieve the optimal number of transmission. Thereby, we provide a counterexample to a related conjecture in the literature and demonstrate the benefits of vector linear codes.