Capturing elements in matroid minors

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, a rank-n spike, the cycle or bond matroid of K_{3,n}, or U_{2,n} or U_{n-2,n}. In Chapter 2, we build on this result to determine what can be said about a large structure using a specified element e of M. In particular, we prove that, for every integer n exceeding two, there is an integer g(n) so that if |E(M)| exceeds g(n), then e is an element of a minor of M isomorphic to the rank-n wheel or whirl, a rank-n spike, the cycle or bond matroid of K_{1,1,1,n}, a specific single-element extension of M(K_{3,n}) or the dual of this extension, or U_{2,n} or U_{n-2,n}. In Chapter 3, we consider a large 3-connected binary matroid with a specified pair of elements. We extend a corollary of the result of Chapter 2 to show the following result for any pair {x,y} of elements of a 3-connected binary matroid M. For every integer n exceeding two, there is an integer h(n) so that if |E(M)| exceeds h(n), then x and y are elements of a minor of M isomorphic to the rank-n wheel, a rank-n binary spike with a tip and a cotip, or the cycle or bond matroid of K_{1,1,1,n}.

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Applied Mathematics

Grantor

Mathematics

Year dc:date.available

2011

Author dc:creator

• Chun, Deborah

• matroid
• unavoidable minor
• ramsey
• rounded

Statement dc:rights

• unrestricted
• Release the entire work immediately for access worldwide.

Identifier

etd-06302011-063215
https://repository.lsu.edu/gradschool_dissertations/1033

OAI identifier oai:identifier

oai:repository.lsu.edu:gradschool_dissertations-2032