Source author record

Pablo Spiga

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

68works
5topics
4close collaborators

Published work

68 publications

preprint2024arXiv

Kronecker classes, normal coverings and chief factors of groups

For a group GG, a subgroup U≤GU \leq G and a group Inn(G)≤A≤Aut(G)\mathrm{Inn}(G) \leq A \leq \mathrm{Aut}(G), we say that UU is an AA-covering group of GG if G=⋃a∈AUaG = \bigcup_{a\in A}U^a. A theorem of Jordan (1872) implies that if GG is a finite group, A=Inn(G)A = \mathrm{Inn}(G) and UU is an AA-covering group of GG, then U=GU = G. Motivated by a question concerning Kronecker classes of field extensions, Neumann and Praeger (1988) conjectured that, more generally, there is an integer function ff such that if GG is a finite group and UU is an AA-covering subgroup of GG, then ∣G:U∣≤f(∣A:Inn(G)∣)|G:U| \leq f(|A:\mathrm{Inn}(G)|). A key piece of evidence for this conjecture is a theorem of Praeger (1994), which asserts that there is a two-variable integer function gg such that if GG is a finite group and UU is an AA-covering subgroup of GG, then ∣G:U∣≤g(∣A:Inn(G)∣,c)|G:U|\leq g(|A:\mathrm{Inn}(G)|,c) where cc is the number of AA-chief factors of~GG. Unfortunately, the proof of this result contains an error. In this paper, using a different argument, we give a correct proof of this theorem.

preprint2023arXiv

Almost all Cayley maps are mapical regular representations

Cayley maps are combinatorial structures built upon Cayley graphs on a group. As such the original group embeds in their group of automorphisms, and one can ask in which situation the two coincide (one then calls the Cayley map a mapical regular representation or MRR) and with what probability. The first question was answered by Jajcay. In this paper we tackle the probabilistic version, and prove that as groups get larger the proportion of MRRs among all Cayley Maps approaches 1.

preprint2022arXiv

A generalization of Szep's conjecture for almost simple groups

We prove a natural generalization of Szep's conjecture. Given an almost simple group GG with socle not isomorphic to an orthogonal group having Witt defect zero, we classify all possible group elements x,y∈G∖{1}x,y\in G\setminus\{1\} with G=NG(⟨x⟩)NG(⟨y⟩)G={\bf N}_G (\langle x\rangle){\bf N}_G(\langle y\rangle), where we are denoting by NG(⟨x⟩){\bf N}_G(\langle x\rangle) and by NG(⟨y⟩){\bf N}_G(\langle y\rangle) the normalizers of the cyclic subgroups ⟨x⟩\langle x\rangle and ⟨y⟩\langle y\rangle. As a consequence of this result, we classify all possible group elements x,y∈G∖{1}x,y\in G\setminus\{1\} with G=CG(x)CG(y)G={\bf C}_G(x){\bf C}_G(y).

preprint2022arXiv

Normal 22-coverings of the finite simple groups and their generalizations

Given a finite group GG, we say that GG has weak normal covering number γw(G)γ_w(G) if γw(G)γ_w(G) is the smallest integer with GG admitting proper subgroups H1,…,Hγw(G)H_1,\ldots,H_{γ_w(G)} such that each element of GG has a conjugate in HiH_i, for some i∈{1,…,γw(G)}i\in \{1,\ldots,γ_w(G)\}, via an element in the automorphism group of GG. We prove that the weak normal covering number of every non-abelian simple group is at least 22 and we classify the non-abelian simple groups attaining 22. As an application, we classify the non-abelian simple groups having normal covering number 22. We also show that the weak normal covering number of an almost simple group is at least two up to one exception. We determine the weak normal covering number and the normal covering number of the almost simple groups having socle a sporadic simple group. Using similar methods we find the clique number of the invariably generating graph of the almost simple groups having socle a sporadic simple group.

preprint2022arXiv

The Engel graph of almost simple groups

Given a finite group GG, the Engel graph of GG is a directed graph encoding pairs of elements satisfying some Engel word. From the work of Detomi, Lucchini and Nemmi, the strongly connectivity of the Engel graph of an arbitrary group GG is reduced to the understanding of the strongly connectivity of the Engel graph of non-abelian simple groups. In this paper, we investigate the strongly connectivity of the Engel graph of finite non-abelian simple groups.

preprint2021arXiv

A generalization of Sims conjecture for finite primitive groups and two point stabilizers in primitive groups

In this paper we propose a refinement of Sims conjecture concerning the cardinality of the point stabilizers in finite primitive groups and we make some progress towards this refinement. In this process, when dealing with primitive groups of diagonal type, we construct a finite primitive group GG on ΩΩ and two distinct points α,β∈Ωα,β\in Ω with Gαβ⊴GαG_{αβ}\unlhd G_α and Gαβ≠1G_{αβ}\ne 1, where GαG_α is the stabilizer of αα in GG and GαβG_{αβ} is the stabilizer of αα and ββ in GG. In particular, this example gives an answer to a question raised independently by Peter Cameron and by Alexander Fomin.

preprint2021arXiv

Hypermaps over non-abelian simple groups and strongly symmetric generating sets

A generating pair x,yx, y for a group GG is said to be \textbf{\textit{symmetric}} if there exists an automorphism φx,yφ_{x,y} of GG inverting both xx and yy, that is, xφx,y=x−1x^{φ_{x,y}}=x^{-1} and yφx,y=y−1y^{φ_{x,y}}=y^{-1}. Similarly, a group GG is said to be \textbf{\textit{strongly symmetric}} if GG can be generated with two elements and if all generating pairs of GG are symmetric. In this paper we classify the finite strongly symmetric non-abelian simple groups. Combinatorially, these are the finite non-abelian simple groups GG such that every orientably regular hypermap with monodromy group GG is reflexible.

preprint2021arXiv

Independent sets of generators of prime power order

A subset XX of a finite group GG is said to be prime-power-independent if each element in XX has prime power order and there is no proper subset YY of XX with ⟨Y,Φ(G)⟩=⟨X,Φ(G)⟩\langle Y, Φ(G)\rangle = \langle X, Φ(G)\rangle, where Φ(G)Φ(G) is the Frattini subgroup of GG. A group GG is Bpp\mathcal{B}_{pp} if all prime-power-independent generating sets for GG have the same cardinality. We prove that, if GG is Bpp\mathcal{B}_{pp}, then GG is solvable. Pivoting on some recent results of Krempa and Stocka, this yields a complete classification of Bpp\mathcal{B}_{pp}-groups.

preprint2020arXiv

A conjecture on bipartite graphical regular representations

In this paper we are concerned with the classification of the finite groups admitting a bipartite DRR and a bipartite GRR. First, we find a natural obstruction in a finite group for not admitting a bipartite GRR. Then we give a complete classification of the finite groups satisfying this natural obstruction and hence not admitting a bipartite GRR. Based on these results and on some extensive computer computations, we state a conjecture aiming to give a complete classification of the finite groups admitting a bipartite GRR. Next, we prove the existence of bipartite DRRs for most of the finite groups not admitting a bipartite GRR found in this paper. Actually, we prove a much stronger result: we give an asymptotic enumeration of the bipartite DRRs over these groups. Again, based on these results and on some extensive computer computations, we state a conjecture aiming to give a complete classification of the finite groups admitting a bipartite DRR.

preprint2020arXiv

Generalised dihedral CI-groups

In this paper, we find a strong new restriction on the structure of CI-groups. We show that, if RR is a generalised dihedral group and if RR is a CI-group, then for every odd prime pp the Sylow pp-subgroup of RR has order pp, or 99. Consequently, any CI-group with quotient a generalised dihedral group has the same restriction, that for every odd prime pp the Sylow pp-subgroup of the group has order pp, or 99. We also give a counter example to the conjecture that every BCI-group is a CI-group.

preprint2020arXiv

On fixity of arc-transitive graphs

The relative fixity of a permutation group is the maximum proportion of the points fixed by a non-trivial element of the group and the relative fixity of a graph is the relative fixity of its automorphism group, viewed as a permutation group on the vertex-set of the graph. We prove in this paper that the relative fixity of connected 22-arc-transitive graphs of a fixed valence tends to 00 as the number of vertices grows to infinity. We prove the same result for the class of arc-transitive graphs of a fixed prime valence, and more generally, for any class of arc-transitive locally-LL graphs, where LL is a fixed quasiprimitive graph-restrictive permutation group.

preprint2020arXiv

On Haar digraphical representations of groups

In this paper we extend the notion of digraphical regular representations in the context of Haar digraphs. Given a group GG, a {\em Haar digraph} ΓΓ over GG is a bipartite digraph having a bipartition {X,Y}\{X,Y\} such that GG is a group of automorphisms of ΓΓ acting regularly on XX and on YY. We say that GG admits a {\em Haar digraphical representation} (HDR for short), if there exists a Haar digraph over GG such that its automorphism group is isomorphic to GG. In this paper, we classify finite groups admitting a HDR.

preprint2020arXiv

On minimal degree of transitive permutation groups with stabiliser being a 22-group

The minimal degree of a permutation group GG is defined as the minimal number of non-fixed points of a non-trivial element of GG. In this paper we show that if GG is a transitive permutation group of degree nn having no non-trivial normal 22-subgroups such that the stabiliser of a point is a 22-group, then the minimal degree of GG is at least 23n\frac{2}{3}n. The proof depends on the classification of finite simple groups.

preprint2020arXiv

On the asymptotic enumeration of Cayley graphs

In this paper we are interested in the asymptotic enumeration of Cayley graphs. It has previously been shown that almost every Cayley digraph has the smallest possible automorphism group: that is, it is a digraphical regular representation (DRR). In this paper, we approach the corresponding question for undirected Cayley graphs. The situation is complicated by the fact that there are two infinite families of groups that do not admit any graphical regular representation (GRR). The strategy for digraphs involved analysing separately the cases where the regular group RR has a nontrivial proper normal subgroup NN with the property that the automorphism group of the digraph fixes each NN-coset setwise, and the cases where it does not. In this paper, we deal with undirected graphs in the case where the regular group has such a nontrivial proper normal subgroup.

preprint2020arXiv

On the existence and the enumeration of bipartite regular representations of Cayley graphs over abelian groups

In this paper we are interested in the asymptotic enumeration of bipartite Cayley digraphs and Cayley graphs over abelian groups. Let AA be an abelian group and let ιι be the automorphism of AA defined by aι=a−1a^ι=a^{-1}, for every a∈Aa\in A. A Cayley graph $\Cay(A, S)$ is said to have an automorphism group as small as possible if $\Aut(\Cay(A,S)) = \langle A,ι\rangle$. In this paper, we show that, except for two infinite families, almost all bipartite Cayley graphs on abelian groups have automorphism group as small as possible. We also investigate the analogous question for bipartite Cayley digraphs.

preprint2020arXiv

On the number of fixed points of automorphisms of vertex-transitive graphs of bounded valency

The main result of this paper is that, if ΓΓ is a finite connected 44-valent arc-transitive graph, then either ΓΓ is part of a well-understood family of graphs, or every non-identity automorphism of ΓΓ fixes at most 1/31/3 of the vertices. As a corollary, we get a similar result for 33-valent vertex-transitive graphs. Based on these results we propose a conjecture on the number of fixed points of non-identity automorphisms of vertex-transitive graphs of bounded valency.

preprint2020arXiv

On triangles in derangement graphs

Given a permutation group GG, the derangement graph ΓGΓ_G of GG is the Cayley graph with connection set the set of all derangements of GG. We prove that, when GG is transitive of degree at least 33, ΓGΓ_G contains a triangle. The motivation for this work is the question of how large can be the ratio of the independence number of ΓGΓ_G to the size of the stabilizer of a point in GG. We give examples of transitive groups where this ratio is maximum.

preprint2016arXiv

Binary permutation groups: alternating and classical groups

We introduce a new approach to the study of finite binary permutation groups and, as an application of our method, we prove Cherlin's binary groups conjecture for groups with socle a finite alternating group, and for the C1\mathcal{C}_1-primitive actions of the finite classical groups. Our new approach involves the notion, defined with respect to a group action, of a `\emph{beautiful subset}'. We demonstrate how the presence of such subsets can be used to show that a given action is not binary. In particular, the study of such sets will lead to a resolution of many of the remaining open cases of Cherlin's binary groups conjecture.

preprint2015arXiv

An application of the Local C(G,T) Theorem to a conjecture of Weiss

Let ΓΓ be a connected GG-vertex-transitive graph, let vv be a vertex of ΓΓ and let GvΓ(v)G_v^{Γ(v)} be the permutation group induced by the action of the vertex-stabiliser GvG_v on the neighbourhood Γ(v)Γ(v). The graph ΓΓ is said to be GG-\emph{locally primitive} if GvΓ(v)G_v^{Γ(v)} is primitive. Richard Weiss conjectured in 19781978 that, there exists a function f:N→Nf:\mathbb{N}\to \mathbb{N} such that, if ΓΓ is a connected GG-vertex-transitive locally primitive graph of valency dd and vv is a vertex of ΓΓ with ∣Gv∣|G_v| finite, then ∣Gv∣≤f(d)|G_v|\leq f(d). As an application of the Local C(G,T)C(G,T) Theorem, we prove this conjecture when GvΓ(v)G_v^{Γ(v)} contains an abelian regular subgroup. In fact, we show that the point-wise stabiliser in GG of a ball of ΓΓ of radius 44 is the identity subgroup.

preprint2015arXiv

Cayley numbers with arbitrarily many distinct prime factors

A positive integer nn is a Cayley number if every vertex-transitive graph of order nn is a Cayley graph. In 1983, Dragan Marušič posed the problem of determining the Cayley numbers. In this paper we give an infinite set SS of primes such that every finite product of distinct elements from SS is a Cayley number. This answers a 1996 outstanding question of Brendan McKay and Cheryl Praeger, which they "believe to be the key unresolved question" on Cayley numbers. We also show that, for every finite product nn of distinct elements from SS, every transitive group of degree nn contains a semiregular element.

preprint2015arXiv

Finite edge-transitive oriented graphs of valency four: a global approach

We develop a new framework for analysing finite connected, oriented graphs of valency 4, which admit a vertex-transitive and edge-transitive group of automorphisms preserving the edge orientation. We identify a sub-family of "basic" graphs such that each graph of this type is a normal cover of at least one basic graph. The basic graphs either admit an edge-transitive group of automorphisms that is quasiprimitive or biquasiprimitive on vertices, or admit an (oriented or unoriented) cycle as a normal quotient. We anticipate that each of these additional properties will facilitate effective further analysis, and we demonstrate that this is so for the quasiprimitive basic graphs. Here we obtain strong restirictions on the group involved, and construct several infinite families of such graphs which, to our knowledge, are different from any recorded in the literature so far. Several open problems are posed in the paper.

preprint2015arXiv

On the order of Borel subgroups of group amalgams and an application to locally-transitive graphs

A permutation group is called semiprimitive if each of its normal subgroups is either transitive or semiregular. Given nontrivial finite transitive permutation groups L1L_1 and L2L_2 with L1L_1 not semiprimitive, we construct an infinite family of rank two amalgams of permutation type [L1,L2][L_1,L_2] and Borel subgroups of strictly increasing order. As an application, we show that there is no bound on the order of edge-stabilisers in locally [L1,L2][L_1,L_2] graphs. We also consider the corresponding question for amalgams of rank k≥3k\geq 3. We completely resolve this by showing that the order of the Borel subgroup is bounded by the permutation type [L1,...,Lk][L_1,...,L_k] only in the trivial case where each of L1,...,LkL_1,...,L_k is regular.

preprint2014arXiv

A comment on: "Further restrictions on the structure of finite DCI-groups"

A finite group R is a CI-group if, whenever S and T are subsets of R with the Cayley graphs Cay(R,S) and Cay(R,T) isomorphic, there exists an automorphism x of R with S^x=T. The classification of CI-groups is an open problem in the theory of Cayley graphs and is closely related to the isomorphism problem for graphs. This paper is a contribution towards this classification, as we show that every dihedral group of order 6p, with p>3 prime, is a CI-group.

preprint2014arXiv

Cayley graphs on abelian groups

Let AA be an abelian group and let ιι be the automorphism of AA defined by i:a↦a−1i:a\mapsto a^{-1}. A Cayley graph Γ=Cay(A,S)Γ=\mathrm{Cay}(A,S) is said to have an automorphism group \emph{as small as possible} if Aut(Γ)=A⋊⟨i⟩\mathrm{Aut}(Γ)= A\rtimes\langle i\rangle. In this paper, we show that almost all Cayley graphs on abelian groups have automorphism group as small as possible, proving a conjecture of Babai and Godsil.

preprint2014arXiv

Finite primitive groups and regular orbits of group elements

We prove that if GG is a finite primitive permutation group and if gg is an element of GG, then either gg has a cycle of length equal to its order, or for some rr, mm and kk, the group G≤Sym(m)wrSym(r)G \leq \mathrm{Sym}(m) \textrm{wr} \mathrm{Sym}(r) preserves the product structure of rr direct copies of the natural action of Sym(m)\mathrm{Sym}(m) on kk-sets. This gives an answer to a question of Siemons and Zalesski and a solution to a conjecture of Giudici, Praeger and the second author.

preprint2014arXiv

Rationality conditions for the eigenvalues of normal finite Cayley graphs

Given a finite group G, we say that a subset C of G is power-closed if, for every x in C and y in <x> with <x>=<y>, we have that y lies in C. In this paper we are interested in finite Cayley digraphs Cay(G,C) over G with connection set C, where C is a union of conjugacy classes of G. We show that each eigenvalue of Cay(G,C) is integral if and only if C is power-closed. This result will follow from a discussion of some more general rationality conditions on the eigenvalues of Cay(G,C).

preprint2014arXiv

Twisted Permutation Codes

We introduce twisted permutation codes, which are frequency permutation arrays analogous to repetition permutation codes, namely, codes obtained from the repetition construction applied to a permutation code. In particular, we show that a lower bound for the minimum distance of a twisted permutation code is the minimum distance of a repetition permutation code. We give examples where this bound is tight, but more importantly, we give examples of twisted permutation codes with minimum distance strictly greater than this lower bound.

preprint2013arXiv

A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two

A complete list of all connected arc-transitive asymmetric digraphs of in-valence and out-valence 2 on up to 1000 vertices is presented. As a byproduct, a complete list of all connected 4-valent graphs admitting a half-arc-transitive group of automorphisms on up to 1000 vertices is obtained. Several graph-theoretical properties of the elements of our census are calculated and discussed.

preprint2013arXiv

A uniform upper bound for the character degree sums and Gelfand-Graev-like characters for finite simple groups

Let G be a finite non-abelian simple group and let p be a prime. We classify all pairs (G,p) such that the sum of the complex irreducible character degrees of G is greater than the index of a Sylow p-subgroup of G. Our classification includes all groups of Lie type in defining characteristic p (because every Gelfand-Graev character of G is multiplicity free and has degree equal to the above index), and a handful of well-described examples.

preprint2013arXiv

Affine transformations of finite vector spaces with large orders or few cycles

Let V be a d-dimensional vector space over a field of prime order p. We classify the affine transformations of V of order at least p^d/4, and apply this classification to determine the finite primitive permutation groups of affine type, and of degree n, that contain a permutation of order at least n/4. Using this result we obtain a classification of finite primitive permutation groups of affine type containing a permutation with at most four cycles.

preprint2013arXiv

Automorphisms of Cayley graphs on generalised dicyclic groups

A graph is called a GRR if its automorphism group acts regularly on its vertex-set. Such a graph is necessarily a Cayley graph. Godsil has shown that there are only two infinite families of finite groups that do not admit GRRs : abelian groups and generalised dicyclic groups. Indeed, any Cayley graph on such a group admits specific additional graph automorphisms that depend only on the group. Recently, Dobson and the last two authors showed that almost all Cayley graphs on abelian groups admit no automorphisms other than these obvious necessary ones. In this paper, we prove the analogous result for Cayley graphs on the remaining family of exceptional groups: generalised dicyclic groups.

preprint2013arXiv

Conjectures on the normal covering number of the finite symmetric and alternating groups

Let γ(Sn)γ(S_n) be the minimum number of proper subgroups HiH_i of the symmetric group SnS_n such that each element in SnS_n lies in some conjugate of one of the Hi.H_i. In this paper we conjecture that γ(Sn)=n2(1−1p1)(1−1p2)+2,γ(S_n)=\frac{n}{2}\left(1-\frac{1}{p_1}\right) \left(1-\frac{1}{p_2}\right)+2, where p1,p2p_1,p_2 are the two smallest primes in the factorization of nn and nn is neither a prime power nor a product of two primes. Support for the conjecture is given by a previous result for n=p1α1p2α2,n=p_1^{α_1}p_2^{α_2}, with (α1,α2)≠(1,1)(α_1,α_2)\neq (1,1). We give further evidence by confirming the conjecture for integers of the form n=15qn=15q for an infinite set of primes qq, and by reporting on a Magma computation. We make a similar conjecture for γ(An)γ(A_n), when nn is even, and provide a similar amount of evidence.

preprint2013arXiv

Finite primitive permutation groups and regular cycles of their elements

We conjecture that if GG is a finite primitive group and if gg is an element of GG, then either the element gg has a cycle of length equal to its order, or for some r,mr,m and kk, the group G≤Sm≀SrG\leq S_m\wr S_r, preserving a product structure of rr direct copies of the natural action of SmS_m or AmA_m on kk-sets. In this paper we reduce this conjecture to the case that GG is an almost simple group with socle a classical group.

preprint2013arXiv

Groups having complete bipartite divisor graphs for their conjugacy class sizes

Given a finite group G, the bipartite divisor graph for its conjugacy class sizes is the bipartite graph with bipartition consisting of the set of conjugacy class sizes of G-Z (where Z denotes the centre of G) and the set of prime numbers that divide these conjugacy class sizes, and with {p,n} being an edge if gcd(p,n)\neq 1. In this paper we construct infinitely many groups whose bipartite divisor graph for their conjugacy class sizes is the complete bipartite graph K_{2,5}, giving a solution to a question of Taeri.

preprint2013arXiv

Normal coverings and pairwise generation of finite alternating and symmetric groups

The normal covering number γ(G)γ(G) of a finite, non-cyclic group GG is the least number of proper subgroups such that each element of GG lies in some conjugate of one of these subgroups. We prove that there is a positive constant cc such that, for GG a symmetric group $\Sym(n)$ or an alternating group $\Alt(n)$, γ(G)≥cnγ(G)\geq cn. This improves results of the first two authors who had earlier proved that aφ(n)≤γ(G)≤2n/3,aφ(n)\leqγ(G)\leq 2n/3, for some positive constant aa, where φφ is the Euler totient function. Bounds are also obtained for the maximum size κ(G)κ(G) of a set XX of conjugacy classes of $G=\Sym(n)$ or $\Alt(n)$ such that any pair of elements from distinct classes in XX generates GG, namely cn≤κ(G)≤2n/3cn\leq κ(G)\leq 2n/3.

preprint2013arXiv

On the maximum orders of elements of finite almost simple groups and primitive permutation groups

We determine upper bounds for the maximum order of an element of a finite almost simple group with socle T in terms of the minimum index m(T) of a maximal subgroup of T: for T not an alternating group we prove that, with finitely many exceptions, the maximum element order is at most m(T). Moreover, apart from an explicit list of groups, the bound can be reduced to m(T)/4. These results are applied to determine all primitive permutation groups on a set of size n that contain permutations of order greater than or equal to n/4.

preprint2013arXiv

On the order of vertex-stabilisers in vertex-transitive graphs with local group Cp×CpC_p\times C_p or Cp≀C2C_p \wr C_2

Let pp be a prime and let LL be either the intransitive permutation group Cp×CpC_p\times C_p of degree 2p2p or the transitive permutation group Cp≀C2C_p \wr C_2 of degree 2p2p. Let ΓΓ be a connected GG-vertex-transitive and GG-edge-transitive graph and let vv be a vertex of ΓΓ. We show that if the permutation group induced by the vertex-stabiliser GvG_v on the neighbourhood Γ(v)Γ(v) is isomorphic to LL then either ∣V(Γ)∣≥p∣Gv∣log⁡p(∣Gv∣/2)|V(Γ)|\geq p|G_v|\log_p\left(|G_v|/2\right), or ∣V(Γ)∣|V(Γ)| is bounded by a constant depending only on pp, or ΓΓ is a very-well understood graph. This generalises a few recent results.

preprint2012arXiv

Asymptotic enumeration of vertex-transitive graphs of fixed valency

Let GG be a group and let SS be an inverse-closed and identity-free generating set of GG. The \emph{Cayley graph} $\Cay(G,S)$ has vertex-set GG and two vertices uu and vv are adjacent if and only if uv−1∈Suv^{-1}\in S. Let CAYd(n)CAY_d(n) be the number of isomorphism classes of dd-valent Cayley graphs of order at most nn. We show that log⁡(CAYd(n))∈Θ(d(log⁡n)2)\log(CAY_d(n))\inΘ(d(\log n)^2), as n→∞n\to\infty. We also obtain some stronger results in the case d=3d=3.

preprint2012arXiv

CI-groups with respect to ternary relational structures: new examples

We find a sufficient condition to establish that certain abelian groups are not CI-groups with respect to ternary relational structures, and then show that the groups Z3×Z22\Z_3\times\Z_2^2, Z7×Z23\Z_7\times\Z_2^3, and Z5×Z24\Z_5\times\Z_2^4 satisfy this condition. Then we completely determine which groups Z23×Zp\Z_2^3\times\Z_p, pp a prime, are CI-groups with respect to binary and ternary relational structures. Finally, we show that Z25\Z_2^5 is not a CI-group with respect to ternary relational structures.

preprint2012arXiv

Cubic vertex-transitive graphs on up to 1280 vertices

A graph is called cubic and tetravalent if all of its vertices have valency 3 and 4, respectively. It is called vertex-transitive and arc-transitive if its automorphism group acts transitively on its vertex-set and on its arc- set, respectively. In this paper, we combine some new theoretical results with computer calculations to construct all cubic vertex-transitive graphs of order at most 1280. In the process, we also construct all tetravalent arc-transitive graphs of order at most 640.

preprint2012arXiv

On intransitive graph-restrictive permutation groups

Let ΓΓ be a finite connected GG-vertex-transitive graph and let vv be a vertex of ΓΓ. If the permutation group induced by the action of the vertex-stabiliser GvG_v on the neighbourhood Γ(v)Γ(v) is permutation isomorphic to LL, then (Γ,G)(Γ,G) is said to be locally-LL. A permutation group LL is graph-restrictive if there exists a constant c(L)c(L) such that, for every locally-LL pair (Γ,G)(Γ,G) and a vertex vv of ΓΓ, the inequality ∣Gv∣≤c(L)|G_v|\leq c(L) holds. We show that an intransitive group is graph-restrictive if and only if it is semiregular.

preprint2012arXiv

On the maximal number of coprime subdegrees in finite primitive permutation groups

The subdegrees of a transitive permutation group are the orbit lengths of a point stabilizer. For a finite primitive permutation group which is not cyclic of prime order, the largest subdegree shares a non-trivial common factor with each non-trivial subdegree. On the other hand it is possible for non-trivial subdegrees of primitive groups to be coprime, a famous example being the rank 5 action of the small Janko group on 266 points which has subdegrees of lengths 11 and 12. We prove that, for every finite primitive group, the maximal size of a set of pairwise coprime non-trivial subdegrees is at most 2.

preprint2011arXiv

Bounding the size of a vertex-stabiliser in a finite vertex-transitive graph

In this paper we discuss a method for bounding the size of the stabiliser of a vertex in a GG-vertex-transitive graph ΓΓ. In the main result the group GG is quasiprimitive or biquasiprimitive on the vertices of ΓΓ, and we obtain a genuine reduction to the case where GG is a nonabelian simple group. Using normal quotient techniques developed by the first author, the main theorem applies to general GG-vertex-transitive graphs which are GG-locally primitive (respectively, GG-locally quasiprimitive), that is, the stabiliser GαG_α of a vertex αα acts primitively (respectively quasiprimitively) on the set of vertices adjacent to αα. We discuss how our results may be used to investigate conjectures by Richard Weiss (in 1978) and the first author (in 1998) that the order of GαG_α is bounded above by some function depending only on the valency of ΓΓ, when ΓΓ is GG-locally primitive or GG-locally quasiprimitive, respectively.

preprint2011arXiv

Coprime subdegrees for primitive permutation groups and completely reducible linear groups

In this paper we answer a question of Gabriel Navarro about orbit sizes of a finite linear group H acting completely reducibly on a vector space V: if the orbits containing the vectors a and b have coprime lengths m and n, we prove that the orbit containing a+b has length mn. Such groups H are always reducible if n and m are greater than 1. In fact, if H is an irreducible linear group, we show that, for every pair of non-zero vectors, their orbit lengths have a non-trivial common factor. In the more general context of finite primitive permutation groups G, we show that coprime non-identity subdegrees are possible if and only if G is of O'Nan-Scott type AS, PA or TW. In a forthcoming paper we will show that, for a finite primitive permutation group, a set of pairwise coprime subdegrees has size at most 2. Finally, as an application of our results, we prove that a field has at most 2 finite extensions of pairwise coprime indices with the same normal closure.

preprint2011arXiv

On graph-restrictive permutation groups

Let ΓΓ be a connected GG-vertex-transitive graph, let vv be a vertex of ΓΓ and let L=GvΓ(v)L=G_v^{Γ(v)} be the permutation group induced by the action of the vertex-stabiliser GvG_v on the neighbourhood Γ(v)Γ(v). Then (Γ,G)(Γ,G) is said to be \emph{locally-LL}. A transitive permutation group LL is \emph{graph-restrictive} if there exists a constant c(L)c(L) such that, for every locally-LL pair (Γ,G)(Γ,G) and an arc (u,v)(u,v) of ΓΓ, the inequality ∣Guv∣≤c(L)|G_{uv}|\leq c(L) holds. Using this terminology, the Weiss Conjecture says that primitive groups are graph-restrictive. We propose a very strong generalisation of this conjecture: a group is graph-restrictive if and only if it is semiprimitive. (A transitive permutation group is said to be \emph{semiprimitive} if each of its normal subgroups is either transitive or semiregular.) Our main result is a proof of one of the two implications of this conjecture, namely that graph-restrictive groups are semiprimitive. We also collect the known results and prove some new ones regarding the other implication.

preprint2011arXiv

Two local conditions on the vertex stabiliser of arc-transitive graphs and their effect on the Sylow subgroups

In this paper we study GG-arc-transitive graphs ΔΔ where the permutation group GxΔ(x)G_x^{Δ(x)} induced by the stabiliser GxG_x of the vertex xx on the neighbourhood Δ(x)Δ(x) satisfies the two conditions given in the introduction. We show that for such a GG-arc-transitive graph ΔΔ, if (x,y)(x,y) is an arc of ΔΔ, then the subgroup Gx,y[1]G_{x,y}^{[1]} of GG fixing pointwise Δ(x)Δ(x) and Δ(y)Δ(y) is a pp-group for some prime pp. Next we prove that every GG-locally primitive (respectively quasiprimitive, semiprimitive) graph satisfies our two local hypotheses. Thus this provides a new Thompson-Wielandt-like theorem for a very large class of arc-transitive graphs. Furthermore, we give various families of GG-arc-transitive graphs where our two local conditions do not apply and where Gx,y[1]G_{x,y}^{[1]} has arbitrarily large composition factors.

preprint2010arXiv

An Erdos-Ko-Rado theorem for the derangement graph of PGL(2,q) acting on the projective line

Let G=PGL(2,q) be the projective general linear group acting on the projective line P_q. A subset S of G is intersecting if for any pair of permutations π,σin S, there is a projective point p in P_q such that p^π=p^σ. We prove that if S is intersecting, then the size of S is no more than q(q-1). Also, we prove that the only sets S that meet this bound are the cosets of the stabilizer of a point of P_q.

preprint2010arXiv

Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs

The main result of this paper is that, if ΓΓ is a connected 4-valent GG-arc-transitive graph and vv is a vertex of ΓΓ, then either ΓΓ is one of a well understood infinite family of graphs, or ∣Gv∣≤2436|G_v|\leq 2^43^6 or $2|G_v|\log_2(|G_v|/2)\leq |\VΓ|$ and that this last bound is tight. As a corollary, we get a similar result for 33-valent vertex-transitive graphs.

preprint2010arXiv

Failure on n-uniqueness: a family of examples

In this paper, the connections between model theory and the theory of infinite permutation groups are used to study the n-existence and the n-uniqueness for n-amalgamation problems of stable theories. We show that, for any n>1, there exists a stable theory having (k+1)-existence and k-uniqueness, for every k<n+1, but that does not have neither (n+2)-existence nor (n+1)-uniqueness. In particular, this generalizes the example, for n=2, due to E.Hrushovski given in [3].

preprint2010arXiv

Tetravalent arc-transitive graphs with unbounded vertex-stabilisers

It has long been known that there exist finite connected tetravalent arc-transitive graphs with arbitrarily large vertex-stabilisers. However, beside a well known family of exceptional graphs, related to the lexicographic product of a cycle with an edgeless graph on two vertices, only a few such infinite families of graphs are known. In this paper, we present two more families of tetravalent arc-transitive graphs with large vertex-stabilisers, each significant for its own reason.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.