On the height and relational complexity of a finite permutation group

Gill, Nick; Lodá, Bianca and Spiga, Pablo (2021). On the height and relational complexity of a finite permutation group. Nagoya Mathematical Journal (Early Access).

DOI: https://doi.org/10.1017/nmj.2021.6


Let $G$ be a permutation group on a set $\Omega$ of size $t$. We say that $\Lambda\subseteq\Omega$ is an \emph{independent set} if its pointwise stabilizer is not equal to the pointwise stabilizer of any proper subset of $\Lambda$. We define the \emph{height} of $G$ to be the maximum size of an independent set, and we denote this quantity $\Height(G)$.

In this paper we study $\Height(G)$ for the case when $G$ is primitive. Our main result asserts that either $\Height(G)< 9\log t$, or else $G$ is in a particular well-studied family (the ``primitive large--base groups''). An immediate corollary of this result is a characterization of primitive permutation groups with large ``relational complexity'', the latter quantity being a statistic introduced by Cherlin in his study of the model theory of permutation groups.

We also study $\Irred(G)$, the maximum length of an irredundant base of $G$, in which case we prove that if $G$ is primitive, then either $\Irred(G)<7\log t$ or else, again, $G$ is in a particular family (which includes the primitive large--base groups as well as some others).

Viewing alternatives

Download history


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions