Discrete Mathematics and Combinatorics Commons^™

Circuits And Enumeration Problems For Matroids, Christine H. Cho

LSU Doctoral Dissertations

This dissertation is a collection of work concerning the structure and enumeration of circuits and other distinguished sets in a matroid. The Tutte polynomial, recognized as the universal deletion-contraction invariant in matroid and graph theory, is a natural starting point when considering enumeration problems for matroids. The main result in Chapter 2 generalizes a theorem of Dean Lucas concerning the Tutte polynomial and its behavior under rank-preserving weak maps. This generalization provides an avenue for comparing the numbers of circuits, bases, rank-k flats, and hyperplanes of a matroid containing an element given two distinct, yet related, elements.

Chapter 3 addresses …

Combinatorial Models For Nonnegativity In Flag Varieties, Williem L. Rizer

Theses and Dissertations--Mathematics

The nonnegative Grassmannian admits a widely studied cell decomposition due to Alexander Postnikov, whose cells are indexed by positroids and modeled by several equivalent combinatorial objects. Subsequent work by authors including Lauren Williams, Suho Oh, and Carolina Benedetti has further developed the combinatorics and geometry of these structures. In this dissertation, we extend some of Postnikov’s combinatorial framework to the nonnegative flag variety. While cell decompositions in this setting were previously obtained, notably in work of Konstanze Rietsch, our focus is on providing new combinatorial models that make this structure more explicit and computationally tractable. We introduce flag positroid pipe …

Induced-Minor-Closed Classes Of Matroids, James Dylan Douthitt

LSU Doctoral Dissertations

A graph is chordal if every cycle of length at least four has a chord. In 1961, Dirac characterized chordal graphs as those graphs that can be built from complete graphs by repeated clique-sums. Generalizing this, we consider the class of simple GF(q)-representable matroids that can be built from projective geometries over GF(q) by repeated generalized parallel connections across projective geometries. We show that this class of matroids is closed under induced minors and characterize the class by its forbidden induced minors, noting that the case when q=2 is distinctive. Additionally, we show that the class of GF(2)-chordal matroids coincides …

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 …

Exponents Of Jacobians Of Graphs And Regular Matroids, Hahn Lheem, Deyuan Li, Carl Joshua Quines, Jessica Zhang

Rose-Hulman Undergraduate Mathematics Journal

Let G be a finite undirected multigraph with no self-loops. The Jacobian Jac (G) is a finite abelian group associated with G whose cardinality is equal to the number of spanning trees of G. There are only a finite number of biconnected graphs G such that the exponent of Jac (G) equals 2 or 3. The definition of a Jacobian can also be extended to regular matroids as a generalization of graphs. We prove that there are finitely many connected regular matroids M such that Jac (M) has exponent 2 and characterize all such matroids.

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 …

Pebble Game Algorithms And Sparse Graphs, Audrey Lee, Ileana Streinu

Computer Science: Faculty Publications

A multi-graph G on n vertices is (k,ℓ)-sparse if every subset of n^′⩽n vertices spans at most kn^′-ℓ edges. G is tight if, in addition, it has exactly kn-ℓ edges. For integer valuesk and ℓ∈[0,2k), we characterize the (k,ℓ)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k,ℓ)-pebble games. [A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (8) (2008) 1425–1437] from graphs to hypergraphs.