thesis_access.pdf (891.3 kB)
Download file

Chordality in Matroids: In Search of the Converse to Hliněný's Theorem

Download (891.3 kB)
thesis
posted on 23.11.2021, 10:46 by Probert, Andrew

Bodlaender et al. [7] proved a converse to Courcelle's Theorem for graphs [15] for the class of chordal graphs of bounded treewidth. Hliněný [25] generalised Courcelle's Theorem for graphs to classes of matroids represented over finite fields and of bounded branchwidth. This thesis has investigated the possibility of obtaining a generalisation of chordality to matroids that would enable us to prove a converse of Hliněný's Theorem [25].  There is a variety of equivalent characterisations for chordality in graphs. We have investigated the relationship between their generalisations to matroids. We prove that they are equivalent for binary matroids but typically inequivalent for more general classes of matroids.  Supersolvability is a well studied property of matroids and, indeed, a graphic matroid is supersolvable if and only if its underlying graph is chordal. This is among the stronger ways of generalising chordality to matroids. However, to obtain the structural results that we need we require a stronger property that we call supersolvably saturated.  Chordal graphs are well known to induce canonical tree decompositions. We show that supersolvably saturated matroids have the same property. These tree decompositions of supersolvably saturated matroids can be processed by a finite state automaton. However, they can not be completely described in monadic second-order logic.  In order to express the matroids and their tree decompositions in monadic second-order logic we need to extend the logic over an extension field for each matroid represented over a finite field. We then use the fact that each maximal round modular flat of the tree decomposition for every matroid represented over a finite field, and in the specified class, spans a point in the vector space over the extension field. This enables us to derive a partial converse to Hliněný's Theorem.

History

Copyright Date

01/01/2018

Date of Award

01/01/2018

Publisher

Te Herenga Waka—Victoria University of Wellington

Rights License

Author Retains Copyright

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

2 STRATEGIC 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

Whittle, Geoff; Downey, Rod