Myhill-Nerode for hypergraphs and an application to gain-graphic matroids
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915928563777536 |
|---|---|
| author | Funk, Daryl Matthews, Angus Mayhew, Dillon |
| author_facet | Funk, Daryl Matthews, Angus Mayhew, Dillon |
| contents | We present a Myhill-Nerode theorem for hypergraphs. The theorem involves an operation which takes two input structures and produces a hypergraph as output. Using this operation, we define a Myhill-Nerode-type equivalence relation and show that if a class of hypergraphs is definable in the counting monadic second-order logic of hypergraphs, then the equivalence relation has finite index. We apply this tool to classes of gain-graphic matroids, and show that if the group $Γ$ is not uniformly locally finite, then the class of $Γ$\dash gain-graphic matroids is not monadically definable. (A group is uniformly locally finite if, for every $k$, there is a maximum size amongst subgroups generated by at most $k$ elements.) 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 $Γ$\dash gain-graphic matroids is not monadically definable. This will be useful in future constructions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_00139 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Myhill-Nerode for hypergraphs and an application to gain-graphic matroids Funk, Daryl Matthews, Angus Mayhew, Dillon Combinatorics Logic 05B35, 03C13, 20F99 We present a Myhill-Nerode theorem for hypergraphs. The theorem involves an operation which takes two input structures and produces a hypergraph as output. Using this operation, we define a Myhill-Nerode-type equivalence relation and show that if a class of hypergraphs is definable in the counting monadic second-order logic of hypergraphs, then the equivalence relation has finite index. We apply this tool to classes of gain-graphic matroids, and show that if the group $Γ$ is not uniformly locally finite, then the class of $Γ$\dash gain-graphic matroids is not monadically definable. (A group is uniformly locally finite if, for every $k$, there is a maximum size amongst subgroups generated by at most $k$ elements.) 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 $Γ$\dash gain-graphic matroids is not monadically definable. This will be useful in future constructions. |
| title | Myhill-Nerode for hypergraphs and an application to gain-graphic matroids |
| topic | Combinatorics Logic 05B35, 03C13, 20F99 |
| url | https://arxiv.org/abs/2510.00139 |