Monadic characterisation conjecture for frame matroids
Monadic characterisation conjecture for frame matroids
A matroid is a finite set system with an independence structure, and a frame matroid is a matroid arising from a biased graph; the monadic second-order language of matroids is the language that permits quantification over elements and sets of elements, together with the matroid relations. Frame-matroid monadic characterisation conjecture. There is a sentence in the monadic second-order language of matroids which characterises the class of frame matroids. Frame matroids are minor-closed, but have infinitely many excluded minors, so this conjecture would require structural methods beyond an excluded-minor list.
Sources & referencesView supporting material
Primary source
Daryl Funk, Dillon Mayhew and Mike Newman, “Defining bicircular matroids in monadic logic”, arXiv:2005.04526 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.