Name
Abstract | ||
|---|---|---|
Hliněný’s Theorem shows that any sentence in the monadic second-order logic of matroids can be tested in polynomial time, when the input is limited to a class of
$${\mathbb {F}}$$
-representable matroids with bounded branch-width (where
$${\mathbb {F}}$$
is a finite field). If each matroid in a class can be decomposed by a subcubic tree in such a way that only a bounded amount of information flows across displayed separations, then the class has bounded decomposition-width. We introduce the pigeonhole property for classes of matroids: if every subclass with bounded branch-width also has bounded decomposition-width, then the class is pigeonhole. An efficiently pigeonhole class has a stronger property, involving an efficiently-computable equivalence relation on subsets of the ground set. We show that Hliněný’s Theorem extends to any efficiently pigeonhole class. In a sequel paper, we use these ideas to extend Hliněný’s Theorem to the classes of fundamental transversal matroids, lattice path matroids, bicircular matroids, and
$$H$$
-gain-graphic matroids, where H is any finite group. We also give a characterisation of the families of hypergraphs that can be described via tree automata: a family is defined by a tree automaton if and only if it has bounded decomposition-width. Furthermore, we show that if a class of matroids has the pigeonhole property, and can be defined in monadic second-order logic, then any subclass with bounded branch-width has a decidable monadic second-order theory.
|
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s00453-022-00939-7 | Algorithmica |
Keywords | DocType | Volume |
Matroid theory, Tree automata, Monadic second-order logic | Journal | 84 |
Issue | ISSN | Citations |
7 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Funk Daryl | 1 | 0 | 0.34 |
| Dillon Mayhew | 2 | 102 | 18.63 |
| Newman Mike | 3 | 0 | 0.34 |