Open Access Te Herenga Waka-Victoria University of Wellington
Browse
thesis_access.pdf (4.61 MB)

On matroids that are transversal and cotransversal

Download (4.61 MB)
Version 2 2023-09-26, 23:59
Version 1 2021-12-08, 20:23
thesis
posted on 2023-09-26, 23:59 authored by Meenu Mariya Jose

There are distinct differences between classes of matroids that are closed under principal extensions and those that are not Finite-field-representable matroids are not closed under principal extensions and they exhibit attractive properties like well-quasi-ordering and decidable theories (at least for subclasses with bounded branch-width). Infinite-field-representable matroids, on the other hand, are closed under principal extensions and exhibit none of these behaviours. For example, the class of rank-3 real representable matroids is not well-quasi-ordered and has an undecidable theory. The class of matroids that are transversal and cotransversal is not closed under principal extensions or coprincipal coextentions, so we expect it to behave more like the class of finite-field-representable matroids. This thesis is invested in exploring properties in the aforementioned class. A major idea that has inspired the thesis is the investigation of well-quasi-ordered classes in the world of matroids that are transversal and cotransversal. We conjecture that any minor-closed class with bounded branch-width containing matroids that are transversal and cotransversal is well-quasi-ordered. In Chapter 8 of the thesis, we prove this is true for lattice-path matroids, a well-behaved class that falls in this intersection. The general class of lattice-path matroids is not well-quasi-ordered as it contains an infinite antichain of so-called ‘notch matroids’. The interesting phenomenon that we observe is that this is essentially the only antichain in this class, that is, any minor-closed family of lattice-path matroids that contains only finitely many notch matroids is well-quasi-ordered. This answers a question posed by Jim Geelen.  Another question that drove the research was recognising fundamental transversal matroids, since these matroids are also cotransversal. We prove that this problem in general is in NP and conjecture that it is NP-complete. We later explore this question for the classes of lattice-path and bicircular matroids. We are successful in finding polynomial-time algorithms in both classes that identify fundamental transversal matroids. We end this part by investigating the intersection of bicircular and cobicircular matroids. We define a specific class - whirly-swirls - and conjecture that eventually any matroid in the above mentioned intersection belongs to this class.

History

Copyright Date

2020-01-01

Date of Award

2020-01-01

Publisher

Te Herenga Waka—Victoria University of Wellington

Rights License

CC BY-NC-ND 4.0

Degree Discipline

Mathematics

Degree Grantor

Te Herenga Waka—Victoria University of Wellington

Degree Level

Doctoral

Degree Name

Doctor of Philosophy

ANZSRC Type Of Activity code

1 PURE BASIC RESEARCH

Victoria University of Wellington Item Type

Awarded Doctoral Thesis

Language

en_NZ

Victoria University of Wellington School

School of Mathematics and Statistics

Advisors

Mayhew, Dillon