We study the natural action of Sn on the set of k-subsets of the set {1,…,n} when 1≤k≤n2. For this action we calculate the maximum size of a minimal base, the height and the maximum length of an ...irredundant base.
Here a base is a set with trivial pointwise stabilizer, the height is the maximum size of a subset with the property that its pointwise stabilizer is not equal to the pointwise stabilizer of any proper subset, and an irredundant base can be thought of as a chain of (pointwise) set-stabilizers for which all containments are proper.
Let G be a permutation group on a set
$\Omega $
of size t. We say that
$\Lambda \subseteq \Omega $
is an independent set if its pointwise stabilizer is not equal to the pointwise stabilizer of any ...proper subset of
$\Lambda $
. We define the height of G to be the maximum size of an independent set, and we denote this quantity
$\textrm{H}(G)$
. In this paper, we study
$\textrm{H}(G)$
for the case when G is primitive. Our main result asserts that either
$\textrm{H}(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
$\textrm{I}(G)$
, the maximum length of an irredundant base of G, in which case we prove that if G is primitive, then either
$\textrm{I}(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).
Group synchronization asks to recover group elements from their pairwise measurements. It has found numerous applications across various scientific disciplines. In this work, we focus on orthogonal ...and permutation group synchronization which are widely used in computer vision such as object matching and structure from motion. Among many available approaches, the spectral methods have enjoyed great popularity due to their efficiency and convenience. We will study the performance guarantees of the spectral methods in solving these two synchronization problems by investigating how well the computed eigenvectors approximate each group element individually. We establish our theory by applying the recent popular leave-one-out technique and derive a block-wise performance bound for the recovery of each group element via eigenvectors. In particular, for orthogonal group synchronization, we obtain a near-optimal performance bound for the group recovery in presence of additive Gaussian noise. For permutation group synchronization under random corruption, we show that the widely-used two-step procedure (spectral method plus rounding) can recover all the group elements exactly if the SNR (signal-to-noise ratio) is close to the information theoretical limit. Our numerical experiments confirm our theory and indicate a sharp phase transition for the exact group recovery.
We study the base sizes of finite quasiprimitive permutation groups of twisted wreath type, which are precisely the finite permutation groups with a unique minimal normal subgroup that is also ...non-abelian, non-simple and regular. Every permutation group of twisted wreath type is permutation isomorphic to a twisted wreath product G=Tk:P acting on its base group Ω=Tk, where T is some non-abelian simple group and P is some group acting transitively on k={1,…,k} with k⩾2. We prove that if G is primitive on Ω and P is quasiprimitive on k, then G has base size 2. We also prove that the proportion of pairs of points that are bases for G tends to 1 as |G|→∞ when G is primitive on Ω and P is primitive on k. Lastly, we determine the base size of any quasiprimitive group of twisted wreath type up to four possible values (and three in the primitive case). In particular, we demonstrate that there are many families of primitive groups of twisted wreath type with arbitrarily large base sizes.
We introduce and discuss an elementary tool from representation theory of finite groups for constructing linear codes invariant under a given permutation group G. The tool gives theoretical insight ...as well as a recipe for computations of generator matrices and weight distributions. In some interesting cases a classification of code vectors under the action of G can be obtained. As an explicit example a class of binary codes is studied extensively which is closely related to the class of binary codes associated to triangular graphs. A second explicit application is related to the action of the Mathieu simple group M24 on the set of octads giving many binary codes of length 759 with interesting properties. We also obtain new alternative proofs for several other theorems and construct several new codes invariant under various subgroups of the Conway simple group Co1.
Pre-primitive permutation groups Anagnostopoulou-Merkouri, Marina; Cameron, Peter J.; Suleiman, Enoch
Journal of algebra,
12/2023, Letnik:
636
Journal Article
Recenzirano
Odprti dostop
A transitive permutation group G on a finite set Ω is said to be pre-primitive if every G-invariant partition of Ω is the orbit partition of a subgroup of G. It follows that pre-primitivity and ...quasiprimitivity are logically independent (there are groups satisfying one but not the other) and their conjunction is equivalent to primitivity. Indeed, part of the motivation for studying pre-primitivity is to investigate the gap between primitivity and quasiprimitivity. We investigate the pre-primitivity of various classes of transitive groups including groups with regular normal subgroups, direct and wreath products, and diagonal groups. In the course of this investigation, we describe all G-invariant partitions for various classes of permutation groups G. We also look briefly at conditions similarly related to other pairs of conditions, including transitivity and quasiprimitivity, k-homogeneity and k-transitivity, and primitivity and synchronization.
Building on earlier papers of several authors, we establish that there exists a universal constant c>0 such that the minimal base size b(G) of a primitive permutation group G of degree n satisfies ...log|G|/logn≤b(G)<45(log|G|/logn)+c. This finishes the proof of Pyber's base size conjecture. The main part of our paper is to prove this statement for affine permutation groups G=V⋊H where H≤GL(V) is an imprimitive linear group. An ingredient of the proof is that for the distinguishing number d(G) (in the sense of Albertson and Collins) of a transitive permutation group G of degree n>1 we have the estimates |G|n<d(G)≤48|G|n.
A transitive permutation group with no fixed point free elements of prime order is called elusive. A permutation group on a set Ω is said to be 2-closed if G is the largest subgroup of
which leaves ...invariant each of the G-orbits for the induced action on
There is a conjecture due to Marušič, Jordan, and Klin asserting that there is no elusive 2-closed permutation group. In this article, we give a proof of the conjecture for permutation groups of degrees
and
where p, q, and r are (not necessarily distinct) three primes.
PDF
