Open Access Te Herenga Waka-Victoria University of Wellington
thesis_access.pdf (891.3 kB)

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

Download (891.3 kB)
Version 2 2023-09-22, 01:43
Version 1 2021-11-23, 10:46
posted on 2023-09-22, 01:43 authored 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.


Copyright Date


Date of Award



Te Herenga Waka—Victoria University of Wellington

Rights License

CC BY 4.0

Degree Discipline


Degree Grantor

Te Herenga Waka—Victoria University of Wellington

Degree Level


Degree Name

Doctor of Philosophy

ANZSRC Type Of Activity code


Victoria University of Wellington Item Type

Awarded Doctoral Thesis



Victoria University of Wellington School

School of Mathematics and Statistics


Whittle, Geoff; Downey, Rod