betaFeedback

WorksMathematics

Permutation codes via spectral graph theory

Abstract

We use the Eigenvalue Method to obtain upper spectral bounds on the size of permutation codes in the Hamming, Ulam, Cayley and Kendall metrics. For the Kendall metric, we improve the double-ball upper bound of Buzaglo and Etzion [IEEE Transactions on Information Theory, 2015] at minimum distance four and lengths seven and eight. For the Cayley metric, we improve the sphere packing bound, and determine when these spectral improvements occur. We derive theoretical spectral criteria for improvements from the ratio-type bounds of low degree, and show that the quadratic ratio-type bound for the Kendall metric always equals sphere packing. Furthermore, we prove sharp spectral bounds and recover known optimal code sizes for the Hamming and Ulam metrics.

Introduction

Permutation codes are subsets of the symmetric group SnS_n whose distinct elements are separated by a prescribed minimum distance. They model coding with ordered symbols and arise in rank-based representations, communication channels and data storage [13, 19, 20, 22, 30, 32]. Rank modulation for flash memories particularly motivates metrics based on adjacent transpositions and translocations [8, 24, 41]. The choice of metric determines the permitted errors and the combinatorial structure of the code problem.

We consider the Hamming, Ulam, Cayley and Kendall τ\tau metrics, denoted by dHd_H, dUd_U, dCd_C and dKd_K. For M∈{H,U,C,K}M \in\{H,U,C,K\}, let AM(n,d)A_M(n,d) be the largest cardinality of a subset of SnS_n with minimum dMd_M-distance at least dd. Our aim is to bound these quantities from above using spectral graph theory, and show that this new approach can bring improvements over previously known bounds, and also provide several cases for which the spectral bounds are attained.

Our main improvements over the best known upper bounds concern minimum Kendall distance four. In particular, we prove

AK(7,4)≤419,AK(8,4)≤2879A_K(7,4) \le419,\qquad A_K(8,4) \le2879

in Propositions 24 and 25, respectively. These improve the double-ball upper bounds 420 and 2880 of Buzaglo and Etzion [17 Corollary 6] (note that these existing bounds are also mentioned as the best known upper bounds in Table II of Parvaresh et al. [37]).

Our starting point is to formulate the minimum distance condition in coding theory in graph-theoretic terms. An independent set in a graph GG contains no adjacent pair of vertices, and the independence number α(G)\alpha(G) is the largest size of such a set. A kk-independent set in a graph GG has distinct vertices at pairwise shortest path distance greater than kk; its largest possible size is the kk-independence number αk(G)\alpha_k(G). The graph power GkG^k joins distinct vertices at distance at most kk, so αk(G)=α(Gk)\alpha_k(G)=\alpha(G^k). We will use the following two graph formulations:

  1. For each of the four metrics, the forbidden-distance graph (or equivalently, the (d−1)(d-1)-graph power), denoted ΓM(n,d)\Gamma_M(n,d), has vertex set SnS_n and joins distinct permutations at dMd_M-distance less than dd. A code is exactly an independent set in this graph, giving

AM(n,d)=α(ΓM(n,d)).(1)A_M(n,d)=\alpha(\Gamma_M(n,d)). \tag*{(1)}
  1. For M∈{U,C,K}M\in\{U,C,K\}, the base graph, denoted GM(n)G_M(n), joins permutations at dMd_M-distance one. Its shortest path distance is dMd_M, and hence, for d≥2d\ge2,

ΓM(n,d)=GM(n)d−1,AM(n,d)=α(GM(n)d−1)=αd−1(GM(n)).(2)\begin{aligned} \Gamma_M(n,d)&=G_M(n)^{d-1},\\ A_M(n,d)&=\alpha\left(G_M(n)^{d-1}\right)=\alpha_{d-1}\left(G_M(n)\right). \tag*{(2)} \end{aligned}

The identities (1) and (2) give the equivalent graph formulations underlying our strategy. They allow us to estimate the maximum code size using graph-theoretic techniques, in particular eigenvalue bounds, applied to the independence number of the forbidden-distance graph or, for M∈{U,C,K}M\in\{U,C,K\}, to the (d−1)(d-1)-independence number of the base graph. We use both formulations throughout the paper.

We should note that for Hamming distance, the corresponding construction uses the ambient Hamming graph Hn=H(n,n)\mathcal{H}_n=H(n,n) on all words in [n]n[n]^n, where [n]={1,…,n}[n]=\{1,\ldots,n\}:

ΓH(n,d)=(Hnd−1)[Sn].\Gamma_H(n,d)=\left(\mathcal{H}_n^{d-1}\right)[S_n].

Here the brackets denote the induced subgraph on permutation vertices; the power is formed before this restriction. Distinct permutations cannot differ in a single position, so the distance-one graph on SnS_n itself is edgeless (Remark 10). Forbidden-distance graphs are also called Gilbert graphs; see [29 Section III] for binary words and [42 Definition 2] for permutations.

With these formulations in place, we apply the Eigenvalue Method, which has been recently introduced by Abiad, Peters and Ravagnani [7]. The method combines polynomial spectral bounds for the graph kk-independence parameter, and their corresponding optimization methods. Its main tools are the inertia-type and ratio-type bounds, together with mixed-integer linear programming (MILP) and linear programming (LP), respectively. For a polynomial pp of degree at most kk, the matrix p(A)p(A) (where AA is the adjacency matrix of the graph GG) has zero off-diagonal entries between vertices at distance greater than kk, which allows us to bound αk(G)\alpha_k(G) using its eigenvalues. For the classical independence number, we will use degree one directly on a forbidden-distance graph. For higher independence we use degree at most d−1d-1 on a base graph. Other coding-theoretic applications of the spectral method have recently appeared in [2, 5, 6, 18].

In this paper we first show the graph properties needed to apply the method [7 Section 3]. The higher-independence formulation requires equality between metric distance and base-graph distance. We prove that the Ulam, Cayley and Kendall base graphs have the required properties, and that all four forbidden-distance graph families are vertex-transitive and hence walk-regular. The Hamming forbidden-distance graph is connected for d≥3d \ge3; its distance-two case is edgeless and gives the trivial exact value AH(n,2)=n!A_H(n,2)=n!. Thus the nontrivial applications below satisfy the required conditions. We should note that distance-regularity and an association scheme are not needed for the Eigenvalue Method to be used [7].

For M∈{U,C,K}M \in\{U,C,K\}, the equivalent formulations (1) and (2) encode the same code problem, but applying spectral bounds to the different graphs can give different estimates, since in general the spectral of a graph and its graph power are not related The adjacency matrix of a graph power is generally not a polynomial in the base adjacency matrix, see e.g. [4]. Our Ulam computations include examples favouring each approach (Table 4). Methods that exploit additional algebraic structure provide complementary comparisons: instances of it are coherent configurations used for Kendall distance [34], and the conjugacy-class linear programming used for Cayley distance [14, 39].

(n,d)(n,d)Base-graph bound (4), (5), (6)Power-graph ratio (4)Singleton (10)Known exact size
(3,2)(3,2)2222
(4,2)(4,2)6†6†66 [26]
(4,3)(4,3)2†222 [26]
(5,2)(5,2)30302424 [26]
(5,3)(5,3)71364 [26]
(5,4)(5,4)3222 [26]
(6,2)(6,2)168168120120 [26]
(6,3)(6,3)27742424 [26]
(6,4)(6,4)103764 [26]
(7,4)(7,4)44–2412 [26]

Table 4. Upper bounds on AU(n,d)A_U(n,d) from the ratio-type bound on GU(n)G_U(n), the ratio bound on ΓU(n,d)=GU(n)d−1\Gamma_U(n,d)=G_U(n)^{d-1}, and the Singleton bound (10). The exact values are from [26 Table I], except (3,2)(3,2), proved in Proposition 27. A dash indicates that the bound was not computed.

We next compare the resulting spectral upper bounds with the known bounds for each metric. For the Hamming distance case, we compare with linear programming, semidefinite programming and combinatorial bounds [10, 12, 14, 15, 35, 39]. For the Ulam distance, we use Singleton bounds and published exact computations [24, 26]. For the Kendall distance, the comparisons include sphere packing, double balls, coherent configurations and representation-theoretic bounds [1, 17, 34, 37, 40]. We also compute the full conjugacy-class linear program for the Cayley metric.

For the Cayley distance case, we derive explicit formulas for the quadratic ratio-type bound and the cubic ratio-type bound (Proposition 13) and determine all lengths at which the quadratic ratio-type bound improves distance-three sphere packing: n=6,8,10,12n=6, 8, 10, 12 (Corollary 15). The improvements are, respectively,

45⟶40,1390⟶1344,78886⟶75600,7149277⟶7044141.45 \longrightarrow40,\qquad1390 \longrightarrow1344,\qquad78886 \longrightarrow75600,\qquad7149277 \longrightarrow7044141.

For each metric, we also make theoretical comparisons with the best known upper bounds at small minimum distances, where closed formulas are available for the corresponding ratio-type bounds. These comparisons give criteria for improvement and identify the limitations of the Eigenvalue Method (§ 5).

We also show that the inertia-type and ratio-type bounds are sharp in several cases. For example, the quadratic inertia-type bounds give AC(4,3)=2A_C(4,3)=2 and AK(3,3)=2A_K(3,3)=2 (Propositions 18 and 21). In the Cayley example the optimal quadratic ratio-type bound is three, so the inertia-type bound is stronger (we note that not so many metric examples where found previously where the inertia-type bound would outperform the ratio-type bound, see [7]). An affine construction attains the Cayley quadratic ratio-type bound AC(5,3)=10A_C(5,3)=10 (Proposition 19). For the Hamming distance, the classical ratio bound recovers AH(n,3)=n!/2A_H(n,3)=n!/2, AH(5,4)=20A_H(5,4)=20 and AH(6,4)=120A_H(6,4)=120 (Proposition 12). For the Ulam distance, the ratio bound on the corresponding graph power gives AU(n,n−1)=2A_U(n,n-1)=2 for every n≥3n \ge3 (Proposition 27). The base-graph Ulam bounds are sharp after flooring at AU(4,2)=6A_U(4,2)=6 and AU(4,3)=2A_U(4,3)=2, as is the Kendall cubic bound at AK(4,4)=3A_K(4,4)=3.

This paper is organized as follows. Section 2 introduces the investigated permutation metrics and also the needed background on spectral graph theory. Section 3 states the coding bounds used for comparison. Section 4 investigates the needed graph properties and derives the specific spectral bounds. Section 5 then derives and compares the bounds for the four metrics, and Section 6 discusses the resulting strengths and limitations.

Preliminaries

Permutation codes under the most common metrics

Let n≥2n \ge2, write [n]={1,…,n}[n] = \{1,\ldots,n\}, and let SnS_n be the symmetric group on [n][n], with identity ee. We write permutations in one-line notation and use the composition convention (στ)(i)=σ(τ(i))(\sigma\tau)(i) = \sigma(\tau(i)). We first define the four metrics and then introduce the corresponding extremal code sizes. The one-line word for σ\sigma is (σ(1)⋯σ(n))(\sigma(1)\cdots\sigma(n)). With our convention, right multiplication by (i j)(i\,j) swaps the entries in positions ii and jj, whereas left multiplication relabels symbols.

The symmetric group SnS_n can be equipped with the following metrics:

Hamming metric

The Hamming distance is

dH(σ,τ)=∣{i∈[n]:σ(i)≠τ(i)}∣.d_H(\sigma,\tau) = \lvert\{i \in[n] : \sigma(i) \ne\tau(i)\}\rvert.

For example, dH(12345,13254)=4d_H(12345,13254) = 4. It measures position-wise disagreement. Its smallest nonzero value on SnS_n is two.

Ulam metric

Let L(σ,τ)L(\sigma,\tau) be the length of a longest common subsequence. The Ulam distance is

dU(σ,τ)=n−L(σ,τ)d_U(\sigma,\tau) = n - L(\sigma,\tau)

Equivalently, this is the minimum number of translocations, each removing one symbol and reinserting it at another position [24].

A common subsequence is obtained by deleting symbols from each word without changing the order of those retained; its symbols need not occupy consecutive positions.

For example, dU(12345,14235)=1d_U(12345,14235) = 1, since 1235 is a common subsequence and moving 4 produces the second word.

Kendall metric

The Kendall distance is the minimum number of swaps of adjacent positions needed to transform one permutation into the other, or equivalently

dK(σ,τ)=inv⁡(σ−1τ),inv⁡(π)=∣{(i,j):i<j, π(i)>π(j)}∣.d_K(\sigma,\tau) = \operatorname{inv}(\sigma^{-1}\tau), \qquad\operatorname{inv}(\pi) = \lvert\{(i,j) : i < j,\ \pi(i) > \pi(j)\}\rvert.

Thus dK(1234,2134)=1d_K(1234,2134) = 1 and dK(12345,54321)=10d_K(12345,54321) = 10. This metric models local ordering errors [17].

Cayley metric

The Cayley distance is the minimum number of swaps of arbitrary pairs of positions needed to transform one permutation into the other. If c(π)c(\pi) counts all cycles, including fixed points, then

dC(σ,τ)=n−c(σ−1τ).d_C(\sigma,\tau) = n - c(\sigma^{-1}\tau).

For example, dC(12345,21354)=2d_C(12345,21354) = 2, since the relative permutation is (1 2)(4 5)(1\,2)(4\,5). The cycle formula follows by splitting each cycle into transpositions and observing that a transposition changes the number of cycles by one.

Codes and their graph representations

Remark 1. Under our composition convention, all four metrics are left-invariant:

dM(gσ,gτ)=dM(σ,τ)=dM(e,σ−1τ).d_M(g\sigma,g\tau)=d_M(\sigma,\tau)=d_M(e,\sigma^{-1}\tau).

The Hamming and Cayley distances are also right-invariant; this is not true in general for Ulam or Kendall distance. The elementary operations give

dU(σ,τ)≤dK(σ,τ),d_U(\sigma,\tau)\le d_K(\sigma,\tau),
dC(σ,τ)≤dK(σ,τ),d_C(\sigma,\tau)\le d_K(\sigma,\tau),
12dH(σ,τ)≤dC(σ,τ)≤dH(σ,τ)−1,for σ≠τ∈Sn.\frac{1}{2}d_H(\sigma,\tau)\le d_C(\sigma,\tau)\le d_H(\sigma,\tau)-1,\quad\text{for }\sigma\ne\tau\in S_n.

For the last pair of inequalities, a nontrivial cycle of length ℓ\ell contributes ℓ\ell to Hamming distance and ℓ−1\ell-1 to Cayley distance.

For M∈{H,U,K,C}M\in\{H,U,K,C\} and an integer d≥1d\ge1, a permutation code of minimum dMd_M-distance at least dd is a subset of SnS_n whose distinct elements are pairwise at dMd_M-distance at least dd. Let AM(n,d)A_M(n,d) denote its maximum possible size; explicitly,

AM(n,d):=max⁡{∣C∣:C⊆Sn, dM(σ,τ)≥d for distinct σ,τ∈C}.A_M(n,d):=\max\{|C|:C\subseteq S_n,\ d_M(\sigma,\tau)\ge d\text{ for distinct }\sigma,\tau\in C\}.

If d=2r+1d=2r+1, the closed metric balls of radius rr centred at distinct codewords are disjoint: a point in two such balls would put their centres at distance at most 2r2r, by the triangle inequality. This gives the sphere-packing bound (20) used below (note that only this implication is needed; we will not assume the converse for an arbitrary metric on SnS_n).

A finite simple undirected graph G=(V,E)G=(V,E) consists of a vertex set VV and a set of edges EE; in particular, there are no loops or multiple edges. Vertices joined by an edge are adjacent. An independent set contains no adjacent pair, and its maximum possible size is the independence number α(G)\alpha(G).

For the coding problem of interest, let ΓM(n,d)\Gamma_M(n,d) have vertex set SnS_n, with distinct σ\sigma and τ\tau adjacent exactly when dM(σ,τ)<dd_M(\sigma,\tau)<d. Thus each vertex represents a complete permutation, not an individual symbol, and an edge represents a pair forbidden by the minimum-distance requirement. It follows directly that

AM(n,d)=α(ΓM(n,d)).A_M(n,d)=\alpha\bigl(\Gamma_M(n,d)\bigr).

Equivalently, a code is a clique, that is, a set of pairwise adjacent vertices, in the complement of ΓM(n,d)\Gamma_M(n,d), where adjacency is reversed for distinct vertices. We use the independent-set formulation throughout.

A path is a sequence of distinct vertices with consecutive vertices adjacent; its length is the number of edges. The graph distance between two vertices u,v∈V(G)u,v\in V(G), denoted dG(u,v)d_G(u,v), is the length of a shortest path from uu to vv, with distance infinity when no such path exists. A graph is connected when all pairs have finite distance; its diameter is then the maximum of these distances.

For M∈{U,C,K}M\in\{U,C,K\}, let GM(n)G_M(n) join permutations at dMd_M-distance one. A sequence of elementary edits corresponds to a sequence of adjacent vertices, so the edit-distance definitions give

dGM(n)(σ,τ)=dM(σ,τ).d_{G_M(n)}(\sigma,\tau)=d_M(\sigma,\tau).

Consequently, a code of minimum distance dd has no path of length at most d−1d-1 between distinct codewords in GM(n)G_M(n). For example, 123, 213, 231, 321 form a shortest path of length three in GK(3)G_K(3), since inv⁡(321)=3\operatorname{inv}(321)=3. The pair {123,321}\{123,321\} therefore has minimum Kendall distance three. The same distance-one construction is not suitable for Hamming distance: it gives an edgeless graph, whose graph distances do not recover dHd_H. Section 4 develops these graph representations and their parameters.

The Eigenvalue Method

The Eigenvalue Method [7] combines polynomial spectral bounds for graph independence parameters with their corresponding optimization methods. We recall the inertia-type and ratio-type bounds below and describe the optimization of the polynomials appearing in these bounds. The inertia-type bound can be optimized by mixed-integer linear programming, while the ratio-type bound admits a linear programming formulation on partially walk-regular graphs. We refer to [16] for the spectral graph theory background.

Let G=(V,E)G=(V,E) be a finite simple undirected graph of order N=∣V∣N=|V|. Its adjacency matrix AA has rows and columns indexed by VV, with Auv=1A_{uv}=1 when uu and vv are adjacent and Auv=0A_{uv}=0 otherwise. Thus, AA is a real symmetric matrix with zero diagonal. The degree of a vertex is its number of neighbours. A graph is δ\delta-regular if every vertex has δ\delta neighbours, in which case A1=δ1A\mathbf{1}=\delta\mathbf{1}, where 1\mathbf{1} is the all-one vector.

An automorphism of GG is a permutation of its vertices that preserves adjacency. The graph is vertex-transitive if, for any two vertices, some automorphism maps one to the other.

For a group Γ\Gamma with identity element ee, and an inverse-closed set S⊆Γ∖{e}S\subseteq\Gamma\setminus\{e\}, meaning S−1=SS^{-1}=S, the Cayley graph Cay⁡(Γ,S)\operatorname{Cay}(\Gamma,S) joins gg and hh when g−1h∈Sg^{-1}h\in S. Its neighbours at gg are the elements gsgs with s∈Ss\in S. Left multiplication is an automorphism, so the graph is vertex-transitive and ∣S∣|S|-regular. It is connected precisely when SS generates Γ\Gamma.

Since AA is real symmetric, it has an orthonormal basis of eigenvectors and real eigenvalues

λ1≥λ2≥⋯≥λN,\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_N,

listed with multiplicity. The spectrum is this multiset of eigenvalues. We also use the distinct eigenvalues θ0>⋯>θr\theta_0>\cdots>\theta_r, with multiplicities m0,…,mrm_0,\ldots,m_r, so that ∑i=0rmi=N\sum_{i=0}^{r}m_i=N. In displayed spectra, θimi\theta_i^{m_i} indicates multiplicity, not exponentiation. For a connected δ\delta-regular graph, λ1=θ0=δ\lambda_1=\theta_0=\delta is simple, with eigenvector 1\mathbf{1}, and all eigenvalues lie in [−δ,δ][-\delta,\delta]. We call the remaining eigenvalues nonprincipal; their eigenvectors lie in the subspace orthogonal to 1\mathbf{1}.

A walk of length jj is a sequence of j+1j+1 vertices with consecutive vertices adjacent; unlike a path, it may repeat vertices. Matrix multiplication shows that (Aj)uv(A^j)_{uv} counts walks of length jj from uu to vv. In particular, (Aj)vv(A^j)_{vv} counts closed walks based at vv, (A2)vv(A^2)_{vv} is the degree of vv, and (A3)vv(A^3)_{vv} is twice the number of triangles containing vv. We take A0=IA^0=I. These observations explain the diagonal quantities in the inertia-type and ratio-type bounds below.

A graph is bipartite if its vertices can be partitioned into two independent sets. Every walk alternates between the two parts, so there are no closed walks of odd length. Its spectrum is symmetric about zero: changing the sign of an eigenvector on one part changes its eigenvalue from λ\lambda to −λ-\lambda. In particular, (A3)vv=0(A^3)_{vv}=0 for bipartite graphs, a simplification used in the cubic bounds below.

We say that a graph GG is kk-partially walk-regular when (Ai)vv(A^i)_{vv} is independent of vv for 0≤i≤k0\leq i\leq k. It is walk-regular if this holds for every ii. Vertex-transitivity implies walk-regularity. Indeed, an automorphism mapping uu to vv gives a bijection between closed walks of any given length based at these vertices. On a walk-regular graph, all diagonal entries of p(A)p(A) are the same constant, for every polynomial pp. Taking their sum and using the eigenvalues of p(A)p(A) gives,

(p(A))vv=1Ntr⁡p(A)=1N∑i=0rmip(θi),N=∣V∣.(3)(p(A))_{vv}=\frac{1}{N}\operatorname{tr}p(A)=\frac{1}{N}\sum_{i=0}^{r}m_i p(\theta_i),\qquad N=|V|. \tag*{(3)}

Definition 2. The kk-independence number of a graph GG, denoted αk(G)\alpha_k(G), is the largest cardinality of a vertex set whose distinct vertices are at graph distance greater than kk. The

graph power GkG^k joins distinct vertices at distance at most kk; hence αk(G)=α(Gk)\alpha_k(G)=\alpha(G^k) where α(G)\alpha(G) denotes the usual independence number of GG.

For the permutation base graphs GM(n)G_M(n), M∈{U,C,K}M \in\{U,C,K\}, a minimum-distance requirement d≥2d \ge2 corresponds to k=d−1k=d-1. For Hamming distance we instead apply ordinary independence bounds, with k=1k=1, directly to ΓH(n,d)\Gamma_H(n,d). The graph power GkG^k should not be confused with the matrix power AkA^k: the latter counts walks and is generally not a zero–one adjacency matrix.

The spectra of GG and GkG^k need not be related by an adjacency polynomial [4]. Applying a polynomial spectral bound to αk(G)\alpha_k(G) is therefore different from applying the ratio or inertia bound to α(Gk)\alpha(G^k). We compare the two approaches for Ulam distance in Table 4.

We now recall the polynomial spectral bounds used in the Eigenvalue Method, together with the corresponding optimization methods; see [7].

We reserve ratio bound for the degree-one case and use ratio-type bound for the polynomial extensions.

Write Rk[x]\mathbb{R}_k[x] for the real polynomials of degree at most kk, where k≥1k \ge1. For p(x)=∑j=0kajxjp(x)=\sum_{j=0}^{k}a_jx^j, define the matrix polynomial p(A)=∑j=0kajAjp(A)=\sum_{j=0}^{k}a_jA^j. It has eigenvalues p(λi)p(\lambda_i) with the same eigenvectors as AA, although their ordering can change. The walk-counting interpretation gives the key implication

dG(u,v)>k⟹(p(A))uv=0(u≠v).d_G(u,v)>k \quad\Longrightarrow\quad(p(A))_{uv}=0 \qquad(u\ne v).

Indeed, there is no walk of length at most kk between such vertices. If CC is kk-independent, the principal submatrix obtained by restricting both the rows and the columns of p(A)p(A) to CC is therefore diagonal. On a walk-regular graph it is a scalar multiple of the identity. This converts the minimum-distance condition into a matrix constraint to which eigenvalue bounds apply [3]. To allow for graphs without a common diagonal, put

W(p)=max⁡v(p(A))vv,w(p)=min⁡v(p(A))vv.W(p)=\max_v(p(A))_{vv},\qquad w(p)=\min_v(p(A))_{vv}.

Theorem 3 (Inertia-type bound [3 Theorem 3.1]). For an NN-vertex graph with eigenvalues λ1≥⋯≥λN\lambda_1\ge\cdots\ge\lambda_N, and p∈Rk[x]p\in\mathbb{R}_k[x],

αk(G)≤min⁡{∣{i:p(λi)≥w(p)}∣,∣{i:p(λi)≤W(p)}∣}.\alpha_k(G)\le\min\left\{\left|\{i:p(\lambda_i)\ge w(p)\}\right|,\left|\{i:p(\lambda_i)\le W(p)\}\right|\right\}.

For k=1k=1 and p(x)=xp(x)=x this is the Cvetković inertia bound [21]. On a walk-regular graph we may subtract the common diagonal of p(A)p(A). If the resulting matrix has inertia (n+,n−,n0)(n_+,n_-,n_0), where these are the numbers of positive, negative and zero eigenvalues counted with multiplicity, respectively, the bound is n0+min⁡(n+,n−)n_0+\min(n_+,n_-).

For the sharp inertia-type examples below, we use p(x)=x2−δp(x)=x^2-\delta, whose diagonal entries vanish on a δ\delta-regular graph. We count its positive, negative and zero eigenvalues and exhibit codes attaining the resulting bounds. We therefore obtain the optimum in these cases without optimizing over all admissible polynomials [4].

Theorem 4 (Ratio-type bound [3 Theorem 3.2]). Let GG be connected and δ\delta-regular, with λ1=δ\lambda_1=\delta. For p∈Rk[x]p\in\mathbb{R}_k[x], put λ(p)=min⁡i≥2p(λi)\lambda(p)=\min_{i\ge2}p(\lambda_i). If p(δ)>λ(p)p(\delta)>\lambda(p), then

αk(G)≤NW(p)−λ(p)p(δ)−λ(p).\alpha_k(G)\le N\frac{W(p)-\lambda(p)}{p(\delta)-\lambda(p)}.

For k=1k=1 and p(x)=xp(x)=x, this gives Hoffman's ratio bound; see, for example, [27]:

α(G)≤R1(G):=−NλNδ−λN.(4)\alpha(G)\le R_1(G):=-\frac{N\lambda_N}{\delta-\lambda_N}. \tag*{(4)}

The following formulas give the optimal ratio-type bounds in degrees two and three. For higher degrees, the polynomial optimization can be formulated as a linear program (LP) [25].

Theorem 5 (Optimal quadratic ratio-type bound [3 Corollary 3.3]). Let GG be a connected δ\delta-regular graph on NN vertices, with distinct eigenvalues δ=θ0>⋯>θr\delta= \theta_0 > \cdots> \theta_r and r≥2r \ge2. Let θi\theta_i be the largest eigenvalue at most −1-1, and let θi−1\theta_{i-1} be the next larger distinct eigenvalue. Then

α2(G)≤Nδ+θiθi−1(δ−θi)(δ−θi−1).(5)\alpha_2(G) \le N \frac{\delta+ \theta_i\theta_{i-1}}{(\delta-\theta_i)(\delta-\theta_{i-1})}. \tag*{(5)}

This is the optimum obtainable from Theorem 4 with a polynomial of degree at most two.

Theorem 6 (Optimal cubic ratio-type bound [31 Theorem 11]). Let GG be a connected δ\delta-regular graph on NN vertices, with distinct eigenvalues δ=θ0>⋯>θr\delta= \theta_0 > \cdots> \theta_r, where r≥3r \ge3 and θr<−1\theta_r < -1. Put Δ=max⁡v(A3)vv\Delta= \max_v(A^3)_{vv} and let θs\theta_s be the smallest eigenvalue satisfying

θs≥−δ2+δθr−Δδ(θr+1).\theta_s \ge-\frac{\delta^2+\delta\theta_r-\Delta}{\delta(\theta_r+1)}.

Then the optimal degree-at-most-three ratio-type bound is

α3(G)≤NΔ−δ(θs+θs+1+θr)−θsθs+1θr(δ−θs)(δ−θs+1)(δ−θr).(6)\alpha_3(G) \le N \frac{\Delta-\delta(\theta_s+\theta_{s+1}+\theta_r)-\theta_s\theta_{s+1}\theta_r}{(\delta-\theta_s)(\delta-\theta_{s+1})(\delta-\theta_r)}. \tag*{(6)}

The optimizing polynomials in (5) and (6) have the displayed two and three roots, respectively. Degenerate small cases can be evaluated directly using Theorem 4.

For general kk, on a connected walk-regular graph (which is necessarily regular), the normalized minor-polynomial LP of Fiol [25] is equivalently

minimize⁡f∈Rk[x] ∑j=0rmjf(θj),f(δ)=1,f(θj)≥0 (j≥1).(7)\underset{f\in\mathbb{R}_k[x]}{\operatorname{minimize}}\ \sum_{j=0}^{r}m_jf(\theta_j),\qquad f(\delta)=1,\qquad f(\theta_j)\ge0\ (j\ge1). \tag*{(7)}

To see the normalization, set f(x)=(p(x)−λ(p))/(p(δ)−λ(p))f(x)=(p(x)-\lambda(p))/(p(\delta)-\lambda(p)) for an admissible pp. Then f(δ)=1f(\delta)=1 and the other eigenvalues of f(A)f(A) are nonnegative. Such a symmetric matrix is called positive semidefinite (PSD). By (3), its trace is exactly N(W(p)−λ(p))/(p(δ)−λ(p))N(W(p)-\lambda(p))/(p(\delta)-\lambda(p)), the corresponding ratio-type bound. The above is a linear program in the coefficients of ff. It is equivalent to the divided-difference formulation in [25]. Its optimum is the best ratio-type bound (we derive integer code bounds by taking floors).

Remark 7 (Equality in the ratio-type bound). On a connected walk-regular graph, put a=(p(A))vva=(p(A))_{vv} and m=λ(p)m=\lambda(p). For a kk-independent set CC of size ss, its characteristic vector zz satisfies zTp(A)z=saz^{T}p(A)z=sa. Write z=(s/N)1+yz=(s/N)\mathbf{1}+y, where y⊥1y\perp\mathbf{1}. Then

sa≥s2Np(δ)+m(s−s2N).sa \ge\frac{s^2}{N}p(\delta)+m\left(s-\frac{s^2}{N}\right).

For nonempty CC, equality in the real-valued ratio-type bound holds exactly when p(A)y=myp(A)y=my. Since code sizes are integers, the floor of a ratio-type bound may be attained even when the displayed inequality is strict.

Known bounds for permutation codes

The upper bounds we will be using for comparison with the spectral bounds come from packing and anticode arguments, injective projections giving Singleton-type bounds, and algebraic optimization. The refinements available depend on the specific permutation metric. For the Hamming distance, linear programming in the conjugacy scheme of SnS_n [14, 39], semidefinite programming [15], and combinatorial arguments [12] provide upper bounds. For the Ulam distance, the subsequence description gives a Singleton bound, while linear and integer programming give further upper bounds, and computer searches determine exact small values [24, 26]. For the Cayley distance, the dependence on cycle type permits the conjugacy-class LP described below. For Kendall distance, anticode refinements [17], coherent configurations [34], and representation-theoretic integer programming [1] give useful comparisons.

A common starting point is the code–anticode bound. An anticode of diameter at most d−1d-1 is a nonempty subset A⊆SnA \subseteq S_n whose pairwise dMd_M-distances are at most d−1d-1. For each of the four metrics,

AM(n,d)≤⌊n!∣A∣⌋.(8)A_M(n,d) \leq\left\lfloor\frac{n!}{|A|} \right\rfloor. \tag*{(8)}

Indeed, left invariance implies that a code CC of minimum distance at least dd meets each translate gAgA in at most one element. Summing ∣C∩gA∣|C \cap gA| over g∈Sng \in S_n gives ∣C∣ ∣A∣≤n!|C|\,|A| \leq n!. This argument underlies the Kendall bounds from balls and double balls in [17].

Throughout, we use the term sphere-packing bound for the disjoint-ball bound (20), with closed balls of radius t=⌊(d−1)/2⌋t = \lfloor(d-1)/2\rfloor in the metric under consideration. We give their sizes BM(n,t)B_M(n,t) in (16)–(19). Such a ball has diameter at most d−1d-1, so sphere packing is a special case of (8). The following subsections state the relevant Singleton bounds and the more specialized bounds used in our tables. Table 1, Table 2, and Table 4 explicitly include the corresponding Singleton comparisons; the Kendall comparisons use the stronger small-distance bounds described below.

(n,d)(n,d)Ratio bound (4)Singleton (9)Known value or upper boundReference
(4,4)(4,4)544Exact; proof below
(5,4)(5,4)202020Exact; Proposition 12
(6,4)(6,4)120120120Exact [10]
(6,5)(6,5)683018Exact [10]
(7,4)(7,4)543840535Upper bound (SDP) [15]
(7,5)(7,5)610210122Upper bound (combinatorial) [35]

Table 1. Upper bounds on AH(n,d)A_H(n,d) from the ratio bound (4) and the Singleton bound (9), together with known exact values and previously known upper bounds.

(n,d)(n,d)Ratio-type bound (27), (28)Sphere packing (20)Singleton (11)Character LP (30)
(4,3)(4,3)3342
(5,3)(5,3)101010{sup}†`2010
(6,3)(6,3)404512040
(7,3)(7,3)229229840220
(8,3)(8,3)1344139067201344
(9,3)(9,3)98079807604809744
(10,3)(10,3)756007888660480075600
(12,3)(12,3)70441417149277798336007044141
(5,4)(5,4)61055
(6,4)(6,4)24453020
(7,4)(7,4)120229210116
(8,4)(8,4)72013901680700

Table 2. Upper bounds on AC(n,d)A_C(n,d) from the ratio-type bounds (27) and (28), sphere packing (20), the Singleton bound (11), and the character bound (30). The quadratic inertia-type bound additionally gives AC(4,3)=2A_C(4,3)=2 (Proposition 18).

Hamming distance

For 1≤d≤n1 \leq d \leq n, the classical permutation Singleton bound is [14 Theorem 1]

AH(n,d)≤n!(d−1)!.(9)A_H(n,d) \leq\frac{n!}{(d-1)!}. \tag*{(9)}

To see this, retain any fixed n−d+1n-d+1 positions of each codeword. Two codewords with the same retained entries would have Hamming distance at most d−1d-1, so this projection is injective. It has n!/(d−1)!n!/(d-1)! possible values.

Stronger bounds include the linear programming bounds of Tarnanen and Bogaerts [14, 39], semidefinite programming bounds [15], and combinatorial bounds [12]. Exact small values can also be obtained by clique methods [10]. For (n,d)=(7,5)(n,d)=(7,5), Montemanni, Barta and Smith [35] give the upper bound 122, improving the semidefinite programming bound 134.

Ulam distance

For 1≤d≤n1 \leq d \leq n, the Singleton bound is [24]

AU(n,d)≤(n−d+1)!.(10)A_U(n,d) \leq(n-d+1)!. \tag*{(10)}

Here one retains a fixed set of n−d+1n-d+1 symbols in their original order. Equal projected words would give a common subsequence of length n−d+1n-d+1, contrary to minimum Ulam distance dd. Thus the projection is injective and has (n−d+1)!(n-d+1)! possible values.

Farnoud, Skachek and Milenkovic [24] develop the coding framework, while Göloğlu, Lember, Riet and Skachek [26] give linear/integer programming bounds and small exact values. Recent constructions are considered in [11]. We use the exact values in [26 Table I] for comparison.

Cayley distance

A Singleton-type projection argument gives

AC(n,d)≤n!d!,1≤d≤n.(11)A_C(n,d) \le\frac{n!}{d!}, \qquad1 \le d \le n. \tag*{(11)}

Retain any fixed n−dn-d positions. Two permutations with the same retained entries differ only on the remaining dd positions, so their relative permutation has Cayley length at most d−1d-1. The projection is therefore injective on a code of minimum distance at least dd, and it has n!/d!n!/d! possible values.

The sphere-packing bound (20) and the conjugacy-class linear programming bound (30) give further upper bounds. The latter uses the symmetric-group character framework of Tarnanen [39]; the formulation allowing arbitrary admissible conjugacy classes is stated in [14 Theorem 6]. We specify its objective and constraints in (30), selecting the admissible classes by Cayley distance, and compare its values with the spectral, sphere-packing, and Singleton bounds in Table 2.

For minimum Cayley distance three, a radius-one ball consists of its centre and the (n2)\binom{n}{2} transpositions. Thus BC(n,1)=1+(n2)B_C(n,1)=1+\binom{n}{2}, and (20) becomes

AC(n,3)≤⌊n!1+(n2)⌋.(12)A_C(n,3) \le\left\lfloor\frac{n!}{1+\binom{n}{2}} \right\rfloor. \tag*{(12)}

The explicit spectrum of the transposition graph [33] makes the Eigenvalue Method particularly accessible. Finally, note that Nguyen [36] derived improved lower bounds.

Kendall-τ\tau distance

For n−1<d≤(n2)n-1<d\le\binom{n}{2}, Barg and Mazumdar’s Singleton bound [9 Theorem 3.2] gives

AK(n,d)≤⌊32+n(n−1)−2d+14⌋!.(13)A_K(n,d) \le\left\lfloor\frac{3}{2}+\sqrt{n(n-1)-2d+\frac{1}{4}} \right\rfloor!. \tag*{(13)}

It follows by retaining the relative order of a fixed set of symbols. This projection bound improves the trivial bound n!n! only when d>n−1d>n-1, so it gives no improvement for the rows with n≥5n\ge5 in Table 3.

For small even distances, the double-ball bound is a useful refinement of sphere packing [17]. Write BK(σ,t)B_K(\sigma,t) for the closed Kendall ball of radius tt centred at σ\sigma. If dK(e,s)=1d_K(e,s)=1, then BK(e,t)∪BK(s,t)B_K(e,t)\cup B_K(s,t) has diameter at most 2t+12t+1. Applying (8) to this union gives

AK(n,2t+2)≤⌊n!∣BK(e,t)∪BK(s,t)∣⌋.(14)A_K(n,2t+2) \le\left\lfloor\frac{n!}{\lvert B_K(e,t)\cup B_K(s,t)\rvert} \right\rfloor. \tag*{(14)}

For t=1t=1, each ball has size nn and their intersection consists of ee and ss, since the adjacent-transposition graph is bipartite. Hence

AK(n,4)≤⌊n!2(n−1)⌋,(15)A_K(n,4) \le\left\lfloor\frac{n!}{2(n-1)} \right\rfloor, \tag*{(15)}

which gives 420 and 2880 at n=7n = 7 and n=8n = 8, respectively. This is the bound of [17 Corollary 6]. Moreover, [17 Theorem 8] shows that, for n≥4n \ge4, a double ball of radius one is a largest Kendall anticode of diameter three. Thus (15) is the strongest upper bound obtained from (8) using a diameter-three anticode.

Further upper bounds use coherent-configuration methods [34] and representation-theoretic integer programming [1]. The comparison incorporates the updated table of Parvaresh et al. [37] and the exact small values reported in [40]. In particular, the bounds AK(6,3)≤116A_K(6,3) \le116 and AK(7,3)≤716A_K(7,3) \le716 of [1] are stronger than sphere packing.

Graphs associated to permutation codes

We distinguish a graph defined by a minimum-distance threshold from a distance-one base graph. For a finite integer-valued metric space (X,dX)(X,d_X), we can define a graph with

V(G)=X,x∼Gy⟺dX(x,y)=1.V(G) = X,\qquad x \sim_G y \Longleftrightarrow d_X(x,y) = 1.

When dXd_X agrees with the shortest-path distance in GG, we identify its kk-th power GkG^k with the graph joining distinct x,yx,y at metric distance at most kk. In this case, a minimum-distance-(k+1)(k+1) code is a kk-independent set in GG [7]. For permutations we write GM(n)G_M(n) for the base graph and ΓM(n,d)\Gamma_M(n,d) for the forbidden-distance graph. The identity between the latter and GM(n)d−1G_M(n)^{d-1} holds for M∈{K,C,U}M \in\{K,C,U\}; the Hamming exception is explained in Remark 10.

Forbidden-distance graphs (power graphs) and independence bounds

For M∈{H,U,K,C}M \in\{H,U,K,C\}, the graph used to encode the minimum-distance requirement is

ΓM(n,d):V=Sn,σ∼τ⟺0<dM(σ,τ)<d.\Gamma_M(n,d):\quad V = S_n,\qquad\sigma\sim\tau\Longleftrightarrow0 < d_M(\sigma,\tau) < d.

Then AM(n,d)=α(ΓM(n,d))A_M(n,d) = \alpha(\Gamma_M(n,d)). Barta and Montemanni [10] study permutation Hamming graphs joining pairs with dH≥dd_H \ge d, while Göloğlu et al. [26] use the analogous graph with dU≥dd_U \ge d for Ulam-code searches. Their underlying unweighted graphs are therefore the complements of ΓH(n,d)\Gamma_H(n,d) and ΓU(n,d)\Gamma_U(n,d), respectively. For M∈{K,C,U}M \in\{K,C,U\}, in Proposition 9 below we identify ΓM(n,d)\Gamma_M(n,d) with GM(n)d−1G_M(n)^{d-1}.

Lemma 8. Every ΓM(n,d)\Gamma_M(n,d) is a Cayley graph, hence vertex-transitive and walk-regular. If BM(n,t):=∣{π:dM(e,π)≤t}∣B_M(n,t) := |\{\pi: d_M(e,\pi) \le t\}|, its degree is BM(n,d−1)−1B_M(n,d-1)-1.

Proof. Left invariance makes π↦σ−1π\pi\mapsto\sigma^{-1}\pi an isometry sending σ\sigma to ee. Thus ΓM(n,d)\Gamma_M(n,d) is the Cayley graph with connecting set {π:0<dM(e,π)<d}\{\pi: 0 < d_M(e,\pi) < d\}. For any π\pi, left invariance and symmetry give dM(e,π−1)=dM(π,e)=dM(e,π)d_M(e,\pi^{-1}) = d_M(\pi,e) = d_M(e,\pi), so this set is inverse-closed. Its size is BM(n,d−1)−1B_M(n,d-1)-1, since the ball contains its centre. Left translations act transitively on the vertices; they also identify the closed walks based at any two vertices, proving walk-regularity.

For d≥2d \ge2, the Ulam, Cayley and Kendall connecting sets contain all adjacent transpositions, so these graphs are connected. For Hamming distance the graph is connected for d≥3d \ge3, since an adjacent transposition has Hamming distance two. At d=2d = 2, ΓH(n,2)\Gamma_H(n,2) is edgeless. □\square

For reference, the ball sizes are

BH(n,t)=∑j=0t(nj)Dj,Dj=j!∑i=0j(−1)ii!,(16)B_H(n,t) = \sum_{j=0}^{t} \binom{n}{j} D_j,\qquad D_j = j! \sum_{i=0}^{j} \frac{(-1)^i}{i!}, \tag*{(16)}
BC(n,t)=∑j=0t[zj]∏i=1n−1(1+iz)(17)B_C(n,t)=\sum_{j=0}^{t} [z^j]\prod_{i=1}^{n-1}(1+iz) \tag*{(17)}
BK(n,t)=∑j=0t[zj]∏i=1n(1+z+⋯+zi−1)(18)B_K(n,t)=\sum_{j=0}^{t} [z^j]\prod_{i=1}^{n}(1+z+\cdots+z^{i-1}) \tag*{(18)}
BU(n,t)=∑λ⊢nλ1≥n−t(fλ)2(19)B_U(n,t)=\sum_{\substack{\lambda\vdash n\\\lambda_1\ge n-t}}(f^\lambda)^2 \tag*{(19)}

Here DjD_j is the number of derangements of jj symbols, [zj][z^j] denotes coefficient extraction, and fλf^\lambda is the number of standard Young tableaux of shape λ\lambda. The notation λ⊢n\lambda\vdash n means that λ=(λ1,…,λr)\lambda=(\lambda_1,\ldots,\lambda_r) is a partition of nn, with λ1≥⋯≥λr>0\lambda_1\ge\cdots\ge\lambda_r>0 and ∑i=1rλi=n\sum_{i=1}^{r}\lambda_i=n. Its Young diagram has λi\lambda_i boxes in row ii; in particular, λ1\lambda_1 is the largest part and the length of the first row. A standard Young tableau is a filling of these boxes with 1,…,n1,\ldots,n, each used once, increasing along rows and down columns; see [38 Chapters 2–3]. The first three identities count by support, cycles and inversions; the last follows from the Robinson–Schensted correspondence [26, 38]. Under this correspondence, λ1\lambda_1 is the length of a longest increasing subsequence of the permutation, so dU(e,π)≤td_U(e,\pi)\le t is equivalent to λ1≥n−t\lambda_1\ge n-t. Disjoint balls give the sphere-packing bound

AM(n,d)≤⌊n!BM(n,⌊(d−1)/2⌋)⌋(20)A_M(n,d)\le\left\lfloor\frac{n!}{B_M(n,\lfloor(d-1)/2\rfloor)}\right\rfloor \tag*{(20)}

The base graph GM(n)G_M(n) and bounds on αk(GM(n))\alpha_k(G_M(n))

Here GM(n)G_M(n) denotes the graph on SnS_n joining permutations at dMd_M-distance one. For an inverse-closed set S⊆Sn∖{e}S\subseteq S_n\setminus\{e\}, the notation Cay⁡(Sn,S)\operatorname{Cay}(S_n,S) means the graph with vertex set SnS_n and edges {σ,σs}\{\sigma,\sigma s\}, for σ∈Sn\sigma\in S_n and s∈Ss\in S. Equivalently, σ∼τ\sigma\sim\tau when σ−1τ∈S\sigma^{-1}\tau\in S. With our composition convention, right multiplication by a generator acts on positions. The three base graphs are

GK(n)=Cay⁡(Sn,{(i i+1):1≤i<n}),GC(n)=Cay⁡(Sn,{(i j):1≤i<j≤n}),GU(n)=Cay⁡(Sn,T∪T−1),T={(a a+1 ⋯ b):1≤a<b≤n}.\begin{aligned} G_K(n)&=\operatorname{Cay}(S_n,\{(i\ i+1):1\le i<n\}),\\ G_C(n)&=\operatorname{Cay}(S_n,\{(i\ j):1\le i<j\le n\}),\\ G_U(n)&=\operatorname{Cay}(S_n,T\cup T^{-1}),\qquad T=\{(a\ a+1\ \cdots\ b):1\le a<b\le n\}. \end{aligned}

The first is the adjacent-transposition graph associated with Kendall distance, used for example by Buzaglo and Etzion [17]; the second is the all-transposition graph studied spectrally by Konstantinova and Kravchuk [33]. The third uses the translocations defining Ulam distance [24]. The cycle (a a+1 ⋯ b)(a\ a+1\ \cdots\ b) moves the entry in position aa to position bb, shifting the intervening entries left; its inverse moves the entry in position bb to position aa. The union T∪T−1T\cup T^{-1} is a set: adjacent transpositions are self-inverse and are counted only once.

Proposition 9. For M∈{K,C,U}M\in\{K,C,U\}, the graph distance in GM(n)G_M(n) equals dMd_M, and

ΓM(n,d)=GM(n)d−1,AM(n,d)=αd−1(GM(n)).\Gamma_M(n,d)=G_M(n)^{d-1},\qquad A_M(n,d)=\alpha_{d-1}(G_M(n)).

These graphs are connected, regular and walk-regular, with parameters

MetricVerticesDegreeDiameter
Kendalln!n!n−1n-1(n2)\binom{n}{2}
Cayleyn!n!(n2)\binom{n}{2}n−1n-1
Ulamn!n!(n−1)2(n-1)^2n−1n-1

Table 5.

Proof. For Ulam distance, a common subsequence of length LL can be left fixed while the other n−Ln-L symbols are moved, and one translocation can increase the LCS by at most one. Thus its graph distance is n−Ln-L. The Ulam degree is (n−1)+2∑ℓ=3n(n−ℓ+1)=(n−1)2(n-1)+2\sum_{\ell=3}^{n}(n-\ell+1)=(n-1)^2. The other degrees and the diameters follow from the inversion and cycle formulas. All connecting sets contain the adjacent transpositions, so the graphs are connected. The remaining properties follow from Lemma 8. □

Remark 10. Let Hn=H(n,n)\mathcal{H}_n=H(n,n) be the Hamming graph on [n]n[n]^n, whose edges join words differing in exactly one coordinate. Its shortest-path distance is the Hamming distance. Identifying permutations with their one-line words gives Sn⊆[n]nS_n\subseteq[n]^n, and hence, for d≥2d\ge2,

ΓH(n,d)=(Hnd−1)[Sn].(21)\Gamma_H(n,d)=\left(\mathcal{H}_n^{d-1}\right)[S_n]. \tag*{(21)}

Here X[Sn]X[S_n] denotes the subgraph of XX induced by the permutation vertices. Thus the graph power is formed before restricting to SnS_n. Restricting first gives the edgeless graph Hn[Sn]\mathcal{H}_n[S_n], because distinct permutations cannot differ in exactly one coordinate. Its shortest-path distances do not recover dHd_H, and its powers differ from (21) for d≥3d\ge3.

In this case, AH(n,d)=α(ΓH(n,d))A_H(n,d)=\alpha(\Gamma_H(n,d)). A valid (but generally weaker) use of the Cayley base graph follows from dH≤2dCd_H\le2d_C:

AH(n,d)≤AC(n,⌈d/2⌉)=α⌈d/2⌉−1(GC(n)).A_H(n,d)\le A_C(n,\lceil d/2\rceil)=\alpha^{\lceil d/2\rceil-1}(G_C(n)).

In particular, replacing “distance one” by “Hamming distance two” gives the Cayley metric, not Hamming distance divided by two. For example, 1234 and 2143 have Hamming distance four and Cayley distance two. The path 1234, 2134, 2143 shows that they are adjacent in GC(4)2G_C(4)^2, whereas they are not adjacent in ΓH(4,4)\Gamma_H(4,4).

For each partition λ⊢n\lambda\vdash n, let ρλ\rho^\lambda be the corresponding irreducible complex representation of SnS_n, of dimension fλf^\lambda [28]. For an inverse-closed connecting set SS, the spectrum of Cay⁡(Sn,S)\operatorname{Cay}(S_n,S) is the union of the spectra of

Bλ=∑s∈Sρλ(s),λ⊢n,(22)B_\lambda=\sum_{s\in S}\rho^\lambda(s),\qquad\lambda\vdash n, \tag*{(22)}

with every block eigenvalue repeated fλf^\lambda times, by the decomposition of the regular representation [38]. We use rational Young seminormal matrices [38]. To specify the matrices used in the computations, index a basis {vt}\{v_t\} by standard Young tableaux tt of shape λ\lambda, let ct(j)c_t(j) be the column index minus the row index of the box containing jj, and set ai(t)=ct(i+1)−ct(i)a_i(t)=c_t(i+1)-c_t(i). For si=(i i+1)s_i=(i\ i+1), the action is

ρλ(si)vt=1ai(t)vt+(1+1ai(t))vsit,\rho^\lambda(s_i)v_t=\frac{1}{a_i(t)}v_t+\left(1+\frac{1}{a_i(t)}\right)v_{s_it},

where the second term is omitted if sits_it is not standard. Here sits_it is obtained by interchanging the entries ii and i+1i+1. We form products of these matrices to represent the other generators in (22) and compute the characteristic polynomials of the resulting blocks over Q\mathbb{Q}.

For a partition μ⊢n\mu\vdash n, let KμK_\mu be the conjugacy class consisting of all permutations whose cycle lengths, including fixed points, form μ\mu, and let ∣Kμ∣|K_\mu| denote its size. The irreducible character associated with ρλ\rho^\lambda is χλ(g)=tr⁡ρλ(g)\chi^\lambda(g)=\operatorname{tr}\rho^\lambda(g) for g∈Sng\in S_n. Characters are constant on conjugacy classes, so we write χλ(μ)\chi^\lambda(\mu) for this value at any g∈Kμg\in K_\mu; in particular, χλ(e)=fλ\chi^\lambda(e)=f^\lambda. See [38], Chapters 1–2 for these representation-theoretic definitions.

If the connecting set SS is a union of conjugacy classes, Schur’s lemma makes each block BλB_\lambda a scalar matrix. Taking its trace gives the associated eigenvalue [16 Proposition 6.3.1]:

θλ=1fλ∑μ⊢nKμ⊆S∣Kμ∣χλ(μ),λ⊢n.(23)\theta_\lambda=\frac{1}{f^\lambda}\sum_{\substack{\mu\vdash n\\K_\mu\subseteq S}}|K_\mu|\chi^\lambda(\mu),\qquad\lambda\vdash n. \tag*{(23)}

Thus the sum runs over the cycle types whose entire conjugacy classes lie in SS. Each partition λ\lambda contributes (fλ)2(f^\lambda)^2 copies of θλ\theta_\lambda to the spectrum; these multiplicities are added when different partitions give the same eigenvalue. For an explicit statement of this character formula and its multiplicity rule, see [33 Theorem 3].

This applies to ΓH(n,d)\Gamma_H(n,d) and ΓC(n,d)\Gamma_C(n,d): both connecting sets are unions of conjugacy classes, since support size and cycle count depend only on cycle type. In particular,

Spec⁡GC(n)={(∑(i,j)∈λ(j−i))(fλ)2:λ⊢n}.(24)\operatorname{Spec} G_C(n)=\left\{\left(\sum_{(i,j)\in\lambda}(j-i)\right)^{(f^\lambda)^2}:\lambda\vdash n\right\}. \tag*{(24)}

with coincident eigenvalues combined [33]. The Kendall and Ulam generating sets are not conjugacy-invariant, so one must use the full blocks in (22).

The spectral upper bounds

We write Rk(G)R_k(G) for the optimal ratio-type bound obtained from polynomials of degree at most kk. In particular, R1(G)R_1(G) is the ratio bound (4). We evaluate (4), (5), and (6) using the spectra in (22)–(24), and take the floor to obtain integer upper bounds on AM(n,d)A_M(n,d).

In the tables, bold entries give known exact values. A superscript † indicates that a bound is attained only after taking the floor, whereas a bold bound without † is attained before rounding. A superscript ⋆ indicates an improvement over the cited best known upper bound. The Hamming and Kendall tables distinguish exact values from previously known upper bounds in the last column. We also prove that the inertia-type bound is sharp in Propositions 18 and 21.

Theoretical comparison criteria

For M∈{U,C,K}M\in\{U,C,K\}, the quadratic ratio-type bound and the cubic ratio-type bound concern minimum distances three and four, respectively. The Hamming ratio-type bounds below instead use degree one on the forbidden-distance graph. We first give an exact comparison for the quadratic ratio-type bound. On an NN-vertex δ\delta-regular base graph, a radius-one ball has δ+1\delta+1 vertices, so the real-valued sphere-packing benchmark for minimum distance three is S2=N/(δ+1)S_2=N/(\delta+1). We write Spec⁡(G)\operatorname{Spec}(G) for the multiset of eigenvalues of the adjacency matrix of GG.

Proposition 11 (Quadratic ratio-type bound: improvement criterion). Under the hypotheses of Theorem 5, put u=θi≤−1u=\theta_i\leq-1 and v=θi−1>−1v=\theta_{i-1}>-1. Then

g2:=Nδ+1−R2(G)=−Nδ(u+1)(v+1)(δ+1)(δ−u)(δ−v)≥0.(25)g_2:=\frac{N}{\delta+1}-R_2(G)=-\frac{N\delta(u+1)(v+1)}{(\delta+1)(\delta-u)(\delta-v)}\geq0. \tag*{(25)}

Thus the optimal quadratic ratio-type bound is no weaker than sphere packing before rounding, and the inequality is strict if and only if −1∉Spec⁡(G)-1\notin\operatorname{Spec}(G). For comparison with a known bound, let BB be a fixed integer such that α2(G)≤B\alpha_2(G)\leq B. Then

⌊R2(G)⌋<B⟺g2>Nδ+1−B.(26)\lfloor R_2(G)\rfloor<B\Longleftrightarrow g_2>\frac{N}{\delta+1}-B. \tag*{(26)}

In particular, strict improvement over the integer sphere-packing bound occurs exactly when g2>S2−⌊S2⌋g_2>S_2-\lfloor S_2\rfloor.

Proof. Subtracting (5) from N/(δ+1)N/(\delta+ 1) gives (25). The denominator is positive, u+1≤0u + 1 \le0, and v+1>0v + 1 > 0, so g2=0g_2 = 0 exactly when u=−1u = -1. Since uu is the largest eigenvalue at most −1-1, this is equivalent to −1∈Spec⁡(G)-1 \in\operatorname{Spec}(G). Finally, ⌊R2(G)⌋<B\lfloor R_2(G)\rfloor< B is equivalent to R2(G)<BR_2(G) < B because BB is an integer, proving (26).

The previous results shows that, for a fixed length, a comparison of the spectral bound with a specified published coding-theoretic bound is decidable by exact finite calculations.

Hamming metric

We work with ΓH(n,d)\Gamma_H(n,d), whose vertices are permutations and whose edges join pairs with 0<dH<d0 < d_H < d. It is the complement of the underlying permutation Hamming graph used in the clique approach of Barta and Montemanni [10]. We obtain Table 1 by applying the ratio bound directly to ΓH(n,d)\Gamma_H(n,d). We compare these bounds with known exact values and previously known upper bounds in the last two columns.

Table 1: Upper bounds on AH(n,d)A_H(n,d) from the ratio bound (4) and the Singleton bound (9), together with known exact values and previously known upper bounds.

The sharp spectral values at (5,4)(5,4) and (6,4)(6,4) also attain the Singleton bound (9). For the elementary comparison AH(4,4)=4A_H(4,4) = 4, distinct codewords must have distinct symbols in any fixed position, so there are at most four; the four cyclic shifts of 1234 attain this value.

We next prove that the ratio bound is sharp in the following cases.

Proposition 12. For n≥2n \ge2, AH(n,3)=n!/2A_H(n,3) = n!/2, and the ratio bound on ΓH(n,3)\Gamma_H(n,3) is sharp. The ratio bounds in Table 1 at (5,4)(5,4) and (6,4)(6,4) are also sharp before flooring.

Proof. Hamming distance two is exactly a transposition, so ΓH(n,3)=GC(n)\Gamma_H(n,3) = G_C(n). This is a regular bipartite graph whose two parts are the even and odd permutations, and the ratio bound gives n!/2n!/2. For n=5n = 5, the maps x↦ax+bx \mapsto ax + b over F5\mathbb{F}_5, a≠0a \ne0, form twenty permutations; two different maps agree at at most one point. The graph ΓH(5,4)\Gamma_H(5,4) has degree 30 and least eigenvalue −6-6, giving 120⋅6/36=20120 \cdot6/36 = 20. For n=6n = 6, the action of PGL⁡(2,5)\operatorname{PGL}(2,5), the projective general linear group of invertible 2×22 \times2 matrices over F5\mathbb{F}_5 modulo nonzero scalar matrices, on the six points of the projective line P1(F5)=F5∪{∞}\mathbb{P}^{1}(\mathbb{F}_5) = \mathbb{F}_5 \cup\{\infty\} gives 120 permutations; a nonidentity fractional linear transformation fixes at most two points. The graph ΓH(6,4)\Gamma_H(6,4) has degree 55 and least eigenvalue −11-11, giving 720⋅11/66=120720 \cdot11/66 = 120.

These ratio-bound calculations recover the displayed exact values, while the remaining spectral entries in Table 1 are weaker than the cited coding bounds.

Cayley metric

We use the all-transposition base graph GC(n)=Cay⁡(Sn,{(i j):1≤i<j≤n})G_C(n)=\operatorname{Cay}(S_n,\{(i\ j):1\le i<j\le n\}), whose spectrum is studied in [33]. Since AC(n,d)=αd−1(GC(n))A_C(n,d)=\alpha_{d-1}(G_C(n)), we apply the degree-(d−1)(d-1) polynomial spectral bounds directly to GC(n)G_C(n). We observe that the content spectrum (24) yields simple expressions for the quadratic and cubic ratio-type bounds. Let ana_n be the smallest positive eigenvalue of GC(n)G_C(n) and put δ=(n2)\delta=\binom{n}{2}. We obtain the following formulas.

Proposition 13. For n≥3n\ge3,

R2(GC(n))=n!δ+an.(27)R_2(G_C(n))=\frac{n!}{\delta+a_n}. \tag*{(27)}

For n≥4n\ge4,

R3(GC(n))=n!2δ=(n−2)!.(28)R_3(G_C(n))=\frac{n!}{2\delta}=(n-2)!. \tag*{(28)}

Proof. The spectrum is integral and symmetric, and contains zero for n≥3n\ge3 [33]. Hence the consecutive eigenvalues in Theorem 5 are −an,0-a_n,0. Substitution gives (27); a normalized polynomial is x(x+an)/(δ(δ+an))x(x+a_n)/(\delta(\delta+a_n)). The graph is bipartite, so Δ=0\Delta=0 and θr=−δ\theta_r=-\delta. The threshold in Theorem 6 is zero, and its roots are 0,−an,−δ0,-a_n,-\delta. Substitution gives (28). □\square

Remark 14. The cubic ratio-type bound for the Cayley metric also follows from the double-ball construction of [17 Lemma 3], which is stated for an arbitrary metric space. Let ss be a transposition and let BC(σ,1)B_C(\sigma,1) be the closed Cayley ball of radius one centred at σ\sigma. The set

D=BC(e,1)∪BC(s,1)D=B_C(e,1)\cup B_C(s,1)

has diameter at most three. Each ball has δ+1\delta+1 elements, and their intersection is {e,s}\{e,s\} because GC(n)G_C(n) is bipartite. Hence ∣D∣=2δ|D|=2\delta, and the code–anticode bound (8) yields

AC(n,4)≤n!2δ=(n−2)!=R3(GC(n)),n≥4.(29)A_C(n,4)\le\frac{n!}{2\delta}=(n-2)!=R_3(G_C(n)),\qquad n\ge4. \tag*{(29)}

Thus the optimal cubic ratio-type bound recovers this established anticode construction. It strictly improves the integer sphere-packing bound for every n≥4n\ge4: the difference before flooring is

n!δ+1−n!2δ=(n−2)!δ−1δ+1>1.\frac{n!}{\delta+1}-\frac{n!}{2\delta}=(n-2)!\frac{\delta-1}{\delta+1}>1.

Its improvement over sphere packing therefore gives no improvement over the double-ball comparison.

We next determine the smallest positive eigenvalue and identify precisely when the quadratic bound improves sphere packing.

Corollary 15. For n≥3n\ge3, the smallest positive eigenvalue of GC(n)G_C(n) is

an={3,n∈{3,6,10},2,n∈{4,5,8,12},1,otherwise.a_n= \begin{cases} 3, & n\in\{3,6,10\},\\ 2, & n\in\{4,5,8,12\},\\ 1, & \text{otherwise}. \end{cases}

Consequently, after taking the floor, the quadratic ratio-type bound improves the distance-three sphere-packing bound precisely when n∈{6,8,10,12}n\in\{6,8,10,12\}. For all other n≥3n\ge3, the two integer bounds agree.

Proof. We observe that the spectrum is integral. By [33 Lemma 2], 11 is an eigenvalue for every odd n≥7n \ge7 and every even n≥14n \ge14. We evaluate the content sums in (24) for the remaining values n=3,4,5,6,8,10,12n=3,4,5,6,8,10,12 and obtain the displayed exceptions. Substitution into (27) and (12) gives the stated comparison; at n=3,4,5n=3,4,5, the real-valued bounds differ, but their floors are respectively 1,3,101,3,10.

Remark 16.

Since an≥1a_n \ge1, (27) gives ⌊R2(GC(n))⌋≤⌊n!/(δ+1)⌋\lfloor R_2(G_C(n))\rfloor\le\lfloor n!/(\delta+1)\rfloor, so the quadratic ratio-type bound is no weaker than the sphere-packing bound (12). Evaluating the spectrum (24) gives (a6,a8,a10)=(3,2,3)(a_6,a_8,a_{10})=(3,2,3); and substituting in (27) yields 40,1344,7560040,1344,75600, respectively. The corresponding sphere-packing bound values follow directly from (12):

⌊6!16⌋=45,⌊8!29⌋=1390,⌊10!46⌋=78886.\left\lfloor\frac{6!}{16}\right\rfloor=45,\qquad \left\lfloor\frac{8!}{29}\right\rfloor=1390,\qquad \left\lfloor\frac{10!}{46}\right\rfloor=78886.

For all four lengths with strict integer improvement, the quadratic ratio-type bound matches the exact full character-LP value in Table 2.

We also obtain a strict integer improvement at n=12n=12:

AC(12,3)≤⌊12!66+2⌋=7044141<7149277=⌊12!66+1⌋.A_C(12,3)\le\left\lfloor\frac{12!}{66+2}\right\rfloor=7044141<7149277=\left\lfloor\frac{12!}{66+1}\right\rfloor.

Corollary 15 identifies all such improvements; in particular, the quadratic bound agrees with sphere packing for every n≥14n \ge14.

At (n,d)=(4,3)(n,d)=(4,3), Proposition 18 gives the sharp inertia-type bound separately.

We use the following character bound in the framework of Tarnanen [39]; the formulation for arbitrary sets of admissible conjugacy classes is also stated in [14 Theorem 6]. Here we select the admissible classes by Cayley distance. This optimization assigns an independent coefficient to every conjugacy class. For μ⊢n\mu\vdash n, let ℓ(μ)\ell(\mu) be the number of parts of μ\mu, equivalently the number of cycles, including fixed points, of a permutation in KμK_\mu. Such a permutation has Cayley distance n−ℓ(μ)n-\ell(\mu) from ee. Write 1n=(1,…,1)1^n=(1,\ldots,1) for the partition with nn parts equal to one, so K1n={e}K_{1^n}=\{e\}. Define the class matrix AμA_\mu, with rows and columns indexed by SnS_n, by (Aμ)σ,τ=1(A_\mu)_{\sigma,\tau}=1 when σ−1τ∈Kμ\sigma^{-1}\tau\in K_\mu and 00 otherwise. In particular, A1n=IA_{1^n}=I. Write F=∑μ⊢ncμAμF=\sum_{\mu\vdash n}c_\mu A_\mu, with real variables cμc_\mu; the coefficient c1nc_{1^n} is the common diagonal entry of FF. Define

LC(n,d):=min⁡{cμ∈R}μ⊢nn!c1nL_C(n,d):=\min_{\{c_\mu\in\mathbb{R}\}_{\mu\vdash n}} n!c_{1^n}

subject to F1=1F\mathbf{1}=\mathbf{1}, F⪰0F\succeq0,

cμ≤0whenever n−ℓ(μ)≥d,(30)c_\mu\leq0\quad\text{whenever }n-\ell(\mu)\geq d, \tag*{(30)}

The same character decomposition as in (23), applied to the weighted sum defining FF, makes the first two constraints equivalent to

∑μ⊢ncμ∣Kμ∣=1,1fλ∑μ⊢ncμ∣Kμ∣χλ(μ)≥0for every λ⊢n,\sum_{\mu\vdash n}c_\mu\lvert K_\mu\rvert=1,\qquad\frac{1}{f^\lambda}\sum_{\mu\vdash n}c_\mu\lvert K_\mu\rvert\chi^\lambda(\mu)\geq0\quad\text{for every }\lambda\vdash n,

respectively.

For the indicator vector zz of a code CC, zTFz≤∣C∣c1nz^TFz\leq|C|c_{1^n} and zTFz≥∣C∣2/n!z^TFz\geq|C|^2/n!, proving the bound. Consequently, AC(n,d)≤⌊LC(n,d)⌋A_C(n,d)\leq\lfloor L_C(n,d)\rfloor. Allowing nonpositive coefficients on admissible pairs is essential; forcing them to zero gives a different, potentially weaker LP. We evaluate the character LP in (30) to obtain the comparison values in Table 2. In particular, we obtain LC(7,4)=350/3L_C(7,4)=350/3 and LC(12,3)=119750400/17L_C(12,3)=119750400/17, which give the displayed integer bounds.

Next we investigate the comparison of the ratio-type bound with the full character LP bound:

Proposition 17. labelprop:cayley-lp-dominance For n≥2n\geq2 and d≥2d\geq2,

LC(n,d)≤Rd−1(GC(n)).L_C(n,d)\leq R_{d-1}(G_C(n)).

Consequently, no polynomial ratio-type bound on the Cayley base graph, including the quadratic ratio-type bound and the cubic ratio-type bound, can strictly improve the bound supplied by the unrestricted character LP (30).

Proof. Let AA be the adjacency matrix of GC(n)G_C(n) and let pp be admissible in Theorem 4, with deg⁡p≤d−1\deg p\leq d-1. Then

F=p(A)−λ(p)Ip(δ)−λ(p)F=\frac{p(A)-\lambda(p)I}{p(\delta)-\lambda(p)}

is positive semidefinite, has row sum one, and has zero entries on distinct pairs at Cayley distance at least dd. Since the transpositions form a conjugacy class, AA and its polynomials are constant on the relative conjugacy classes, so FF is feasible in (30). Its objective is the ratio-type bound obtained from pp. Minimizing over admissible polynomials proves the result.

The proposition compares two methods and does not assert that every numerical character-LP value in Table 2 was previously published. The four distance-three improvements over sphere packing recover the character-LP values computed here.

In Table 2, the ratio-type bound improves the Singleton bound in every row except (5, 4), where the Singleton and character-LP bounds both give five.

We next prove that the quadratic inertia-type bound is sharp for Cayley codes on four symbols. We observe that, in this case, it is stronger than the optimal quadratic ratio-type bound, extending the sharp applications surveyed in [7 Table 1].

Proposition 18. AC(4,3)=2A_C(4,3)=2. The degree-two inertia bound on GC(4)G_C(4) is sharp, whereas the optimal degree-two ratio-type bound equals three.

Proof. The spectrum is 61,29,04,(−2)9,(−6)16^1, 2^9, 0^4, (-2)^9, (-6)^1. The matrix A2−6IA^2-6I has zero diagonal and inertia (2,22,0)(2,22,0), so Theorem 3 gives α2≤2\alpha_2 \le2. The identity and the cycle (1 2 3 4)(1\ 2\ 3\ 4) have Cayley distance three and attain the bound. Equation (27) gives 24/(6+2)=324/(6+2)=3.

We next give an affine construction attaining the quadratic ratio-type bound on five symbols.

Proposition 19. The quadratic ratio-type bound on GC(5)G_C(5) is sharp and gives AC(5,3)=10A_C(5,3)=10. The Singleton bound is sharp at AC(5,4)=5A_C(5,4)=5.

Proof. Identify the five symbols with F5\mathbb{F}_5. The ten affine permutations

C={x↦ax+b:a∈{1,2}, b∈F5}C=\{x\mapsto ax+b:a\in\{1,2\},\ b\in\mathbb{F}_5\}

have minimum Cayley distance three. For distinct maps with the same multiplier, the relative permutation is a nonzero translation, hence a 5-cycle of Cayley length four. For different multipliers, it has the form x↦cx+tx\mapsto cx+t with c∈{2,3}c\in\{2,3\}. This map has a unique fixed point and is conjugate by a translation to x↦cxx\mapsto cx; because cc has order four in F5∗\mathbb{F}_5^*, its cycle type is (4,1)(4,1) and its Cayley length is three. The content spectrum (24) gives a5=2a_5=2, so (27) yields R2(GC(5))=120/(10+2)=10R_2(G_C(5))=120/(10+2)=10, attained by CC.

The five translations alone have pairwise Cayley distance four and attain the Singleton bound (11), namely 5!/4!=55!/4!=5.

For every n≥2n\ge2, the ratio bound is sharp at AC(n,2)=n!/2A_C(n,2)=n!/2 by parity.

Kendall-τ\tau metric

We use the adjacent-transposition base graph GK(n)=Cay⁡(Sn,{(i i+1):1≤i<n})G_K(n)=\operatorname{Cay}(S_n,\{(i\ i+1):1\le i<n\}), the graph associated with Kendall distance in [17]. In Table 3, we evaluate degree-two and degree-three ratio-type bounds on this graph, with k=d−1k=d-1, rather than ratio bounds on its powers. We compare these bounds with the known values and upper bounds in [37 Table II]. In particular, the values 420 and 2880 follow from the double-ball bound (15) of Buzaglo and Etzion [17].

(n,d)(n,d)Ratio-type bound (5), (6)Known value or upper boundReference
(3,3)(3,3)22Exact; Proposition 21
(4,3)(4,3)65Exact [17]; construction below
(4,4)(4,4)3†3^{\dagger}3Exact; proof below
(5,3)(5,3)2420Exact [40]
(5,4)(5,4)1512Exact [40]
(6,3)(6,3)120116Upper bound [1]
(6,4)(6,4)7264Exact [40]
(7,3)(7,3)720716Upper bound [1]
(7,4)(7,4)419⋆419^{\star}420Upper bound; double ball (15) [17, 37]
(8,4)(8,4)2879⋆2879^{\star}2880Upper bound; double ball (15) [17, 37]

Table 3. Upper bounds on AK(n,d)A_K(n,d) from (5) and (6), together with known exact values and previously known upper bounds. The bounds 419 and 2879 improve the double-ball bounds 420 and 2880 of Buzaglo and Etzion [17].

We next investigate the performance of the quadratic ratio-type bound for the Kendall metric:

Corollary 20. For every n≥3n\ge3,

R2(GK(n))=(n−1)!(31)R_2(G_K(n))=(n-1)! \tag*{(31)}

Thus the optimal quadratic ratio-type bound equals the distance-three sphere-packing bound and cannot improve any previously known upper bound that is at most sphere packing.

Proof. Edelman and White [23 Corollary 5.4] prove that −1-1 is an eigenvalue of the adjacent-transposition graph for every n≥2n\ge2. Apply Proposition 11 with N=n!N=n! and δ=n−1\delta=n-1 to obtain R2(GK(n))=n!/n=(n−1)!R_2(G_K(n))=n!/n=(n-1)!. A Kendall ball of radius one has nn elements, so this is precisely sphere packing.

This result explains all distance-three ratio-type entries in Table 3 without a separate spectral computation at each length. In particular, the quadratic ratio-type bound cannot reach the stronger upper bounds 116 and 716 at lengths six and seven cited in Section 3. At (n,d)=(4,3)(n,d)=(4,3), the nonexistence of a perfect radius-one code gives AK(4,3)≤5A_K(4,3)\le5 [17]; a five-word construction is {1234,1432,2341,3412,4213}\{1234,1432,2341,3412,4213\}.

The parity classes show that R1(GK(n))=AK(n,2)=n!/2R_1(G_K(n))=A_K(n,2)=n!/2. At (n,d)=(4,4)(n,d)=(4,4) the optimal cubic ratio-type value is approximately 3.844526892, whose floor is attained by {1234,4213,3412}\{1234,4213,3412\}. Thus the floor of the cubic bound is sharp.

We next prove that the quadratic inertia-type bound is sharp for Kendall codes on three symbols. We observe that both quadratic spectral bounds attain the exact code size in this case. Together with Proposition 18, this gives sharp inertia-type applications for two permutation metrics.

Proposition 21. The degree-two inertia-type bound on GK(3)G_K(3) is sharp and gives AK(3,3)=2A_K(3,3)=2.

Proof. The graph GK(3)G_K(3) is a six-cycle, with spectrum 21,12,(−1)2,(−2)12^1,1^2,(-1)^2,(-2)^1. For its adjacency matrix AA, the matrix A2−2IA^2-2I has zero diagonal and inertia (2,4,0)(2,4,0). Theorem 3 gives AK(3,3)=α2(GK(3))≤2A_K(3,3)=\alpha_2(G_K(3))\leq2, attained by {123,321}\{123,321\}. The optimal quadratic ratio-type bound also equals two by (5).

We next specialize the cubic ratio-type bound to connected bipartite regular graphs. We observe that nonsingularity of the adjacency matrix gives a strict improvement over N/(2δ)N/(2\delta).

Proposition 22. Let GG be a connected bipartite δ\delta-regular graph on NN vertices, where δ>1\delta>1, and put a=min⁡i∣λi∣a=\min_i|\lambda_i|. The optimal cubic ratio-type bound is

R3(G)=N(δ−a2)2(δ2−a2).(32)R_3(G)=\frac{N(\delta-a^2)}{2(\delta^2-a^2)}. \tag*{(32)}

It is attained by p(x)=(x+δ)(x2−a2)p(x)=(x+\delta)(x^2-a^2) and is strictly smaller than N/(2δ)N/(2\delta) exactly when the adjacency matrix is nonsingular.

Proof. We observe that, since GG is bipartite, its spectrum is symmetric about zero and (A3)vv=0(A^3)_{vv}=0. Moreover, a2<δa^2<\delta: the average of the squared eigenvalues is δ\delta, while the eigenvalue δ\delta has square δ2>δ\delta^2>\delta. The polynomial pp is nonnegative on the spectrum, has minimum zero on the nonprincipal eigenvalues, and satisfies

(p(A))vv=δ2−δa2,p(δ)=2δ(δ2−a2).(p(A))_{vv}=\delta^2-\delta a^2,\qquad p(\delta)=2\delta(\delta^2-a^2).

Theorem 4 therefore gives (32). If there are only three distinct eigenvalues, the biadjacency matrix, whose rows and columns are indexed by the two parts and whose entries record adjacency, has rank one. Since the graph is connected, this zero–one matrix has no zero row or column and must be an all-one matrix. Regularity then gives G=Kδ,δG = K_{\delta,\delta}, for which the optimal bound is one directly. Otherwise, Theorem 6 applies, and its threshold is zero. When a>0a > 0, the three optimizing roots are aa, −a-a, −δ-\delta. When a=0a = 0, its roots are 00, −b-b, −δ-\delta, where −b-b is the largest negative eigenvalue; substitution again gives N/(2δ)N/(2\delta). Finally,

N2δ−R3(G)=Na2(δ−1)2δ(δ2−a2),\frac{N}{2\delta} - R_3(G) = \frac{Na^2(\delta- 1)}{2\delta(\delta^2 - a^2)},

which is positive exactly when a>0a > 0.

Next we focus on understanding the theoretical performance of the cubic ratio-type bound for the Kendall metric, and provide a criteria of spectral improvement.

Corollary 23. labelcor:kendall-cubic-comparison Let n≥4n \ge4, set N=n!N = n! and δ=n−1\delta= n - 1, and let a=min⁡i∣λi∣a = \min_i |\lambda_i| for the adjacency eigenvalues of GK(n)G_K(n). Write Dn=N/(2δ)D_n = N/(2\delta) for the double-ball upper bound in (15). Then

⌊R3(GK(n))⌋<Dn⟺0∉Spec⁡(GK(n)).(33)\lfloor R_3(G_K(n))\rfloor< D_n \quad\Longleftrightarrow\quad0 \notin\operatorname{Spec}(G_K(n)). \tag*{(33)}

More generally, let BB be a fixed integer upper bound on AK(n,4)A_K(n,4), used for comparison and satisfying 1≤B≤Dn1 \le B \le D_n. Then

⌊R3(GK(n))⌋<B⟺a2>δ(N−2δB)N−2B.(34)\lfloor R_3(G_K(n))\rfloor< B \quad\Longleftrightarrow\quad a^2 > \frac{\delta(N - 2\delta B)}{N - 2B}. \tag*{(34)}

If n≡1(mod4)n \equiv1 \pmod{4} or n∈{6,10,12}n \in\{6,10,12\}, then

R3(GK(n))=Dn,R_3(G_K(n)) = D_n,

so the cubic ratio-type bound cannot improve the double-ball bound at those lengths.

Proof. For n≥4n \ge4, Dn=n(n−2)!/2D_n = n(n - 2)!/2 is an integer. Proposition 22 therefore proves (33). For the more general comparison, integrality of BB gives ⌊R3(GK(n))⌋<B\lfloor R_3(G_K(n))\rfloor< B if and only if R3(GK(n))<BR_3(G_K(n)) < B. Substitution of (32) and multiplication by its positive denominator gives

(N−2B)a2>δ(N−2δB).(N - 2B)a^2 > \delta(N - 2\delta B).

Since B≤N/(2δ)B \le N/(2\delta) and δ>1\delta> 1, we have N−2B>0N - 2B > 0, proving (34). Finally, Edelman and White [23 Corollary 6.2 and Theorem 7.2] show that zero is an eigenvalue for n≡1(mod4)n \equiv1 \pmod{4} and for n=6,10,12n = 6, 10, 12. Substituting a=0a = 0 into (32) proves the last result.

Thus nonsingularity is necessary and sufficient for a new integer improvement whenever the published benchmark is the double-ball value. If a stronger bound B<DnB < D_n is available, the strictly positive threshold in (34) must also be exceeded. For a fixed nn, nonsingularity can be decided exactly by checking the determinants of the rational blocks in (22); the proof below uses this criterion at lengths seven and eight. The singular families above give a partial classification in nn, without claiming that all remaining lengths are nonsingular.

We first apply Proposition 22 to GK(7)G_K(7).

Proposition 24. AK(7,4)≤419A_K(7,4) \le419.

Proof. For a connected bipartite δ\delta-regular graph with nonsingular adjacency matrix and δ>1\delta> 1, let 0<η<min⁡i∣λi∣20 < \eta< \min_i |\lambda_i|^2. The polynomial pη(x)=(x+δ)(x2−η)p_\eta(x) = (x+\delta)(x^2-\eta) is nonnegative on the spectrum, has nonprincipal minimum zero at −δ-\delta, and has common diagonal δ2−δη\delta^2-\delta\eta. Therefore

α3(G)≤N(δ−η)2(δ2−η)<N2δ.(35)\alpha_3(G) \le\frac{N(\delta-\eta)}{2(\delta^2-\eta)} < \frac{N}{2\delta}. \tag*{(35)}

We therefore obtain a strict improvement whenever the adjacency matrix is nonsingular.

For GK(7)G_K(7), N=7!=5040N=7!=5040 and δ=6\delta=6. We compute the following determinants of the rational Young seminormal blocks (22), using one representative of each pair of conjugate partitions and including the self-conjugate partition (4,1,1,1)(4,1,1,1) once:

λ\lambda(7)(7)(6,1)(6,1)(5,2)(5,2)(5,1,1)(5,1,1)
det⁡Bλ\det B_\lambda6629112911−1116-111613521352

Table 6 (PDF p. 22).

λ\lambda(4,3)(4,3)(4,2,1)(4,2,1)(4,1,1,1)(4,1,1,1)(3,3,1)(3,3,1)
det⁡Bλ\det B_\lambda−1449-1449−58752-5875211224224

Table 7 (PDF p. 22).

We observe that every displayed determinant is nonzero. Conjugate partitions give sign-twisted blocks, so the remaining blocks are also nonsingular. The decomposition (22) therefore shows that the adjacency matrix of GK(7)G_K(7) is nonsingular.

Thus (35) is strictly smaller than 5040/12=4205040/12=420, proving the integer bound.

We further compute that none of these blocks has an eigenvalue in [−1/100,1/100][-1/100,1/100]. By sign twisting, the same holds for the conjugate partitions.

Thus η=1/10000\eta=1/10000 is admissible, and an explicit polynomial giving the same integer bound is

p(x)=(x+6)(10000x2−1),AK(7,4)≤⌊151197480359999⌋=419.p(x)=(x+6)(10000x^2-1),\qquad A_K(7,4)\le\left\lfloor\frac{151197480}{359999}\right\rfloor=419.

Indeed, p(6)=4319988p(6)=4319988, the common diagonal of p(A)p(A) is 359994359994, and min⁡i≥2p(λi)=0\min_{i\ge2}p(\lambda_i)=0. Substitution in Theorem 4 gives the displayed fraction.

We next apply the same argument to GK(8)G_K(8).

Proposition 25. AK(8,4)≤2879A_K(8,4)\le2879.

Proof. For GK(8)G_K(8), we have N=8!=40320N=8!=40320 and δ=7\delta=7. We compute the following determinants of the rational Young seminormal blocks and observe that each is nonzero. We take one representative of each conjugate pair and include the self-conjugate partitions (4,2,1,1)(4,2,1,1) and (3,3,2)(3,3,2) once.

λ\lambdadet⁡Bλ\det B_\lambdaλ\lambdadet⁡Bλ\det B_\lambda
(8)(8)77(5,1,1,1)(5,1,1,1)−527-527
(7,1)(7,1)6060560605(4,4)(4,4)−6365-6365
(6,2)(6,2)−429341381-429341381(4,3,1)(4,3,1)−2311432523-2311432523
(6,1,1)(6,1,1)−79582797-79582797(4,2,2)(4,2,2)477484825477484825
(5,3)(5,3)−1110876125-1110876125(4,2,1,1)(4,2,1,1)−1915900441-1915900441
(5,2,1)(5,2,1)−23050630659875-23050630659875(3,3,2)(3,3,2)−342065025-342065025

Table 8 (PDF p. 22).

Conjugate partitions give sign-twisted blocks, so every block is nonsingular. Proposition 22 gives R3(GK(8))<40320/14=2880R_3(G_K(8))<40320/14=2880, proving the integer bound.

We compute that these blocks have no eigenvalues in [−1/10000,1/10000][-1/10000,1/10000]. We may therefore use the polynomial

p(x)=(x+7)(108x2−1),p(x)=(x+7)(10^8x^2-1),

which is nonnegative on the spectrum and gives

AK(8,4)≤⌊20160⋅6999999994899999999⌋=2879.A_K(8,4) \le\left\lfloor\frac{20160 \cdot699999999}{4899999999} \right\rfloor= 2879.

The polynomial has common diagonal 4899999993 and p(7)=68599999986p(7) = 68599999986.

We observe that the optimized cubic bounds are approximately 419.987663 for n=7n = 7 and 2879.999925 for n=8n = 8. These improve the double-ball upper bounds 420 and 2880 recorded in [37 Table II]. The nonsingularity criterion explains why a strict improvement occurs: GK(5)G_K(5) and GK(6)G_K(6) are singular and their optimal cubic bounds equal the double-ball values 15 and 72.

For n=8n = 8, we also compute that the block for (4,3,1)(4,3,1) has an eigenvalue in (−1/100,0)(-1/100,0). Thus 0<a<1/1000 < a < 1/100 in Proposition 22, which also proves 2879<R3(GK(8))<28802879 < R_3(G_K(8)) < 2880 directly from (32).

The other nontrivial rows of Table 3 are weaker than the cited exact values or upper bounds.

Ulam metric

We use the unweighted translocation base graph GU(n)=Cay⁡(Sn,T∪T−1)G_U(n) = \operatorname{Cay}(S_n,T \cup T^{-1}) from § 4.2. Its graph distance is the Ulam distance of [24], and it is regular and walk-regular by Proposition 9. We therefore apply the ratio-type bounds to AU(n,d)=αd−1(GU(n))A_U(n,d) = \alpha_{d-1}(G_U(n)). In Table 4, we also evaluate the ratio bound on ΓU(n,d)=GU(n)d−1\Gamma_U(n,d) = G_U(n)^{d-1}. The complement of this power graph is the graph used for the clique computations in [26]. We obtain the Singleton bound column by evaluating (10) and cite the published exact values individually.

Next we study the theoretical performance of the quadratic ratio-type bound for the Ulam metric at even lengths:

Corollary 26. For every even n≥4n \ge4,

R2(GU(n))=n!(n−1)2+1>(n−2)!.(36)R_2(G_U(n)) = \frac{n!}{(n-1)^2 + 1} > (n-2)!. \tag*{(36)}

Consequently, the quadratic ratio-type bound cannot improve the Singleton bound on AU(n,3)A_U(n,3). After flooring, the two bounds agree at n=4n = 4, whereas the quadratic ratio-type bound is strictly weaker for every even n≥6n \ge6.

Proof. Let AA be the adjacency matrix of GU(n)G_U(n) and let v=(vσ)σ∈Snv = (v_\sigma)_{\sigma\in S_n}, where vσ=sgn⁡(σ)v_\sigma= \operatorname{sgn}(\sigma) is 1 for an even permutation and −1 for an odd permutation. A cycle of length ℓ\ell has sign (−1)ℓ−1(-1)^{\ell-1}, so the generating set in § 4.2 gives

Av=(−(n−1)+2∑ℓ=3n(n−ℓ+1)(−1)ℓ−1)v.Av = \left( -(n-1) + 2 \sum_{\ell=3}^{n} (n-\ell+1)(-1)^{\ell-1} \right)v.

For even nn, pairing each odd length ℓ≥3\ell\ge3 with the following even length ℓ+1\ell+ 1 makes the sum in parentheses equal to −1. Thus −1 is an eigenvalue, and Proposition 11, with δ=(n−1)2\delta= (n-1)^2, gives the equality in (36). Moreover,

R2(GU(n))−(n−2)!=(n−2)!(n−2)(n−1)2+1>0.R_2(G_U(n)) - (n-2)! = \frac{(n-2)!(n-2)}{(n-1)^2 + 1} > 0.

The difference is 2/52/5 at n=4n = 4. For n≥6n \ge6, it exceeds one, since (n−2)!≥2(n−2)(n-2)! \ge2(n-2) and 2(n−2)2>(n−1)2+12(n-2)^2 > (n-1)^2 + 1. This proves the wished result.

We observe that neither graph formulation always gives the stronger spectral bound. The bounds on GU(n)G_U(n) are stronger at (6,3)(6,3) and (6,4)(6,4), whereas the ratio bound on ΓU(n,d)\Gamma_U(n,d) is sharp at (5,4)(5,4). The bounds in the first two cases remain weaker than the known coding bounds.

We next prove sharpness in several Ulam instances.

Proposition 27. The ratio bound on GU(3)G_U(3) is sharp. On GU(4)G_U(4) the ratio bound and the degree-two ratio-type bound are sharp after taking the floor at minimum distances two and three, respectively. For every n≥3n \ge3, the ratio bound on ΓU(n,n−1)\Gamma_U(n,n-1) is sharp and AU(n,n−1)=2A_U(n,n-1)=2.

Proof. The spectrum of GU(3)G_U(3) is 414^1, 030^3, (−2)2(-2)^2, giving 6⋅2/(4+2)=26\cdot2/(4+2)=2, attained by {123,321}\{123,321\}. For n=4n=4 the spectrum is

91, (13)3, (5)3, 13, (−1)6, (−5)3, (−3)2, (−13)39^1,\ (\sqrt{13})^3,\ (\sqrt{5})^3,\ 1^3,\ (-1)^6,\ (-\sqrt{5})^3,\ (-3)^2,\ (-\sqrt{13})^3

The ratio bound gives 2413/(9+13)≈6.8646924\sqrt{13}/(9+\sqrt{13})\approx6.86469, whose floor is attained by

{1234,4231,4132,3241,3142,2143}.\{1234,4231,4132,3241,3142,2143\}.

The consecutive eigenvalues in (5) are −1,1-1,1, giving R2=12/5R_2=12/5; the pair {1234,4321}\{1234,4321\} attains its floor. Finally, two permutations have Ulam distance n−1n-1 exactly when their orders are reverses of one another. Consequently ΓU(n,n−1)\Gamma_U(n,n-1) is the complete graph Kn!K_{n!} with a perfect matching removed. It has degree n!−2n!-2 and least eigenvalue −2-2, so the ratio bound gives two, attained by any reversal pair.

Concluding remarks

We have translated permutation-code problems into graph independence problems, and this allowed us to apply the Eigenvalue Method in four different metrics.

For Kendall distance four, nonsingularity of the adjacency matrix is necessary and sufficient for the optimal cubic ratio-type bound to improve the integer double-ball bound, and we obtained improved upper bounds at lengths seven and eight. In contrast, the quadratic ratio-type bound for the Kendall metric equals distance-three sphere packing at every length. For Cayley distance, we determined all lengths at which the quadratic ratio-type bound improves distance-three sphere packing. The cubic ratio-type bound equals the double-ball bound, and the full character LP is at least as strong as all polynomial ratio-type bounds on the Cayley base graph.

For Ulam distance at even lengths, the quadratic ratio-type bound cannot improve the corresponding Singleton bound. Together with the exact integer comparison in Proposition 11, these results show both the scope and the limitations of the ratio-type bounds of low degree (or alternatively, small minimum distance).

Besides the ratio-type bound application, we also obtained sharp inertia-type bounds and recovered several exact code sizes. We observed that the Ulam bounds on a base graph and on its powers can differ, and that the Cayley inertia-type bound on four symbols is stronger than the optimal quadratic ratio-type bound.

The obtained results illustrate the role of the polynomial spectral bounds within the Eigenvalue Method, and their power in studying in permutation codes.

Acknowledgements

Aida Abiad is supported by NWO (Dutch Research Council) through the grant VI.Vidi.213.085. Delio Jaramillo-Velez was partially supported by the NSF grant DMS-2401558. Joachim Rosenthal was supported in part by Swiss National Science Foundation under grant number 212865.

This work was initiated at the Coding Theory and Cryptography Summer School held at the Virginia Tech Steger Center during July 2026; the authors thank the organizers for such an inspiring event.

Declaration of AI use

The authors acknowledge the use of ChatGPT (OpenAI; accessed October 2026) for preliminary brainstorming, language editing, and assistance with checking spectral calculations and drafting supporting arguments. The authors are responsible for verifying the statements, computations, and proofs and for the accuracy and integrity of the final article.

References

  1. [1]A. Abdollahi, J. Bagherian, F. Jafari, M. Khatami, F. Parvaresh, and R. Sobhani. New upper bounds on the size of permutation codes under Kendall τ-metric. Cryptography and Communications, 15(5):891–903, 2023.arxiv.org/abs/2303.02349
  2. [2]A. Abiad, G. Alfarano, and A. Ravagnani. Eigenvalue bounds and alternating rank-metric codes. Journal of Algebra and Its Applications, 24(13n14):2541011, 2025.arxiv.org/abs/2405.09254
  3. [3]A. Abiad, G. Coutinho, and M. A. Fiol. On the k-independence number of graphs. Discrete Mathematics, 342(10):2875–2885, 2019.
  4. [4]A. Abiad, G. Coutinho, M. A. Fiol, B. D. Nogueira, and S. Zeijlemaker. Optimization of eigenvalue bounds for the independence and chromatic number of graph powers. Discrete Mathematics, 345(3):Paper No. 112706, 15, 2022.arxiv.org/abs/2010.12649
  5. [5]A. Abiad, A. P. Khramova, and A. Ravagnani. Eigenvalue bounds for sum–rank–metric codes. IEEE Transactions on Information Theory, 70(7):4843–4855, 2024.arxiv.org/abs/2307.13613
  6. [6]A. Abiad, A. Neri, and L. Reijnders. Eigenvalue bounds for the distance-t chromatic number of a graph and their application to Lee codes. Journal of Algebra and Its Applications, 24(13n14):2541024, 2025.arxiv.org/abs/2404.14839
  7. [7]A. Abiad, L. Peters, and A. Ravagnani. The Eigenvalue Method in coding theory. Canadian Journal of Mathematics, pages 1–41, 2025. Published online 22 September 2025.DOI
  8. [8]A. Barg and A. Mazumdar. Codes in permutations and error correction for rank modulation. In 2010 IEEE International Symposium on Information Theory, pages 854–858. IEEE, 2010.
  9. [9]A. Barg and A. Mazumdar. Codes in permutations and error correction for rank modulation. IEEE Transactions on Information Theory, 56(7):3158–3165, 2010.
  10. [10]J. Barta and R. Montemanni. The maximum clique problem for permutation Hamming graphs. Journal of Optimization Theory and Applications, 194:492–507, 2022.
  11. [11]S. Bereg, M. S. Miah, and M. S. Islam. New lower bounds for permutation codes in the Ulam metric. In N. Misra and A. Pandey, editors, Algorithms and Discrete Applied Mathematics, pages 43–56, Cham, 2026. Springer Nature Switzerland.DOI
  12. [12]J. Bierbrauer and K. Metsch. A bound on permutation codes. The Electronic Journal of Combinatorics, 20(3):P6, 2013.DOI
  13. [13]I. F. Blake, G. Cohen, and M. Deza. Coding with permutations. Information and Control, 43(1):1–19, 1979.DOI
  14. [14]M. Bogaerts. New upper bounds for the size of permutation codes via linear programming. The Electronic Journal of Combinatorics, 17(1):R135, 2010.DOI
  15. [15]M. Bogaerts and P. Dukes. Semidefinite programming for permutation codes. Discrete Mathematics, 326:34–43, 2014.arxiv.org/abs/1212.1185
  16. [16]A. E. Brouwer and W. H. Haemers. Spectra of graphs. Universitext. Springer, New York, 2012.
  17. [17]S. Buzaglo and T. Etzion. Bounds on the size of permutation codes with the Kendall τ-metric. IEEE Transactions on Information Theory, 61(6):3241–3250, June 2015.arxiv.org/abs/1408.4963
  18. [18]E. Byrne and L. François. The multilinear forms Cayley graph and the eigenvalue method for tensor codes, 2026. arXiv:2607.03479v2.arxiv.org/abs/2607.03479
  19. [19]H. Chadwick and L. Kurz. Rank permutation group codes based on Kendall’s correlation statistic. IEEE Transactions on Information Theory, 15(2):306–315, 1969.
  20. [20]C. J. Colbourn, T. Klove, and A. C. Ling. Permutation arrays for powerline communication and mutually orthogonal latin squares. IEEE Transactions on Information Theory, 50(6):1289–1291, 2004.DOI
  21. [21]D. M. Cvetković. Graphs and their spectra. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., (354-356, 354):1–50, 1971.
  22. [22]P. Diaconis and R. L. Graham. Spearman’s footrule as a measure of disarray. Journal of the Royal Statistical Society Series B: Statistical Methodology, 39(2):262–268, 1977.DOI
  23. [23]P. H. Edelman and D. E. White. Codes, transforms and the spectrum of the symmetric group. Pacific Journal of Mathematics, 143(1):47–67, 1990.DOI
  24. [24]F. H. Farnoud, V. Skachek, and O. Milenkovic. Error-correction in flash memories via codes in the Ulam metric. IEEE Transactions on Information Theory, 59(5):3003–3020, 2013.arxiv.org/abs/1202.0932
  25. [25]M. A. Fiol. A new class of polynomials from the spectrum of a graph, and its application to bound the k-independence number. Linear Algebra and its Applications, 605:1–20, 2020.
  26. [26]F. Gölöğlu, J. Lember, A.-E. Riet, and V. Skachek. New bounds for permutation codes in Ulam metric. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 1726–1730. IEEE, 2015.
  27. [27]W. H. Haemers. Interlacing eigenvalues and graphs. Linear Algebra and its Applications, 226/228:593–616, 1995.DOI
  28. [28]G. D. James. The Representation Theory of the Symmetric Groups, volume 682 of Lecture Notes in Mathematics. Springer, Berlin, Heidelberg, 1978.
  29. [29]T. Jiang and A. Vardy. Asymptotic improvement of the Gilbert–Varshamov bound on the size of binary codes. IEEE Transactions on Information Theory, 50(8):1655–1664, 2004.DOI
  30. [30]J. K. Karlof. Permutation codes for the Gaussian channel. IEEE Transactions on Information Theory, 35(4):726–732, 1989.DOI
  31. [31]L. C. Kavi and M. Newman. The optimal bound on the 3-independence number obtainable from a polynomial-type method. Discrete Mathematics, 346(7):113471, 2023.DOI
  32. [32]M. G. Kendall and J. D. Gibbons. Rank Correlation Methods. Edward Arnold, London, fifth edition, 1990.
  33. [33]E. V. Konstantinova and A. Kravchuk. Spectrum of the transposition graph. Linear Algebra and its Applications, 654:379–389, 2022.DOI
  34. [34]F. Y. C. Lim and M. Hagiwara. Linear programming upper bounds on permutation code sizes from coherent configurations related to the Kendall-tau distance metric. In 2012 IEEE International Symposium on Information Theory Proceedings, pages 2998–3002. IEEE, 2012.arxiv.org/abs/1202.0241
  35. [35]R. Montemanni, J. Barta, and D. H. Smith. Permutation codes: a new upper bound for M(7,5). In 2014 International Conference on Informatics and Advanced Computing, 2014.
  36. [36]T. Nguyen. Improving the Gilbert-Varshamov bound for permutation codes in the Cayley metric and Kendall τ-metric. CoRR, abs/2404.15126, 2024.arxiv.org/abs/2404.15126
  37. [37]F. Parvaresh, R. Sobhani, A. Abdollahi, J. Bagherian, F. Jafari, and M. Khatami. Improved bounds on the size of permutation codes under Kendall τ-metric. IEEE Transactions on Information Theory, 71(6):4156–4166, 2025.arxiv.org/abs/2406.06029
  38. [38]B. E. Sagan. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, volume 203 of Graduate Texts in Mathematics. Springer, New York, 2 edition, 2001.
  39. [39]H. Tarnanen. Upper bounds on permutation codes via linear programming. European Journal of Combinatorics, 20(1):101–114, 1999.DOI
  40. [40]S. Vijayakumaran. Largest permutation codes with the Kendall τ-metric in S₅ and S₆. IEEE Communications Letters, 20(10):1912–1915, 2016.
  41. [41]Z. Wang, A. Jiang, and J. Bruck. On the capacity of bounded rank modulation for flash memories. In 2009 IEEE International Symposium on Information Theory, pages 1234–1238. IEEE, 2009.DOI
  42. [42]L. Yang, K. Chen, and L. Yuan. New lower bounds on sizes of permutation arrays, 2008. arXiv:0801.3986.arxiv.org/abs/0801.3986

Paper details

vlnc:W_zz53wggr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents