Greedy bases and relational complexity of diagonal type groups
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916016186982400 |
|---|---|
| author | Huang, Hong Yi Roney-Dougal, Colva M. |
| author_facet | Huang, Hong Yi Roney-Dougal, Colva M. |
| contents | A base for a subgroup $G$ of $\mathrm{Sym}(Ω)$ is a sequence of elements of $Ω$ with trivial pointwise stabiliser. The size of the smallest base for $G$ is denoted $b(G)$. There is a natural greedy algorithm to compute a base for $G$, and it was conjectured by Cameron in 1999 that there exists an absolute constant $c$ such that if $G$ is primitive then any base returned by this algorithm has size at most $cb(G)$. In this paper we determine the size of every base returned by the greedy algorithm when $G$ is a primitive group of diagonal type, and hence prove Cameron's conjecture for these groups.
The relational complexity $\mathrm{RC}(G)$ of $G$ is a measure of the way in which the orbits of $G$ on $Ω^k$ for various $k$ determine the action of $G$ on $Ω$. Very few precise values of relational complexity are known, and in particular it is not known which primitive groups have relational complexity $3$. In this paper we prove that if $G$ is primitive of diagonal type then $\mathrm{RC}(G) \geqslant 4$, that this lower bound is attained by infinitely many such $G$, and that the relational complexity of the groups of diagonal type is unbounded. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_16032 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Greedy bases and relational complexity of diagonal type groups Huang, Hong Yi Roney-Dougal, Colva M. Group Theory A base for a subgroup $G$ of $\mathrm{Sym}(Ω)$ is a sequence of elements of $Ω$ with trivial pointwise stabiliser. The size of the smallest base for $G$ is denoted $b(G)$. There is a natural greedy algorithm to compute a base for $G$, and it was conjectured by Cameron in 1999 that there exists an absolute constant $c$ such that if $G$ is primitive then any base returned by this algorithm has size at most $cb(G)$. In this paper we determine the size of every base returned by the greedy algorithm when $G$ is a primitive group of diagonal type, and hence prove Cameron's conjecture for these groups. The relational complexity $\mathrm{RC}(G)$ of $G$ is a measure of the way in which the orbits of $G$ on $Ω^k$ for various $k$ determine the action of $G$ on $Ω$. Very few precise values of relational complexity are known, and in particular it is not known which primitive groups have relational complexity $3$. In this paper we prove that if $G$ is primitive of diagonal type then $\mathrm{RC}(G) \geqslant 4$, that this lower bound is attained by infinitely many such $G$, and that the relational complexity of the groups of diagonal type is unbounded. |
| title | Greedy bases and relational complexity of diagonal type groups |
| topic | Group Theory |
| url | https://arxiv.org/abs/2605.16032 |