pith. sign in

arxiv: 2604.13887 · v1 · submitted 2026-04-15 · 🧮 math.CO · math.GR

Some remarks on the orbit dimension of transitive groups and on the metric dimension of Johnson graphs

Alice Drera , Pablo Spiga This is my paper

Pith reviewed 2026-05-10 12:58 UTC · model grok-4.3

classification 🧮 math.CO math.GR
keywords orbit dimensionpermutation grouptransitive groupJohnson graphmetric dimensionrankseparation number
0
0 comments X

The pith

Transitive permutation groups satisfy σ(G) ≤ |Ω| - r + 1, with equality only in groups of specific structure.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that any transitive permutation group G on a domain Ω has orbit dimension at most one more than the domain size minus the group's rank. It supplies detailed structural information on the groups that meet this bound with equality. The same invariant is then specialized to the symmetric group acting on k-subsets, where it turns out to equal the metric dimension of the associated Johnson graph. Readers may care because the bound gives a uniform estimate across all transitive actions and directly links a group-theoretic separation number to a well-studied graph parameter.

Core claim

If G is transitive on Ω with rank r, then the orbit dimension σ(G) is at most |Ω| - r + 1. Equality cases are constrained to groups whose point stabilizers produce a particular pattern of orbits. When G is the full symmetric group of degree n acting on the k-subsets of {1, …, n}, this same number σ(G) coincides exactly with the metric dimension of the Johnson graph J(n, k).

What carries the argument

The orbit dimension σ(G): the smallest subset S of Ω such that the stabilizers G_α (α in S) place every pair of distinct points into distinct orbits.

If this is right

  • Groups attaining equality must have point stabilizers whose orbits satisfy a rigid combinatorial condition.
  • The inequality supplies an immediate, computable upper bound for σ(G) once the rank is known.
  • Metric dimension of any Johnson graph J(n, k) equals the orbit dimension of the natural symmetric-group action on k-subsets.
  • Structural classification of equality cases restricts possible transitive actions to a short list of known types.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same separation idea might yield bounds for groups that are transitive on most but not all points.
  • Algorithms that compute rank could be reused to estimate metric dimension for Johnson graphs without building the full distance matrix.
  • The bound may connect to coding-theory notions of separating systems or identifying codes.

Load-bearing premise

The bound depends on the usual definition of rank as the number of orbits of a point stabilizer together with the assumption that G acts transitively on Ω.

What would settle it

A single transitive permutation group whose minimal separating set S has cardinality strictly larger than |Ω| - r + 1.

Figures

Figures reproduced from arXiv: 2604.13887 by Alice Drera, Pablo Spiga.

Figure 1
Figure 1. Figure 1: The auxiliary graph Γ for the separating set in Example 3.6. Observe that Γ is a simple graph, that is, it has no multiple edges. Indeed, there are no two distinct elements i, j ∈ [m] with (MS)i = (MS)j , since otherwise Lemma 3.5 would contradict the fact that S is separating. Therefore d2 equals the number of edges of Γ, that is, d2 = e(A, A) + e(A, B) + e(B, B). We claim that (5) each vertex of Γ has va… view at source ↗
Figure 2
Figure 2. Figure 2: Auxiliary figure for the proof of (14) (MS)x0 + (MS)x2 + (MS)x4 = (MS)x1 + (MS)x3 + (MS)x5 , which contradicts Lemma 3.5. Now, (14) implies that the subgraph of Γ induced on B1 is a disjoint union of edges and isolated vertices. In particular, (15) e(B1, B1) ≤ |B1| 2 . 12 [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The hypergraph when q = 3 We now describe the hyperedges of H. • H has 6q hyperedges of cardinality 1, corresponding to the elements of D1. In the figures, these are represented by the solid green vertices. In particular, this set coincides with the set A introduced in Section 3.2, while the black vertices correspond to the set B. • H has 3q hyperedges of cardinality 2, represented by solid blue edges. The… view at source ↗
Figure 5
Figure 5. Figure 5: The hypergraph when q ≡ 1 (mod 3) · · · [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The hypergraph when q ≡ 0 (mod 3) · · · [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The hypergraph when q ≡ 2 (mod 3) [7] P. Erd˝os, H. Sachs, Regul¨are Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin￾Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 12 (1963), 251–257. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_7.png] view at source ↗
read the original abstract

The orbit dimension $\sigma(G)$ (also called the separation number or rigidity index) of a permutation group $G$ with domain $\Omega$ is the minimum cardinality of a subset $S \subseteq \Omega$ such that, for any two distinct elements $\omega,\omega'\in \Omega$, there exists $\alpha\in S$ for which $\omega$ and $\omega'$ lie in distinct orbits of the stabilizer $G_\alpha$. In this paper, we first observe that if $G$ is transitive, then $\sigma(G)\le |\Omega|-r+1$, where $r$ is the rank of $G$, and we obtain strong structural information on the groups for which equality holds. Next, we investigate the orbit dimension in the case where $G$ is the symmetric group of degree $n$, acting on the set of $k$-subsets of $\{1,\ldots,n\}$. In this case, this invariant equals the metric dimension of Johnson graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper defines the orbit dimension σ(G) of a permutation group G on Ω as the smallest S ⊆ Ω such that stabilizers G_α (α ∈ S) place any two distinct points in different orbits. For transitive G it proves σ(G) ≤ |Ω| − r + 1 (r = rank of G) and characterizes the equality cases; it further shows that when G = Sym(n) acts on the k-subsets of {1,…,n}, σ(G) equals the metric dimension of the Johnson graph J(n,k).

Significance. The bound follows directly from the standard definition of rank (number of orbits of a point stabilizer) and a counting argument on orbit labels, supplying a parameter-free upper bound on separation number. The equality-case characterization and the exact identification with Johnson-graph metric dimension (via intersection sizes determining orbits) are useful for both permutation-group theory and metric graph theory.

minor comments (2)
  1. Abstract: the phrase 'strong structural information on the groups for which equality holds' is not expanded; a one-sentence indication of the characterization (e.g., non-S points form a single orbit under stabilizers of points in S) would make the abstract self-contained.
  2. §1 (or wherever the definition appears): a single concrete example of a small transitive group, its rank, and the computed σ(G) would help readers verify the bound before the general proof.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript, the accurate summary, and the positive evaluation of its significance. We appreciate the recommendation for minor revision and will prepare an updated version incorporating any necessary adjustments.

Circularity Check

0 steps flagged

No significant circularity; bound follows directly from definitions

full rationale

The paper derives the inequality σ(G) ≤ |Ω| − r + 1 for transitive G by a direct counting argument from the definitions of orbit dimension (minimum separating set via distinct G_α-orbits) and rank (number of orbits of a point stabilizer). Equality cases are characterized by the orbit structure of stabilizers without any fitted parameters or self-referential equations. The Johnson-graph identification follows immediately because graph distance equals k minus intersection size, which are precisely the orbit labels under the setwise stabilizer. No load-bearing self-citations appear, and the claims remain self-contained against standard group-theoretic definitions with no reduction to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard definitions of permutation-group rank and orbit dimension; no new entities or fitted constants are introduced.

axioms (1)
  • standard math The rank of a transitive permutation group G on Ω is the number of orbits of the stabilizer G_ω for any ω in Ω.
    Invoked in the statement of the bound; this is the classical definition from permutation group theory.

pith-pipeline@v0.9.0 · 5470 in / 1338 out tokens · 45545 ms · 2026-05-10T12:58:25.606548+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

  1. [1]

    R. F. Bailey; P. J. Cameron, Base size, metric dimension and other invariants of groups and graphsBull. Lond. Math. Soc.43(2011), 209–242

    work page 2011

  2. [2]

    R. F. Bailey, On the metric dimension of imprimitive distance-regular graphs,Ann. Comb.20(2016), 641–659

    work page 2016

  3. [3]

    R. F. Bailey, J. C´ aceres, D. Garijo, A. Gonz´ alez, A. M´ arquez, K. Meagher, M. L. Puertas, Resolving sets for Johnson and Kneser graphs,Electoric J. Combin.34(2013), 736–751

    work page 2013

  4. [4]

    P. J. Cameron,Permutation Groups, London Mathematical Society Student Texts, Cambridge University Press, 1999

    work page 1999

  5. [5]

    P. J. Cameron, D. G. Fon-Der-Flaass, Bases for permutation groups and matroids,Eur. J. Comb.16(1995), 537–544

    work page 1995

  6. [6]

    P. J. Cameron, Base size and separation number, basesep.pdf 16 · · · Figure 5.The hypergraph whenq≡1 (mod 3) · · · Figure 6.The hypergraph whenq≡0 (mod 3) · · · Figure 7.The hypergraph whenq≡2 (mod 3)

    work page

  7. [7]

    Erd˝ os, H

    P. Erd˝ os, H. Sachs, Regul¨ are Graphen gegebener Taillenweite mit minimaler Knotenzahl,Wiss. Z. Martin- Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe12(1963), 251–257. 17

    work page 1963

  8. [8]

    Fijavˇ z, B

    G. Fijavˇ z, B. Mohar, Rigidity and separation indices of Paley graphs,Discrete Math.289(2004), 1157–161

    work page 2004

  9. [9]

    Fijavˇ z, B

    G. Fijavˇ z, B. Mohar, Separation and rigidity index of graphs on surfaces,Graphs Combin.26(2010), 491–498

    work page 2010

  10. [10]

    Tullio Levi-Civita

    Z. Halasi, On the base size for the symmetric group acting on subsets.Studia Sci. Math. Hungar.49(2012), 492–500. Scuola Galileiana di Studi Superiori, Universit `a di Padova; Dipartimento di Matematica “Tullio Levi-Civita”, Universit`a di Padova, Via Trieste 63, 35121 Padova, Italy Email address:alice.drera@studenti.unipd.it Dipartimento di Matematica e ...

    work page 2012