It is trivial to see that any graph can be embedded as a unit-distance graph, if the space-dimension is high enough. The fact that the Heawood and Doyle graphs have unit distance embeddings in the plane is pretty remarkable, I guess. But the NATURAL QUESTION now is: for your favorite family of graphs, what is the minimum space dimension D you need, to unit-distance-embed it? This is an interesting (new?) integer-valued graph invariant. The question is especially interesting for "distance regular" graphs. For them, there exist natural embeddings that arise as follows. If the graph has graphical diameter d, then the NxN symmetric adjacency matrix of the graph has d+1 distinct real eigenvalues. The N eigenvectors all wlog lie on a unit sphere surface in N dimensions. For any two vertices at graphical distance J from you, their corresponding eigenvectors should lie at geometrical distance f(J) from you. In particular, we get a constant-edge-length embedding of the graph drawn on a sphere. Now for the vertices at graphical distance J from somebody, they lie on a lower-dimensional sphere, the dimension being the dimension of the appropriate eigenspace. Now let us consider "projective planes" encoded via their point-line NxN bipartite incidence structures. Always N=k^2+k+1 and N is prime power in all known examples. ** The Heawood graph is the case N=7 and shows D(7)=2. ** The K33 graph is the case N=3 and since the K23 subgraph is *not* unit-distance graph in the plane, this is not either, but K23 can be embedded in 3-space with unit distances (triangular bipyramid) and Kjj can be embedded in 4-space for any value of j: place the j red points on a circle of radius 1/sqrt(2) in the xy plane, and the j blue points on another such circle in the zt plane, both centered at (0,0,0,0). I can prove K33 is not embeddable in 3-space: consider unit spheres centered at the 3 red points; their intersection is necessarily at most 2 points if the 3 red points are distinct. QED. (If coincident points were allowed, then any bipartite graph would be embeddable on the line.) So D(3)=4. ** The next cases would be N=13 and N=21. The projective planes viewed as bipartite graphs with N+N vertices, N=k^2+k+1, always have graphical diameter=4. The eigenvalues of the NxN red-blue adjacency matrix? The squared matrix equals J+k*I, where I=identity matrix and J=all ones matrix, which makes spectrum determination for the squared matrix easy: its eigenvalues are (k+1) with multiplicity 1, and sqrt(k) with multiplicity N-1. The eigenvalues of the 2Nx2N full adjacency matrix then should be +-(k+1) with multiplicity 1 each, and +-sqrt(k) with multiplicity N-1 each. This eigen-information does not seem to lead to any interesting low dimensional embeddings, sorry.
participants (1)
-
Warren D Smith