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 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 metrics, denoted by , , and . For , let be the largest cardinality of a subset of with minimum -distance at least . 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
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 contains no adjacent pair of vertices, and the independence number is the largest size of such a set. A -independent set in a graph has distinct vertices at pairwise shortest path distance greater than ; its largest possible size is the -independence number . The graph power joins distinct vertices at distance at most , so . We will use the following two graph formulations:
For each of the four metrics, the forbidden-distance graph (or equivalently, the -graph power), denoted , has vertex set and joins distinct permutations at -distance less than . A code is exactly an independent set in this graph, giving
For , the base graph, denoted , joins permutations at -distance one. Its shortest path distance is , and hence, for ,
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 , to the -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 on all words in , where :
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 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 -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 of degree at most , the matrix (where is the adjacency matrix of the graph ) has zero off-diagonal entries between vertices at distance greater than , which allows us to bound 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 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 ; its distance-two case is edgeless and gives the trivial exact value . 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 , 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].
Table 4. Upper bounds on from the ratio-type bound on , the ratio bound on , and the Singleton bound (10). The exact values are from [26 Table I], except , 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: (Corollary 15). The improvements are, respectively,
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 and (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 (Proposition 19). For the Hamming distance, the classical ratio bound recovers , and (Proposition 12). For the Ulam distance, the ratio bound on the corresponding graph power gives for every (Proposition 27). The base-graph Ulam bounds are sharp after flooring at and , as is the Kendall cubic bound at .
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 , write , and let be the symmetric group on , with identity . We write permutations in one-line notation and use the composition convention . We first define the four metrics and then introduce the corresponding extremal code sizes. The one-line word for is . With our convention, right multiplication by swaps the entries in positions and , whereas left multiplication relabels symbols.
The symmetric group can be equipped with the following metrics:
Hamming metric
The Hamming distance is
For example, . It measures position-wise disagreement. Its smallest nonzero value on is two.
Ulam metric
Let be the length of a longest common subsequence. The Ulam distance is
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, , 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
Thus and . 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 counts all cycles, including fixed points, then
For example, , since the relative permutation is . 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:
The Hamming and Cayley distances are also right-invariant; this is not true in general for Ulam or Kendall distance. The elementary operations give
For the last pair of inequalities, a nontrivial cycle of length contributes to Hamming distance and to Cayley distance.
For and an integer , a permutation code of minimum -distance at least is a subset of whose distinct elements are pairwise at -distance at least . Let denote its maximum possible size; explicitly,
If , the closed metric balls of radius centred at distinct codewords are disjoint: a point in two such balls would put their centres at distance at most , 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 ).
A finite simple undirected graph consists of a vertex set and a set of edges ; 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 .
For the coding problem of interest, let have vertex set , with distinct and adjacent exactly when . 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
Equivalently, a code is a clique, that is, a set of pairwise adjacent vertices, in the complement of , 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 , denoted , is the length of a shortest path from to , 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 , let join permutations at -distance one. A sequence of elementary edits corresponds to a sequence of adjacent vertices, so the edit-distance definitions give
Consequently, a code of minimum distance has no path of length at most between distinct codewords in . For example, 123, 213, 231, 321 form a shortest path of length three in , since . The pair 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 . 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 be a finite simple undirected graph of order . Its adjacency matrix has rows and columns indexed by , with when and are adjacent and otherwise. Thus, is a real symmetric matrix with zero diagonal. The degree of a vertex is its number of neighbours. A graph is -regular if every vertex has neighbours, in which case , where is the all-one vector.
An automorphism of 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 with identity element , and an inverse-closed set , meaning , the Cayley graph joins and when . Its neighbours at are the elements with . Left multiplication is an automorphism, so the graph is vertex-transitive and -regular. It is connected precisely when generates .
Since is real symmetric, it has an orthonormal basis of eigenvectors and real eigenvalues
listed with multiplicity. The spectrum is this multiset of eigenvalues. We also use the distinct eigenvalues , with multiplicities , so that . In displayed spectra, indicates multiplicity, not exponentiation. For a connected -regular graph, is simple, with eigenvector , and all eigenvalues lie in . We call the remaining eigenvalues nonprincipal; their eigenvectors lie in the subspace orthogonal to .
A walk of length is a sequence of vertices with consecutive vertices adjacent; unlike a path, it may repeat vertices. Matrix multiplication shows that counts walks of length from to . In particular, counts closed walks based at , is the degree of , and is twice the number of triangles containing . We take . 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 to . In particular, for bipartite graphs, a simplification used in the cubic bounds below.
We say that a graph is -partially walk-regular when is independent of for . It is walk-regular if this holds for every . Vertex-transitivity implies walk-regularity. Indeed, an automorphism mapping to gives a bijection between closed walks of any given length based at these vertices. On a walk-regular graph, all diagonal entries of are the same constant, for every polynomial . Taking their sum and using the eigenvalues of gives,
Definition 2. The -independence number of a graph , denoted , is the largest cardinality of a vertex set whose distinct vertices are at graph distance greater than . The
graph power joins distinct vertices at distance at most ; hence where denotes the usual independence number of .
For the permutation base graphs , , a minimum-distance requirement corresponds to . For Hamming distance we instead apply ordinary independence bounds, with , directly to . The graph power should not be confused with the matrix power : the latter counts walks and is generally not a zero–one adjacency matrix.
The spectra of and need not be related by an adjacency polynomial [4]. Applying a polynomial spectral bound to is therefore different from applying the ratio or inertia bound to . 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 for the real polynomials of degree at most , where . For , define the matrix polynomial . It has eigenvalues with the same eigenvectors as , although their ordering can change. The walk-counting interpretation gives the key implication
Indeed, there is no walk of length at most between such vertices. If is -independent, the principal submatrix obtained by restricting both the rows and the columns of to 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
Theorem 3 (Inertia-type bound [3 Theorem 3.1]). For an -vertex graph with eigenvalues , and ,
For and this is the Cvetković inertia bound [21]. On a walk-regular graph we may subtract the common diagonal of . If the resulting matrix has inertia , where these are the numbers of positive, negative and zero eigenvalues counted with multiplicity, respectively, the bound is .
For the sharp inertia-type examples below, we use , whose diagonal entries vanish on a -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 be connected and -regular, with . For , put . If , then
For and , this gives Hoffman's ratio bound; see, for example, [27]:
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 be a connected -regular graph on vertices, with distinct eigenvalues and . Let be the largest eigenvalue at most , and let be the next larger distinct eigenvalue. Then
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 be a connected -regular graph on vertices, with distinct eigenvalues , where and . Put and let be the smallest eigenvalue satisfying
Then the optimal degree-at-most-three ratio-type bound is
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 , on a connected walk-regular graph (which is necessarily regular), the normalized minor-polynomial LP of Fiol [25] is equivalently
To see the normalization, set for an admissible . Then and the other eigenvalues of are nonnegative. Such a symmetric matrix is called positive semidefinite (PSD). By (3), its trace is exactly , the corresponding ratio-type bound. The above is a linear program in the coefficients of . 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 and . For a -independent set of size , its characteristic vector satisfies . Write , where . Then
For nonempty , equality in the real-valued ratio-type bound holds exactly when . 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 [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 is a nonempty subset whose pairwise -distances are at most . For each of the four metrics,
Indeed, left invariance implies that a code of minimum distance at least meets each translate in at most one element. Summing over gives . 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 in the metric under consideration. We give their sizes in (16)–(19). Such a ball has diameter at most , 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.
Table 1. Upper bounds on from the ratio bound (4) and the Singleton bound (9), together with known exact values and previously known upper bounds.
| Ratio-type bound (27), (28) | Sphere packing (20) | Singleton (11) | Character LP (30) | |
| 3 | 3 | 4 | 2 | |
| 10 | {sup}†` | 20 | 10 | |
| 40 | 45 | 120 | 40 | |
| 229 | 229 | 840 | 220 | |
| 1344 | 1390 | 6720 | 1344 | |
| 9807 | 9807 | 60480 | 9744 | |
| 75600 | 78886 | 604800 | 75600 | |
| 7044141 | 7149277 | 79833600 | 7044141 | |
| 6 | 10 | 5 | 5 | |
| 24 | 45 | 30 | 20 | |
| 120 | 229 | 210 | 116 | |
| 720 | 1390 | 1680 | 700 |
Table 2. Upper bounds on 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 (Proposition 18).
Hamming distance
For , the classical permutation Singleton bound is [14 Theorem 1]
To see this, retain any fixed positions of each codeword. Two codewords with the same retained entries would have Hamming distance at most , so this projection is injective. It has 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 , Montemanni, Barta and Smith [35] give the upper bound 122, improving the semidefinite programming bound 134.
Ulam distance
For , the Singleton bound is [24]
Here one retains a fixed set of symbols in their original order. Equal projected words would give a common subsequence of length , contrary to minimum Ulam distance . Thus the projection is injective and has 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
Retain any fixed positions. Two permutations with the same retained entries differ only on the remaining positions, so their relative permutation has Cayley length at most . The projection is therefore injective on a code of minimum distance at least , and it has 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 transpositions. Thus , and (20) becomes
The explicit spectrum of the transposition graph [33] makes the Eigenvalue Method particularly accessible. Finally, note that Nguyen [36] derived improved lower bounds.
Kendall- distance
For , Barg and Mazumdar’s Singleton bound [9 Theorem 3.2] gives
It follows by retaining the relative order of a fixed set of symbols. This projection bound improves the trivial bound only when , so it gives no improvement for the rows with in Table 3.
For small even distances, the double-ball bound is a useful refinement of sphere packing [17]. Write for the closed Kendall ball of radius centred at . If , then has diameter at most . Applying (8) to this union gives
For , each ball has size and their intersection consists of and , since the adjacent-transposition graph is bipartite. Hence
which gives 420 and 2880 at and , respectively. This is the bound of [17 Corollary 6]. Moreover, [17 Theorem 8] shows that, for , 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 and 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 , we can define a graph with
When agrees with the shortest-path distance in , we identify its -th power with the graph joining distinct at metric distance at most . In this case, a minimum-distance- code is a -independent set in [7]. For permutations we write for the base graph and for the forbidden-distance graph. The identity between the latter and holds for ; the Hamming exception is explained in Remark 10.
Forbidden-distance graphs (power graphs) and independence bounds
For , the graph used to encode the minimum-distance requirement is
Then . Barta and Montemanni [10] study permutation Hamming graphs joining pairs with , while Göloğlu et al. [26] use the analogous graph with for Ulam-code searches. Their underlying unweighted graphs are therefore the complements of and , respectively. For , in Proposition 9 below we identify with .
Lemma 8. Every is a Cayley graph, hence vertex-transitive and walk-regular. If , its degree is .
Proof. Left invariance makes an isometry sending to . Thus is the Cayley graph with connecting set . For any , left invariance and symmetry give , so this set is inverse-closed. Its size is , 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 , the Ulam, Cayley and Kendall connecting sets contain all adjacent transpositions, so these graphs are connected. For Hamming distance the graph is connected for , since an adjacent transposition has Hamming distance two. At , is edgeless.
For reference, the ball sizes are
Here is the number of derangements of symbols, denotes coefficient extraction, and is the number of standard Young tableaux of shape . The notation means that is a partition of , with and . Its Young diagram has boxes in row ; in particular, is the largest part and the length of the first row. A standard Young tableau is a filling of these boxes with , 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, is the length of a longest increasing subsequence of the permutation, so is equivalent to . Disjoint balls give the sphere-packing bound
The base graph and bounds on
Here denotes the graph on joining permutations at -distance one. For an inverse-closed set , the notation means the graph with vertex set and edges , for and . Equivalently, when . With our composition convention, right multiplication by a generator acts on positions. The three base graphs are
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 moves the entry in position to position , shifting the intervening entries left; its inverse moves the entry in position to position . The union is a set: adjacent transpositions are self-inverse and are counted only once.
Proposition 9. For , the graph distance in equals , and
These graphs are connected, regular and walk-regular, with parameters
| Metric | Vertices | Degree | Diameter |
| Kendall | |||
| Cayley | |||
| Ulam |
Table 5.
Proof. For Ulam distance, a common subsequence of length can be left fixed while the other symbols are moved, and one translocation can increase the LCS by at most one. Thus its graph distance is . The Ulam degree is . 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 be the Hamming graph on , 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 , and hence, for ,
Here denotes the subgraph of induced by the permutation vertices. Thus the graph power is formed before restricting to . Restricting first gives the edgeless graph , because distinct permutations cannot differ in exactly one coordinate. Its shortest-path distances do not recover , and its powers differ from (21) for .
In this case, . A valid (but generally weaker) use of the Cayley base graph follows from :
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 , whereas they are not adjacent in .
For each partition , let be the corresponding irreducible complex representation of , of dimension [28]. For an inverse-closed connecting set , the spectrum of is the union of the spectra of
with every block eigenvalue repeated 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 by standard Young tableaux of shape , let be the column index minus the row index of the box containing , and set . For , the action is
where the second term is omitted if is not standard. Here is obtained by interchanging the entries and . We form products of these matrices to represent the other generators in (22) and compute the characteristic polynomials of the resulting blocks over .
For a partition , let be the conjugacy class consisting of all permutations whose cycle lengths, including fixed points, form , and let denote its size. The irreducible character associated with is for . Characters are constant on conjugacy classes, so we write for this value at any ; in particular, . See [38], Chapters 1–2 for these representation-theoretic definitions.
If the connecting set is a union of conjugacy classes, Schur’s lemma makes each block a scalar matrix. Taking its trace gives the associated eigenvalue [16 Proposition 6.3.1]:
Thus the sum runs over the cycle types whose entire conjugacy classes lie in . Each partition contributes copies of 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 and : both connecting sets are unions of conjugacy classes, since support size and cycle count depend only on cycle type. In particular,
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 for the optimal ratio-type bound obtained from polynomials of degree at most . In particular, 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 .
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 , 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 -vertex -regular base graph, a radius-one ball has vertices, so the real-valued sphere-packing benchmark for minimum distance three is . We write for the multiset of eigenvalues of the adjacency matrix of .
Proposition 11 (Quadratic ratio-type bound: improvement criterion). Under the hypotheses of Theorem 5, put and . Then
Thus the optimal quadratic ratio-type bound is no weaker than sphere packing before rounding, and the inequality is strict if and only if . For comparison with a known bound, let be a fixed integer such that . Then
In particular, strict improvement over the integer sphere-packing bound occurs exactly when .
Proof. Subtracting (5) from gives (25). The denominator is positive, , and , so exactly when . Since is the largest eigenvalue at most , this is equivalent to . Finally, is equivalent to because 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 , whose vertices are permutations and whose edges join pairs with . 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 . We compare these bounds with known exact values and previously known upper bounds in the last two columns.
Table 1: Upper bounds on 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 and also attain the Singleton bound (9). For the elementary comparison , 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 , , and the ratio bound on is sharp. The ratio bounds in Table 1 at and are also sharp before flooring.
Proof. Hamming distance two is exactly a transposition, so . This is a regular bipartite graph whose two parts are the even and odd permutations, and the ratio bound gives . For , the maps over , , form twenty permutations; two different maps agree at at most one point. The graph has degree 30 and least eigenvalue , giving . For , the action of , the projective general linear group of invertible matrices over modulo nonzero scalar matrices, on the six points of the projective line gives 120 permutations; a nonidentity fractional linear transformation fixes at most two points. The graph has degree 55 and least eigenvalue , giving .
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 , whose spectrum is studied in [33]. Since , we apply the degree- polynomial spectral bounds directly to . We observe that the content spectrum (24) yields simple expressions for the quadratic and cubic ratio-type bounds. Let be the smallest positive eigenvalue of and put . We obtain the following formulas.
Proposition 13. For ,
For ,
Proof. The spectrum is integral and symmetric, and contains zero for [33]. Hence the consecutive eigenvalues in Theorem 5 are . Substitution gives (27); a normalized polynomial is . The graph is bipartite, so and . The threshold in Theorem 6 is zero, and its roots are . Substitution gives (28).
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 be a transposition and let be the closed Cayley ball of radius one centred at . The set
has diameter at most three. Each ball has elements, and their intersection is because is bipartite. Hence , and the code–anticode bound (8) yields
Thus the optimal cubic ratio-type bound recovers this established anticode construction. It strictly improves the integer sphere-packing bound for every : the difference before flooring is
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 , the smallest positive eigenvalue of is
Consequently, after taking the floor, the quadratic ratio-type bound improves the distance-three sphere-packing bound precisely when . For all other , the two integer bounds agree.
Proof. We observe that the spectrum is integral. By [33 Lemma 2], is an eigenvalue for every odd and every even . We evaluate the content sums in (24) for the remaining values and obtain the displayed exceptions. Substitution into (27) and (12) gives the stated comparison; at , the real-valued bounds differ, but their floors are respectively .
Remark 16.
Since , (27) gives , so the quadratic ratio-type bound is no weaker than the sphere-packing bound (12). Evaluating the spectrum (24) gives ; and substituting in (27) yields , respectively. The corresponding sphere-packing bound values follow directly from (12):
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 :
Corollary 15 identifies all such improvements; in particular, the quadratic bound agrees with sphere packing for every .
At , 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 , let be the number of parts of , equivalently the number of cycles, including fixed points, of a permutation in . Such a permutation has Cayley distance from . Write for the partition with parts equal to one, so . Define the class matrix , with rows and columns indexed by , by when and otherwise. In particular, . Write , with real variables ; the coefficient is the common diagonal entry of . Define
subject to , ,
The same character decomposition as in (23), applied to the weighted sum defining , makes the first two constraints equivalent to
respectively.
For the indicator vector of a code , and , proving the bound. Consequently, . 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 and , 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 and ,
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 be the adjacency matrix of and let be admissible in Theorem 4, with . Then
is positive semidefinite, has row sum one, and has zero entries on distinct pairs at Cayley distance at least . Since the transpositions form a conjugacy class, and its polynomials are constant on the relative conjugacy classes, so is feasible in (30). Its objective is the ratio-type bound obtained from . 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. . The degree-two inertia bound on is sharp, whereas the optimal degree-two ratio-type bound equals three.
Proof. The spectrum is . The matrix has zero diagonal and inertia , so Theorem 3 gives . The identity and the cycle have Cayley distance three and attain the bound. Equation (27) gives .
We next give an affine construction attaining the quadratic ratio-type bound on five symbols.
Proposition 19. The quadratic ratio-type bound on is sharp and gives . The Singleton bound is sharp at .
Proof. Identify the five symbols with . The ten affine permutations
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 with . This map has a unique fixed point and is conjugate by a translation to ; because has order four in , its cycle type is and its Cayley length is three. The content spectrum (24) gives , so (27) yields , attained by .
The five translations alone have pairwise Cayley distance four and attain the Singleton bound (11), namely .
For every , the ratio bound is sharp at by parity.
Kendall- metric
We use the adjacent-transposition base graph , 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 , 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].
| Ratio-type bound (5), (6) | Known value or upper bound | Reference | |
| 2 | 2 | Exact; Proposition 21 | |
| 6 | 5 | Exact [17]; construction below | |
| 3 | Exact; proof below | ||
| 24 | 20 | Exact [40] | |
| 15 | 12 | Exact [40] | |
| 120 | 116 | Upper bound [1] | |
| 72 | 64 | Exact [40] | |
| 720 | 716 | Upper bound [1] | |
| 420 | Upper bound; double ball (15) [17, 37] | ||
| 2880 | Upper bound; double ball (15) [17, 37] |
Table 3. Upper bounds on 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 ,
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 is an eigenvalue of the adjacent-transposition graph for every . Apply Proposition 11 with and to obtain . A Kendall ball of radius one has 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 , the nonexistence of a perfect radius-one code gives [17]; a five-word construction is .
The parity classes show that . At the optimal cubic ratio-type value is approximately 3.844526892, whose floor is attained by . 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 is sharp and gives .
Proof. The graph is a six-cycle, with spectrum . For its adjacency matrix , the matrix has zero diagonal and inertia . Theorem 3 gives , attained by . 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 .
Proposition 22. Let be a connected bipartite -regular graph on vertices, where , and put . The optimal cubic ratio-type bound is
It is attained by and is strictly smaller than exactly when the adjacency matrix is nonsingular.
Proof. We observe that, since is bipartite, its spectrum is symmetric about zero and . Moreover, : the average of the squared eigenvalues is , while the eigenvalue has square . The polynomial is nonnegative on the spectrum, has minimum zero on the nonprincipal eigenvalues, and satisfies
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 , for which the optimal bound is one directly. Otherwise, Theorem 6 applies, and its threshold is zero. When , the three optimizing roots are , , . When , its roots are , , , where is the largest negative eigenvalue; substitution again gives . Finally,
which is positive exactly when .
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 , set and , and let for the adjacency eigenvalues of . Write for the double-ball upper bound in (15). Then
More generally, let be a fixed integer upper bound on , used for comparison and satisfying . Then
If or , then
so the cubic ratio-type bound cannot improve the double-ball bound at those lengths.
Proof. For , is an integer. Proposition 22 therefore proves (33). For the more general comparison, integrality of gives if and only if . Substitution of (32) and multiplication by its positive denominator gives
Since and , we have , proving (34). Finally, Edelman and White [23 Corollary 6.2 and Theorem 7.2] show that zero is an eigenvalue for and for . Substituting 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 is available, the strictly positive threshold in (34) must also be exceeded. For a fixed , 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 , without claiming that all remaining lengths are nonsingular.
We first apply Proposition 22 to .
Proposition 24. .
Proof. For a connected bipartite -regular graph with nonsingular adjacency matrix and , let . The polynomial is nonnegative on the spectrum, has nonprincipal minimum zero at , and has common diagonal . Therefore
We therefore obtain a strict improvement whenever the adjacency matrix is nonsingular.
For , and . 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 once:
Table 6 (PDF p. 22).
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 is nonsingular.
Thus (35) is strictly smaller than , proving the integer bound.
We further compute that none of these blocks has an eigenvalue in . By sign twisting, the same holds for the conjugate partitions.
Thus is admissible, and an explicit polynomial giving the same integer bound is
Indeed, , the common diagonal of is , and . Substitution in Theorem 4 gives the displayed fraction.
We next apply the same argument to .
Proposition 25. .
Proof. For , we have and . 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 and once.
Table 8 (PDF p. 22).
Conjugate partitions give sign-twisted blocks, so every block is nonsingular. Proposition 22 gives , proving the integer bound.
We compute that these blocks have no eigenvalues in . We may therefore use the polynomial
which is nonnegative on the spectrum and gives
The polynomial has common diagonal 4899999993 and .
We observe that the optimized cubic bounds are approximately 419.987663 for and 2879.999925 for . These improve the double-ball upper bounds 420 and 2880 recorded in [37 Table II]. The nonsingularity criterion explains why a strict improvement occurs: and are singular and their optimal cubic bounds equal the double-ball values 15 and 72.
For , we also compute that the block for has an eigenvalue in . Thus in Proposition 22, which also proves 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 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 . In Table 4, we also evaluate the ratio bound on . 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 ,
Consequently, the quadratic ratio-type bound cannot improve the Singleton bound on . After flooring, the two bounds agree at , whereas the quadratic ratio-type bound is strictly weaker for every even .
Proof. Let be the adjacency matrix of and let , where is 1 for an even permutation and −1 for an odd permutation. A cycle of length has sign , so the generating set in § 4.2 gives
For even , pairing each odd length with the following even length makes the sum in parentheses equal to −1. Thus −1 is an eigenvalue, and Proposition 11, with , gives the equality in (36). Moreover,
The difference is at . For , it exceeds one, since and . This proves the wished result.
We observe that neither graph formulation always gives the stronger spectral bound. The bounds on are stronger at and , whereas the ratio bound on is sharp at . 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 is sharp. On 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 , the ratio bound on is sharp and .
Proof. The spectrum of is , , , giving , attained by . For the spectrum is
The ratio bound gives , whose floor is attained by
The consecutive eigenvalues in (5) are , giving ; the pair attains its floor. Finally, two permutations have Ulam distance exactly when their orders are reverses of one another. Consequently is the complete graph with a perfect matching removed. It has degree and least eigenvalue , 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]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]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]A. Abiad, G. Coutinho, and M. A. Fiol. On the k-independence number of graphs. Discrete Mathematics, 342(10):2875–2885, 2019.
- [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]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]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]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]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]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]J. Barta and R. Montemanni. The maximum clique problem for permutation Hamming graphs. Journal of Optimization Theory and Applications, 194:492–507, 2022.
- [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]J. Bierbrauer and K. Metsch. A bound on permutation codes. The Electronic Journal of Combinatorics, 20(3):P6, 2013.DOI
- [13]I. F. Blake, G. Cohen, and M. Deza. Coding with permutations. Information and Control, 43(1):1–19, 1979.DOI
- [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]M. Bogaerts and P. Dukes. Semidefinite programming for permutation codes. Discrete Mathematics, 326:34–43, 2014.arxiv.org/abs/1212.1185
- [16]A. E. Brouwer and W. H. Haemers. Spectra of graphs. Universitext. Springer, New York, 2012.
- [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]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]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]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]D. M. Cvetković. Graphs and their spectra. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., (354-356, 354):1–50, 1971.
- [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]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]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]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]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]W. H. Haemers. Interlacing eigenvalues and graphs. Linear Algebra and its Applications, 226/228:593–616, 1995.DOI
- [28]G. D. James. The Representation Theory of the Symmetric Groups, volume 682 of Lecture Notes in Mathematics. Springer, Berlin, Heidelberg, 1978.
- [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]J. K. Karlof. Permutation codes for the Gaussian channel. IEEE Transactions on Information Theory, 35(4):726–732, 1989.DOI
- [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]M. G. Kendall and J. D. Gibbons. Rank Correlation Methods. Edward Arnold, London, fifth edition, 1990.
- [33]E. V. Konstantinova and A. Kravchuk. Spectrum of the transposition graph. Linear Algebra and its Applications, 654:379–389, 2022.DOI
- [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]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]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]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]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]H. Tarnanen. Upper bounds on permutation codes via linear programming. European Journal of Combinatorics, 20(1):101–114, 1999.DOI
- [40]S. Vijayakumaran. Largest permutation codes with the Kendall τ-metric in S₅ and S₆. IEEE Communications Letters, 20(10):1912–1915, 2016.
- [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]L. Yang, K. Chen, and L. Yuan. New lower bounds on sizes of permutation arrays, 2008. arXiv:0801.3986.arxiv.org/abs/0801.3986