Permutation Codes, Hamming Graphs and Turan Graphs

This paper investigates the properties of permutation Ham- ming graphs, a class of graphs in which the vertices are the permutations of n symbols and the edges connect pairs of vertices at a Hamming dis- tance greater than or equal to a value d. Despite a remarkable regularity, permutation Hamming graphs elude general formulas for relevant indica- tors like the clique number. The clique number plays a crucial role in the Maximum Permutation Code Problem (MPCP), a well-known optimiza- tion problem. This work focuses on the relationship between permutation Hamming graphs and a particular type of Tura ́n graphs. The main re- sult is a theorem asserting that permutation Hamming graphs are the intersection of a set of Tur ́an graphs. This equivalence has implications on the MPCP. In fact it enables a reformulation as a hitting set problem, which in turn can be translated into a binary integer program.