Return to Answer

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. Kind of like mastermind with 3 pegs, 7 colors, and no repeated colors allowed. Here is one representative of each associate class with respect to 123:

distance 2: 132 134 145

distance 3: 214 231 234 245 456

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&0&2&6&0&0&0&0&0\\ 0&0&0&8&0 &4&0&0&0&0\\ 0&1&1&3&3&0&0&1&3&0 \\ 0&2&0&2&4&0&0&0&2&2\\ 0&0&1&0&0 &3&0&2&6&0\\ 0&0&0&0&0&0&0&12&0&0 \\ 0&0&0&1&0&1&1&3&6&0\\ 0&0&0&1&1 &1&0&2&5&2\\ 0&0&0&0&3&0&0&0&6&3\end {array} \right] $$

Further analysis is possible, such as finding nice eigenvectors and substructures, but I still suspect that someone knows all this.

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 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.

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. Kind of like mastermind with 3 pegs, 7 colors, and no repeated colors allowed. Here is one representative of each associate class with respect to 123:

distance 0: 123 (itself)

distance 1: 124

distance 2: 132 134 145

distance 3: 214 231 234 245 456

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&0&2&6&0&0&0&0&0\\ 0&0&0&8&0 &4&0&0&0&0\\ 0&1&1&3&3&0&0&1&3&0 \\ 0&2&0&2&4&0&0&0&2&2\\ 0&0&1&0&0 &3&0&2&6&0\\ 0&0&0&0&0&0&0&12&0&0 \\ 0&0&0&1&0&1&1&3&6&0\\ 0&0&0&1&1 &1&0&2&5&2\\ 0&0&0&0&3&0&0&0&6&3\end {array} \right] $$

Further analysis is possible, such as finding nice eigenvectors and substructures, but I still suspect that someone knows all this.

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][1]. [1]: http://en.wikipedia.org/wiki/Permutohedron

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..)