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, 246 pp. 372–411.

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

Abstract

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

Look up in Google Scholar

Download history

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

CORE (COnnecting REpositories)