6
$\begingroup$

It is well-known that Petersen graph is an strongly regular graph with parameters (10,3,0,1) and can be considered as complement graph of $L(K_5)$ and its spectrum is $\{3,1^5,(-2)^4\}$.

Also, It is proved that any graph with $\lambda(G)\ge -2$ can be represented in one of the root systems $A_n$, $D_n$, $E_8$, $E_7$ or $E_6$. Also it is proved that all exceptional graphs are representable in the root system $E_8$, which is contained of $E_7$ and $E_6$.

It can be easily proved that Petersen graph is not a generalized line graph and so it is an exceptional graph. So it have a representation in the root systems $E_8$, $E_7$ or $E_6$.

I want to find a representation for this graph in $E_6$ but because I don't have enough vision in the elements of the root system $E_6$, I could not find this representation.

I will be so thankful for any help and answer about finding this representation.

$\endgroup$
5
$\begingroup$

Consider sets of lines in $\mathbb{R}^d$, such that the angle between two distinct lines is either $60^\circ$ or $90^\circ$. Such a set is indecomposable if we cannot partition it into two non-empty subsets such that vectors in different subsets are ore orthogonal. It is star-closed if whenever if contains lines $L$ and $M$ at an angle of $60^\circ$, it also contains the unique third line in their span that is at $60^\circ$ to $L$ and $M$. Cameron, Goethals, Seidel and Seidel proved that an indecomposable star-closed set of lines (with mutual angles $60^\circ$ and $90^\circ$) is necessarily one of the root systems $A_n$, $D_n$, $E_6$, $E_7$, $E_8$. Further any set of lines at mutual angles $60^\circ$ and $90^\circ$ can be star-closed.

Now let $A$ be the adjacency matrix of the Petersen graph. Then $A+2I$ is positive semidefinite and it is therefore the Gram matrix of 10 vectors of squared-length two. Since $-2$ has multiplicity four as an eigenvalue, $A+2I$ has rank six and so our 10 vectors lie in $\mathbb{R}^6$. It follows that the star-closure of these lines is a root system in $\mathbb{R}^6$. Since the Petersen graph is not a generalized line graph, it must be $E_6$.

You can find more information about this in the paper by Cameron et al; there is also a treatment in Chapter 12 of "Algebraic Graph Theory" by Royle and myself.

$\endgroup$
  • $\begingroup$ Thank you very much for your exact answer. I have studied the two references that you mentioned in your answer, but I have another question in one of them. In constructing representation of Petersen graph in example 4.9 of the paper by Cameron et al; I don't understand this part well: In $L(K_{3,3})$ plus isolated vertex $\{e_4,e_8\}\cup\{e_i+e_j:i=1,2,3;j=5,6,7\}$, we switch with respect to $\{e_i+e_{4+i}:i=1,2,3\}$. Is this the representation of Petersen in $E_6$? $\endgroup$ – A-213 Jan 1 '15 at 21:14
  • 1
    $\begingroup$ To be frank, I do not see how they apply switching. But they give an explicit embedding of the Clebsch graph and the Petersen graph is the subgraph of Clebsch induced by vertices at distance two from a given vertex. $\endgroup$ – Chris Godsil Jan 2 '15 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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