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

Abstract

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.