Skip to main content
MathOverflow

Return to Answer

Added note that the Truncated Octahedron illustrates the result about bipartite graphs.
Source Link
Blue
Blue
  • 1.2k
  • 1
  • 9
  • 17

Not an answer, but perhaps the basis for a plan of attack ...

A consequence of the spectral theorem as it applies to the adjacency matrix of a graph $G$ is that, for every (presumably real) eigenvalue --say, with multiplicity $m$-- there exists a geometric realization, $R$, of $G$ in $\mathbb{R}^m$ such that each automorphism of $G$ induces a rigid isometry of $R$. I call these "spectral realizations" (which I discuss at length in my note "Spectral Realizations of Graphs" (PDF)). A spectral realization has this eigenic property: moving each vertex to the vector sum of its neighbors has the same effect as scaling the realization by the associated eigenvalue.

For example, these are the spectral realizations of the 15-cycle and the (skeleton of the) Truncated Octahedron (uniform polyhedron $U_8$).

Spectral Realizations of the 15-cycle http://daylateanddollarshort.com/math/pdfs/mathoverflow-spectralpolygons.png

(Whoops! Typo: Caption should read "Note that (b), (c), (e), and (h) are faithful".)

Spectral Realizations of the Truncated Octahedron http://daylateanddollarshort.com/math/pdfs/mathoverflow-spectralpolyhedra.png

(The caption seems to imply that there are other, higher-dimensional, realizations of the Truncated Octahedron; in this case, there are none. The caption is a template used for over 70 figures in my note, and I haven't gone back to edit the individual cases.)

One way to attack your problem, then, would be to attempt to reverse the implication: Use the combinatorics of the graph to prove independently that sufficiently many spectral realizations exist, "using up" all the eigen-dimensions; the associated eigenvalues must be real as they serve as scale factors for the eigenic property of these realizations.

It's not clear to me how a combinatorial approach to finding these realizations would proceed; they fall so neatly out of the spectral theorem, after all. However, I can demonstrate that sometimes there's a nice interplay between the combinatorics and the geometry; here's an example I left as a comment to an answer of another MO question:

Proposition: If $\lambda$ is a (real) eigenvalue of a bipartite graph, then so is $-\lambda$.

Proof: If $\lambda$ is a (real) eigenvalue, then there exists a corresponding spectral realization of the graph, such that the realization has the eigenic property with scale factor $\lambda$. If the graph is bipartite, take a two-coloring of its vertices; for each vertex of a chosen color, move the corresponding realized vertex to its reflection in the origin. The result is a realization with eigenic scale factor $-\lambda$, which must therefore be an eigenvalue of the graph. QED. (Note: The Truncated Octahedron, pictured above, is bipartite.)

I'd love to see the geometry of these realizations explained completely from the combinatorics of the graphs. (I'm personally trying to investigate the combinatorial conditions under which two spectral realizations may share the same vertex coordinates, as with the skeletapairs of the Truncated Octahedra realization shown, or the Dodecahedron and Great Stellated Dodecahedron, etc.) I hope you keep us posted on your progress in this area.

Not an answer, but perhaps the basis for a plan of attack ...

A consequence of the spectral theorem as it applies to the adjacency matrix of a graph $G$ is that, for every (presumably real) eigenvalue --say, with multiplicity $m$-- there exists a geometric realization, $R$, of $G$ in $\mathbb{R}^m$ such that each automorphism of $G$ induces a rigid isometry of $R$. I call these "spectral realizations" (which I discuss at length in my note "Spectral Realizations of Graphs" (PDF)). A spectral realization has this eigenic property: moving each vertex to the vector sum of its neighbors has the same effect as scaling the realization by the associated eigenvalue.

For example, these are the spectral realizations of the 15-cycle and the (skeleton of the) Truncated Octahedron (uniform polyhedron $U_8$).

Spectral Realizations of the 15-cycle http://daylateanddollarshort.com/math/pdfs/mathoverflow-spectralpolygons.png

(Whoops! Typo: Caption should read "Note that (b), (c), (e), and (h) are faithful".)

Spectral Realizations of the Truncated Octahedron http://daylateanddollarshort.com/math/pdfs/mathoverflow-spectralpolyhedra.png

(The caption seems to imply that there are other, higher-dimensional, realizations of the Truncated Octahedron; in this case, there are none. The caption is a template used for over 70 figures in my note, and I haven't gone back to edit the individual cases.)

One way to attack your problem, then, would be to attempt to reverse the implication: Use the combinatorics of the graph to prove independently that sufficiently many spectral realizations exist, "using up" all the eigen-dimensions; the associated eigenvalues must be real as they serve as scale factors for the eigenic property of these realizations.

It's not clear to me how a combinatorial approach to finding these realizations would proceed; they fall so neatly out of the spectral theorem, after all. However, I can demonstrate that sometimes there's a nice interplay between the combinatorics and the geometry; here's an example I left as a comment to an answer of another MO question:

Proposition: If $\lambda$ is a (real) eigenvalue of a bipartite graph, then so is $-\lambda$.

Proof: If $\lambda$ is a (real) eigenvalue, then there exists a corresponding spectral realization of the graph, such that the realization has the eigenic property with scale factor $\lambda$. If the graph is bipartite, take a two-coloring of its vertices; for each vertex of a chosen color, move the corresponding realized vertex to its reflection in the origin. The result is a realization with eigenic scale factor $-\lambda$, which must therefore be an eigenvalue of the graph. QED.

I'd love to see the geometry of these realizations explained completely from the combinatorics of the graphs. (I'm personally trying to investigate the combinatorial conditions under which two spectral realizations may share the same vertex coordinates, as with the skeleta of the Dodecahedron and Great Stellated Dodecahedron.) I hope you keep us posted on your progress in this area.

Not an answer, but perhaps the basis for a plan of attack ...

A consequence of the spectral theorem as it applies to the adjacency matrix of a graph $G$ is that, for every (presumably real) eigenvalue --say, with multiplicity $m$-- there exists a geometric realization, $R$, of $G$ in $\mathbb{R}^m$ such that each automorphism of $G$ induces a rigid isometry of $R$. I call these "spectral realizations" (which I discuss at length in my note "Spectral Realizations of Graphs" (PDF)). A spectral realization has this eigenic property: moving each vertex to the vector sum of its neighbors has the same effect as scaling the realization by the associated eigenvalue.

For example, these are the spectral realizations of the 15-cycle and the (skeleton of the) Truncated Octahedron (uniform polyhedron $U_8$).

Spectral Realizations of the 15-cycle http://daylateanddollarshort.com/math/pdfs/mathoverflow-spectralpolygons.png

(Whoops! Typo: Caption should read "Note that (b), (c), (e), and (h) are faithful".)

Spectral Realizations of the Truncated Octahedron http://daylateanddollarshort.com/math/pdfs/mathoverflow-spectralpolyhedra.png

(The caption seems to imply that there are other, higher-dimensional, realizations of the Truncated Octahedron; in this case, there are none. The caption is a template used for over 70 figures in my note, and I haven't gone back to edit the individual cases.)

One way to attack your problem, then, would be to attempt to reverse the implication: Use the combinatorics of the graph to prove independently that sufficiently many spectral realizations exist, "using up" all the eigen-dimensions; the associated eigenvalues must be real as they serve as scale factors for the eigenic property of these realizations.

It's not clear to me how a combinatorial approach to finding these realizations would proceed; they fall so neatly out of the spectral theorem, after all. However, I can demonstrate that sometimes there's a nice interplay between the combinatorics and the geometry; here's an example I left as a comment to an answer of another MO question:

Proposition: If $\lambda$ is a (real) eigenvalue of a bipartite graph, then so is $-\lambda$.

Proof: If $\lambda$ is a (real) eigenvalue, then there exists a corresponding spectral realization of the graph, such that the realization has the eigenic property with scale factor $\lambda$. If the graph is bipartite, take a two-coloring of its vertices; for each vertex of a chosen color, move the corresponding realized vertex to its reflection in the origin. The result is a realization with eigenic scale factor $-\lambda$, which must therefore be an eigenvalue of the graph. QED. (Note: The Truncated Octahedron, pictured above, is bipartite.)

I'd love to see the geometry of these realizations explained completely from the combinatorics of the graphs. (I'm personally trying to investigate the combinatorial conditions under which two spectral realizations may share the same vertex coordinates, as with pairs of the Truncated Octahedra realization shown, or the Dodecahedron and Great Stellated Dodecahedron, etc.) I hope you keep us posted on your progress in this area.

Source Link
Blue
Blue
  • 1.2k
  • 1
  • 9
  • 17

Not an answer, but perhaps the basis for a plan of attack ...

A consequence of the spectral theorem as it applies to the adjacency matrix of a graph $G$ is that, for every (presumably real) eigenvalue --say, with multiplicity $m$-- there exists a geometric realization, $R$, of $G$ in $\mathbb{R}^m$ such that each automorphism of $G$ induces a rigid isometry of $R$. I call these "spectral realizations" (which I discuss at length in my note "Spectral Realizations of Graphs" (PDF)). A spectral realization has this eigenic property: moving each vertex to the vector sum of its neighbors has the same effect as scaling the realization by the associated eigenvalue.

For example, these are the spectral realizations of the 15-cycle and the (skeleton of the) Truncated Octahedron (uniform polyhedron $U_8$).

Spectral Realizations of the 15-cycle http://daylateanddollarshort.com/math/pdfs/mathoverflow-spectralpolygons.png

(Whoops! Typo: Caption should read "Note that (b), (c), (e), and (h) are faithful".)

Spectral Realizations of the Truncated Octahedron http://daylateanddollarshort.com/math/pdfs/mathoverflow-spectralpolyhedra.png

(The caption seems to imply that there are other, higher-dimensional, realizations of the Truncated Octahedron; in this case, there are none. The caption is a template used for over 70 figures in my note, and I haven't gone back to edit the individual cases.)

One way to attack your problem, then, would be to attempt to reverse the implication: Use the combinatorics of the graph to prove independently that sufficiently many spectral realizations exist, "using up" all the eigen-dimensions; the associated eigenvalues must be real as they serve as scale factors for the eigenic property of these realizations.

It's not clear to me how a combinatorial approach to finding these realizations would proceed; they fall so neatly out of the spectral theorem, after all. However, I can demonstrate that sometimes there's a nice interplay between the combinatorics and the geometry; here's an example I left as a comment to an answer of another MO question:

Proposition: If $\lambda$ is a (real) eigenvalue of a bipartite graph, then so is $-\lambda$.

Proof: If $\lambda$ is a (real) eigenvalue, then there exists a corresponding spectral realization of the graph, such that the realization has the eigenic property with scale factor $\lambda$. If the graph is bipartite, take a two-coloring of its vertices; for each vertex of a chosen color, move the corresponding realized vertex to its reflection in the origin. The result is a realization with eigenic scale factor $-\lambda$, which must therefore be an eigenvalue of the graph. QED.

I'd love to see the geometry of these realizations explained completely from the combinatorics of the graphs. (I'm personally trying to investigate the combinatorial conditions under which two spectral realizations may share the same vertex coordinates, as with the skeleta of the Dodecahedron and Great Stellated Dodecahedron.) I hope you keep us posted on your progress in this area.