7
$\begingroup$
  • 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.

$\endgroup$
2
  • $\begingroup$ I finally understand what you are asking --- to clarify you might indicate that the $k$-tuples in your graph are ordered k-tuples. $\endgroup$ Commented Dec 15, 2010 at 20:51
  • $\begingroup$ 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. $\endgroup$
    – Jon Noel
    Commented Feb 9, 2011 at 20:19

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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 . $\endgroup$ Commented Dec 21, 2010 at 16:34
  • 1
    $\begingroup$ 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] $\endgroup$ Commented Dec 21, 2010 at 21:00
  • 1
    $\begingroup$ Thanks. I added details on the eigenvalues for one graph. $\endgroup$ Commented Jan 5, 2011 at 7:13
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 6, 2011 at 5:11
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 6, 2011 at 5:12
3
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ 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). $\endgroup$ Commented Dec 15, 2010 at 19:42
  • $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Commented Dec 15, 2010 at 19:48
  • $\begingroup$ Yes, I read that. Are you saying that the graph I described and the Kneser graph have the same number of vertices? $\endgroup$ Commented Dec 15, 2010 at 19:51
  • 1
    $\begingroup$ 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$). $\endgroup$ Commented Dec 15, 2010 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.