Subdegree growth rates of infinite primitive permutation groups

Thesis



If G is a group acting on a set Ω, and α, β ∈ Ω, the directed graph whose vertex set is Ω and whose edge set is the orbit (α, β)^G is called an orbital graph of G. These graphs have many uses in permutation group theory. A graph Γ is said to be primitive if its automorphism group acts primitively on its vertex set, and is said to have connectivity one if there is a vertex α such that the graph Γ\{α} is not connected. A half-line in Γ is a one-way infinite path in Γ. The ends of a locally finite graph Γ are equivalence classes on the set of half-lines: two half-lines lie in the same end if there exist infinitely many disjoint paths between them.

A complete characterisation of the primitive undirected graphs with connectivity one is already known. We give a complete characterisation in the directed case. This enables us to show that if G is a primitive permutation group with a locally finite orbital graph with more than one end, then G has a connectivity-one orbital graph Γ, and that this graph is essentially unique. Through the application of this result we are able to determine both the structure of G, and its action on the end space of Γ.

If α ∈ Ω, the orbits of the stabiliser G_α are called the α-suborbits of G. The size of an α-suborbit is called a subdegree. If all subdegrees of an infinite primitive group G are finite, Adeleke and Neumann claim one may enumerate them in a non-decreasing sequence (m_r). They conjecture that the growth of the sequence (m_r) is extremal when G acts distance transitively on a locally finite graph; that is, for all natural numbers m the stabiliser in G of any vertex α permutes the vertices lying at distance m from α transitively. They also conjecture that for any primitive group G possessing a finite self-paired suborbit of size m there might exist a number c which perhaps depends upon G, perhaps only on m, such that m_r ≤ c(m-2)^r-1. We show their questions are poorly posed, as there exist primitive groups possessing at least two distinct subdegrees, each occurring infinitely often. The subdegrees of such groups cannot be enumerated as claimed. We give a revised definition of subdegree enumeration and growth, and show that under these new definitions their conjecture is true for groups exhibiting exponential subdegree growth above a prescribed bound.

Authors: Smith, S; Simon M. Smith

• Publication date: 2005
• DOI: 10.5287/ora-a4xnym2gy
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Subjects: Graph theory; Group theory