# Is the following graph well known?

• The vertices are all (ordered) $k$-tuples with distinct components from a universe of size $n$.
• Two vertices are adjacent if their Hamming distance is 1 (i.e. if they differ in exactly one component).

Notice that this graph has $\frac{n!}{(n-k)!}$ vertices. It is an $k(n-k)$-regular graph.

Does the graph have a name?

A closely related graph is the Hamming graph (denoted by $H(n,k)$), which does not exclude the tuples with duplicate components. It has $k^n$ vertices. It is closely related because the graph I am looking for is the induced subgraph of $H(n,k)$ after removing the vertices corresponding to tuples with repeat components.

Another similar graph is the Johnson graph, whose vertices are all subsets of size $k$ from a universe of size n with an edge between two vertices if their set intersection is $n-1$. It has $\binom{n}{k}$ vertices.

The Kneser graph (and its generalization) have similar definitions as well, but like the Johnson graph, they also have $\binom{n}{k}$ vertices.

• I finally understand what you are asking --- to clarify you might indicate that the $k$-tuples in your graph are ordered k-tuples. – Matthew Kahle Dec 15 '10 at 20:51
• If anyone is interested, here is a link to a paper that deals with graphs that are similar to (but more general than) Johnson Graphs: arXiv. It doesn't answer the question though, just an interesting paper that is somewhat relevant to this topic. – Jon Noel Feb 9 '11 at 20:19

They might have a name, I don't know. For the next few lines let us call each a Partial Permutation graph $PP(n,k)$ (assume $k<n$). They may not get as much respect because they are not distance transitive (which the Hamming, Johnson and Knesser Graphs are) or even distance regular (but see below for the special case $k=n$). The Symmetric Group on the underlying set acts on all 4 kinds of graphs and allows one to map any vertex to any other. Consider $n>4$ and $k=2$. In all 4 cases the maximum distance is 2. In $J(n,2)$ any two non-adjacent vertices such as $\lbrace a,b \rbrace$ & $\lbrace c,d \rbrace$ have 4 mutual neighbors. In $H(n,2)$, $[a,b]$ & $[c,d]$ have two mutual neighbors ($[a,d]$ and $[c,b]$) as do $[a,a]$ & $[c,d]$ or $[a,a]$ & $[c,c]$ and more importantly $[a,b]$ & $[c,a]$ as well as $[a,b]$ & $[b,a]$. I'll leave Knesser graphs for the reader to consider. In $PP(n,2)$ $[a,b]$ & $[c,d]$ still have two mutual neighbors but $[a,b]$ & $[c,a]$ only have one while $[a,b]$ & $[b,a]$ have none. So there are three ways to be at distance $2$. It is a 5-class association scheme of diameter 2 however. For $k=3$ or $k=4$ there begin to be a great number of associate classes. If I calculate correctly, for $n>2k$ $PP(n,k)$ has diameter $k$ but $\binom{k+1}{2}-1$ associate classes (or orbits on pairs of vertices under the action of the automorphism group if you prefer)

In the special case that $k=n$ one would have a graph with $n!$ vertices each of degree $\binom n2$ (one would have to let adjacency be differing in only two positions). Since that is a Cayley graph for $S_n$, it is distance transitive. In the more restricted case that adjacency is that two permutations differ only by the swap of two adjacent positions it is the skeleton of the permutohedron.

later I certainly looked at those graphs at some point. At the time I did not realize that they (seem) to always have all eigenvalues integral (based on a criminally small number of test cases). I wonder if there is an easy way to see that happens (if it does..)

much later The graph PP(7,3) actually has 10 associate classes. I had fun so here are the details. A disclaimer, I'm sure that group representation methods are much more efficient if one knows how to use them.I found the classes by making the 210 by 210 adjacency matrix then raising it to the 4th power. Of the 44100 entries, 10 distinct values occur and they reveal what the classes are (although once you know it is obvious!). Then the adjacency matrix (or simple combinatorics) reveals the numbers. The relation depends on the number of entries equal in value and in the same place and also the number of entries equal but not in the same place. And then more. Note that with respect to 123, both 214 and 241 have one new symbol, but 123 and 214 are at distance 4 (say 123 124 154 254 214) while 123 143 243 241 is a distance 3 path.

distance 0: 123 (itself)

distance 1: 124

distance 2: 134 145

distance 3: 234 245 456 132

distance 4: 214 231

distance 0: 123 (itself)

distance 1: 124

distance 2: 145 134

distance 3: 132 456 451 432

distance 4: 214 231

Each vertex (such as u=123) is adjacent to 12 other vertices. If v is a vertex in class i with respect to u then row i in this matrix shows in column j how many of the 12 neighbors of u are in class j with respect to v. Then we find that the eigenvalues of this small matrix are [12,8,5,4,3,1,0,-3,-3,-3] The repeated eigenvalue -3 was what made me suspect that there were 8 classes. `

$$\left[ \begin {array}{cccccccccc} 0&12&0&0&0&0&0&0&0&0 \\ 1&3&6&2&0&0&0&0&0&0\\ 0&2&4&2&0 &2&2&0&0&0\\ 0&1&3&3&1&0&3&1&0&0 \\ 0&0&0&8&0&0&0&0&4&0\\ 0&0&3&0&0 &3&6&0&0&0\\ 0&0&1&1&0&2&5&2&1&0 \\ 0&0&0&1&0&0&6&3&1&1\\ 0&0&0&0&1 &0&6&2&3&0\\ 0&0&0&0&0&0&0&12&0&0\end {array}\right]$$ Further analysis is possible, such as finding nice eigenvectors and substructures, but I still suspect that someone knows all this.

• I don't recall. As a test case, (which I did not do before) PP(7,3) has 210 vertices, diameter 3, and eigenvalues.....(time to write a program)...[63, 1], [16, 12], [7, 6], [3, 104], [-3, 14], [-5, 30], [-9, 28], [-11, 15] (that is to say that 3 is an eigenvalue of multiplicity 104). I did that in the simplest way possible (let Maple use 1 minute of my time 48M of memory and 3 sec of computing on a 210 by 210 0,1 matrix). With more thought on my side it should be possible to do PP(n,3) with a symbolic 8 x 8 matrix . – Aaron Meyerowitz Dec 21 '10 at 16:34
• Sorry, that was actually the distance 2 matrix (i.e. [1,2,3] connected to [1,4,5] & [1,4,2] & [1,3,2]) The correct eigenvalues and multiplicities are: [12, 1], [8, 12], [5, 6], [4, 15], [3, 28], [1, 30], [0, 14], [-3, 104] – Aaron Meyerowitz Dec 21 '10 at 21:00
• Thanks. I added details on the eigenvalues for one graph. – Aaron Meyerowitz Jan 5 '11 at 7:13
• In a distance transitive graph the number of associate classes is the diameter (plus one). In a power $A^k$ (or polynomial $f(A)$) of the adjacency matrix the value of the $(u,v)$ entry depends only on the associate class. So looking at $A^k$ can reveal the associate classes. I am being imprecise here. An association scheme is any partition of the pairs subject to certain conditions. I am (as is usuual) calling that scheme with the fewest classes the association scheme of the graph. – Aaron Meyerowitz Jan 6 '11 at 5:11
• The regularity conditions can hold with out there actually being automorphisms, then the graph is said to be distance regular. There is one example (of a distance regular but not distance transitive) graph with degree 3. It has 126 vertices and (thus) 189 edges. – Aaron Meyerowitz Jan 6 '11 at 5:12

It is the "generalized Kneser graph". See the Wikipedia article on "Kneser graph" and references therein. See also a paper by B. Mohar and I. Rivin on related geometric questions...

• Are you sure? The graph the I am looking for has n!/(n-k)! vertices, but the Kneser graph (and its generalization) have (n choose k). – Tyson Williams Dec 15 '10 at 19:42
• The below is a paste from the wikipedia article: The generalized Kneser graph KGn,k,s has the same vertex set as the Kneser graph KGn,k, but connects two vertices whenever they correspond to sets that intersect in s or fewer items (Denley 1997). Thus KGn,k,0 = KGn,k. – Igor Rivin Dec 15 '10 at 19:48
• Yes, I read that. Are you saying that the graph I described and the Kneser graph have the same number of vertices? – Tyson Williams Dec 15 '10 at 19:51
• It doesn't look to me as though any value of s makes the generalised Kneser graph fit Tyson's criteria. They fail on two counts: (1) the vertex sets should be ordered tuples, not subsets, as already observed, and (2) the adjacency criterion would need to be specify the size of the intersection exactly (as $k-1$) rather than merely giving an upper bound ($\leq s$). – Vaughn Climenhaga Dec 15 '10 at 22:22