Digital Commons Network^™

Matroid Generalizations Of Some Graph Results, Cameron Crenshaw

LSU Doctoral Dissertations

The edges of a graph have natural cyclic orderings. We investigate the matroids for which a similar cyclic ordering of the circuits is possible. A full characterization of the non-binary matroids with this property is given. Evidence of the difficulty of this problem for binary matroids is presented, along with a partial result for binary orderable matroids.

For a graph G, the ratio of |E(G)| to the minimum degree of G has a natural lower bound. For a matroid M that is representable over a finite field, we generalize this to a lower bound on …

Applications Of Powerset Operators, Especially To Matroids, Nathan Uricchio

Dissertations - ALL

Let \(\mathcal{V}\) denote a vector space over an arbitrary field with an inner product. For any collection \(\mathcal{S}\) of vectors from \(\mathcal{V}\) the collection of all vectors orthogonal to each vector in \(\mathcal{S}\) is a subspace, denoted as \(\mathcal{S}^{\perp_v}\) and called the \textit{orthogonal complement} of \(\mathcal{S}\). One of the fundamental theorems of vector space theory states that, \((\mathcal{S}^{\perp_v})^{\perp_v}\) is the subspace \textit{spanned} by \(\mathcal{S}\). Thus the ``spanning'' operator on the subsets of a vector space is the square of the ``orthogonal complement'' operator.

In matroid theory, the orthogonal complement of a matroid \(M\) is also well-defined and similarly results in …

Matroids Determinable By Two Partial Representations, Aurora Calderon Dojaquez

Electronic Theses, Projects, and Dissertations

A matroid is a mathematical object that generalizes and connects notions of independence that arise in various branches of mathematics. Some matroids can be represented by a matrix whose entries are from some field; whereas, other matroids cannot be represented in this way. However, every matroid can be partially represented by a matrix over the field GF(2). In fact, for a given matroid, many different partial representations may exist, each providing a different collection of information about the matroid with which they are associated. Such a partial representation of a matroid usually does not uniquely determine the matroid on its …

On Selected Subclasses Of Matroids, Tara Elizabeth Fife

LSU Doctoral Dissertations

Matroids were introduced by Whitney to provide an abstract notion of independence.

In this work, after giving a brief survey of matroid theory, we describe structural results for various classes of matroids. A connected matroid $M$ is unbreakable if, for each of its flats $F$, the matroid $M/F$ is connected%or, equivalently, if $M^*$ has no two skew circuits. . Pfeil showed that a simple graphic matroid $M(G)$ is unbreakable exactly when $G$ is either a cycle or a complete graph. We extend this result to describe which graphs are the underlying graphs of unbreakable frame matroids. A laminar family is …

Exploring Flag Matroids And Duality, Zachary Garcia

Electronic Theses, Projects, and Dissertations

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, …

Matroid - Based Variable Selection For Complex Data Structures, Wimarsha Thathsarani Jayanetti

Open Access Theses & Dissertations

This research project has the objective to extend use of the matroid algorithm using statistically based criteria, Joint/Multivariate Cumulants (Speed, 1983) and Effective Dependence (Pena & Rodriguez, 2003) to capture linear as well as non-linear higher order dependencies. We also improve variable selection for complex data structures using the proposed matroid algorithm. The limiting distribution of the joint cumulant was defined using U-statistics theory by Hoeffding (1948). U-statistics variance as theorized by Hoeffding provide a lower bound for the estimated variance, and our simulation results justify the use of Hoeffding U-statistic variance for determining a threshold for joint cumulants deviation …

Regular Round Matroids, Svetlana Borissova

Electronic Theses, Projects, and Dissertations

A matroid M is a finite set E, called the ground set of M, together with a notion of what it means for subsets of E to be independent. Some matroids, called regular matroids, have the property that all elements in their ground set can be represented by vectors over any field. A matroid is called round if its dual has no two disjoint minimal dependent sets. Roundness is an important property that was very useful in the recent proof of Rota's conjecture, which remained an unsolved problem for 40 years in matroid theory. In this thesis, we …

Extremal Problems In Matroid Connectivity, John Tyler Moss

LSU Doctoral Dissertations

Matroid k-connectivity is typically defined in terms of a connectivity function. We can also say that a matroid is 2-connected if and only if for each pair of elements, there is a circuit containing both elements. Equivalently, a matroid is 2-connected if and only if each pair of elements is in a certain 2-element minor that is 2-connected. Similar results for higher connectivity had not been known. We determine a characterization of 3-connectivity that is based on the containment of small subsets in 3-connected minors from a given list of 3-connected matroids. Bixby’s Lemma is a well-known inductive tool in …

Capturing Elements In Matroid Minors, Deborah Chun

LSU Doctoral Dissertations

In this dissertation, we begin with an introduction to a matroid as the natural generalization of independence arising in three different fields of mathematics. In the first chapter, we develop graph theory and matroid theory terminology necessary to the topic of this dissertation. In Chapter 2 and Chapter 3, we prove two main results. A result of Ding, Oporowski, Oxley, and Vertigan reveals that a large 3-connected matroid M has unavoidable structure. For every n exceeding two, there is an integer f(n) so that if |E(M)| exceeds f(n), then M has a minor isomorphic to the rank-n wheel or whirl, …

The Structure Of 4-Separations In 4-Connected Matroids, Jeremy M. Aikin

LSU Doctoral Dissertations

Oxley, Semple and Whittle described a tree decomposition for a 3-connected matroid M that displays, up to a natural equivalence, all non-trivial 3-separations of M. Crossing 3-separations gave rise to fundamental structures known as flowers. In this dissertation, we define generalized flower structure called a k-flower, with no assumptions on the connectivity of M. We completely classify k-flowers in terms of the local connectivity between pairs of petals. Specializing to the case of 4-connected matroids, we give a new notion of equivalence of 4-separations that we show will be needed to describe a tree decomposition for 4-connected matroids. Finally, we …

Unavoidable Minors In Graphs And Matroids, Carolyn Barlow Chun

LSU Doctoral Dissertations

It is well known that every sufficiently large connected graph G has either a vertex of high degree or a long path. If we require G to be more highly connected, then we ensure the presence of more highly structured minors. In particular, for all positive integers k, every 2-connected graph G has a series minor isomorphic to a k-edge cycle or K_{2,k}. In 1993, Oxley, Oporowski, and Thomas extended this result to 3- and internally 4-connected graphs identifying all unavoidable series minors of these classes. Loosely speaking, a series minor allows for arbitrary edge deletions but only allows edges …

The H-Vectors Of Matroids And The Arithmetic Degree Of Squarefree Strongly Stable Ideals, Erik Stokes

University of Kentucky Doctoral Dissertations

Making use of algebraic and combinatorial techniques, we study two topics: the arithmetic degree of squarefree strongly stable ideals and the h-vectors of matroid complexes.

For a squarefree monomial ideal, I, the arithmetic degree of I is the number of facets of the simplicial complex which has I as its Stanley-Reisner ideal. We consider the case when I is squarefree strongly stable, in which case we give an exact formula for the arithmetic degree in terms of the minimal generators of I as well as a lower bound resembling that from the Multiplicity Conjecture. Using this, we can …