Abstract

The aim of this talk is to propose a topic of study that connects infinite matroids with pushdown automata on words indexed by arbitrary linear orders. The motivation for this study is the key open conjecture concerning infinite matroids, the Intersection Conjecture of Nash-Williams, as well as a result from my paper “Infinite Matroidal Version of Hall’s Matching Theorem, J. London Math. Soc., (2) 71 (2005), 563578.” The main result of this paper can be described using pushdown automata as follows. Let P=(M,W) be a pair of matroids on the same groundset E. We assign to P a language L_P consisting of transfinite words (indexed by ordinals) on the alphabet A={-1,0,1}. The language L_P is obtained by taking all injective transfinite sequences of the elements of E and translating each such sequence f into a word of L_P. The translation involves replacing an element of f by -1, 0 or 1 depending on whether it is spanned by its predecessors in both, one or none of the matroids M and W.

Theorem There exists a pushdown automaton T on transfinite sequences in the alphabet A such that the language L_T consisting of words accepted by T has the following property: For every pair P of matroids satisfying property (), the language L_P is a subset of L_T if and only if the pair P has a packing (the ground set E can be partitioned into sets E_M and E_N that are spanning in M and N, respectively).

The property () is that M is either finitary or a countable union of finite co-rank matroids and W is finitary.