Non-definability conjecture for infinite-group gain-graphic matroids
Non-definability conjecture for infinite-group gain-graphic matroids
Let be an infinite group. A gain-graphic matroid is a frame matroid obtained from a graph with edge gains in , and a class is characterised by a sentence in monadic second-order logic when membership is exactly described by such a sentence. Infinite-group gain-graphic non-definability conjecture. The class of -gain-graphic matroids cannot be characterised by a sentence in monadic second-order logic. Together with the finite-group excluded-minor conjecture, this would give a finite-versus-infinite dichotomy for logical definability of gain-graphic matroid classes; the source records the conjecture as unresolved only for infinite groups of finite exponent.
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.