2025/09/30 by Funk, Daryl, Matthews, Angus, Mayhew, Dillon
#03C13 #05B35 #20F99 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.2510.00139
We present an analogue of a Myhill-Nerode characterisation which will allow us to prove that classes of hypergraphs cannot be defined by sentences in the counting monadic second-order logic of hypergraphs. We apply this to classes of gain-graphic matroids, and show that if the group Γ is not uniformly locally finite, then the class of Γ-gain-graphic matroids is not monadically definable. (A group is uniformly locally finite if and only if there is a maximum size amongst subgroups generated by at most k elements, for every k.) In addition, we define the conviviality graph of a group, and show that if the group Γ has an infinite conviviality graph, then the class of Γ-gain-graphic matroids is not monadically definable. This will be useful in future constructions.