Cyclic Group Spectra for Some Small Relation Algebras
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913279698272256 |
|---|---|
| author | Alm, Jeremy F. Bostic, Ashlee Chenault, Claire Coleman, Kenyon Culver, Chesney |
| author_facet | Alm, Jeremy F. Bostic, Ashlee Chenault, Claire Coleman, Kenyon Culver, Chesney |
| contents | The question of characterizing the (finite) representable relation algebras in a ``nice" way is open. The class $\mathbf{RRA}$ is known to be not finitely axiomatizable in first-order logic. Nevertheless, it is conjectured that ``almost all'' finite relation algebras are representable.
All finite relation algebras with three or fewer atoms are representable. So one may ask, Over what cardinalities of sets are they representable? This question was answered completely by Andréka and Maddux (``Representations for small relation algebras,'' \emph{Notre Dame J. Form. Log.}, \textbf{35} (1994)); they determine the spectrum of every finite relation algebra with three or fewer atoms.
In the present paper, we restrict attention to cyclic group representations, and completely determine the cyclic group spectrum for all seven symmetric integral relation algebras on three atoms. We find that in some instances, the spectrum and cyclic spectrum agree; in other instances, the spectra disagree for finitely many $n$; finally, for other instances, the spectra disagree for infinitely many $n$. The proofs employ constructions, SAT solvers, and the probabilistic method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_15939 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cyclic Group Spectra for Some Small Relation Algebras Alm, Jeremy F. Bostic, Ashlee Chenault, Claire Coleman, Kenyon Culver, Chesney Logic Discrete Mathematics Combinatorics 03G15, 05D40 The question of characterizing the (finite) representable relation algebras in a ``nice" way is open. The class $\mathbf{RRA}$ is known to be not finitely axiomatizable in first-order logic. Nevertheless, it is conjectured that ``almost all'' finite relation algebras are representable. All finite relation algebras with three or fewer atoms are representable. So one may ask, Over what cardinalities of sets are they representable? This question was answered completely by Andréka and Maddux (``Representations for small relation algebras,'' \emph{Notre Dame J. Form. Log.}, \textbf{35} (1994)); they determine the spectrum of every finite relation algebra with three or fewer atoms. In the present paper, we restrict attention to cyclic group representations, and completely determine the cyclic group spectrum for all seven symmetric integral relation algebras on three atoms. We find that in some instances, the spectrum and cyclic spectrum agree; in other instances, the spectra disagree for finitely many $n$; finally, for other instances, the spectra disagree for infinitely many $n$. The proofs employ constructions, SAT solvers, and the probabilistic method. |
| title | Cyclic Group Spectra for Some Small Relation Algebras |
| topic | Logic Discrete Mathematics Combinatorics 03G15, 05D40 |
| url | https://arxiv.org/abs/2403.15939 |