Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Just to build on the answer which Chris gave, one can replace two disjoint copies $K_3$ with two disjoint copies of any graph $G$ (which is not bipartite, just to keep things simple). Let the vertices of $G$ be numbered $0,1,\cdots,v-1.$ Now make two graphs $G_1$ (not bipartite) and $G_2$ (bipartite) with vertex sets $0,1,\cdots,2v-1$ and matrices $A_1$ and $A_2$. For each edge $(i,j)$ of $G$ add edges $(i,j)$ and $(i+v,j+v)$ to $G_1$ and also edges $(i,j+v)$ and $(i+v,j)$ to $G_2.$ With this numbering we have $A_1^2=A_2^2$ so even knowing the exact matrix $A^2$ does not tell you the eigenvalues of $A$.

If the largest eigenvalue of $A^2$ is $\alpha$ with multiplicity $m$ then $A$ has eigenvalue $+\sqrt{\alpha}$ with multiplicity at least $\frac{m}2.$

If we do not allow loops then we do know that the sum (with multiplicities) of the eigenvalues is $0$.

Here are a couple of explicit variations of the example above which easily generalize (in case you don't want disconnected graphs or don't want a purely bipartite graph). If numbered correctly, they also preserve the $A_1^2=A_2^2$ feature (or $A-1^2=A_2^2=A_3^2$$A_1^2=A_2^2=A_3^2$ in the second.)

  • Add a seventh vertex connected to each of the six others. Then the eigenvalues are $[1+\sqrt{7},1-\sqrt{7},2,-1,-1,-1,-1]$ for two copies of $K_3$ but $[1+\sqrt{7},1-\sqrt{7},-2,1,1,-1,-1]$ for $K_6$

  • Here are three different graphs each with $12$ vertices and every one of the first $6$ connected to every one of the second $6$: For the first and second sets of $6$ vertices put in edges to make two copies of $K_3$ in each OR $K_6$ in each OR $K_6$ for one and two copies of $K_3$ for the other. Then the eigenvalues are $[ 8,-4,2,2,-1^{8}]$ OR $[8,-4,-2,-2,1^4,-1^4 ]$ OR $[8,-4,2,-2,1^4,-1^4]$

Even this second example can be further generalized to give huge sets of graphs all with distinct spectrums but all having the same $A^2$: Take any graph you like, say $H$ with $w$ vertices, Make (lots of) new graphs with $2vw$ vertices by replacing some vertices by $G_1$ from above and others by $G_2$. Replace each edge of $H$ by $(2v)^2$ edges constituting all possible edges between corresponding copies of $G_i$.

Just to build on the answer which Chris gave, one can replace two disjoint copies $K_3$ with two disjoint copies of any graph $G$ (which is not bipartite, just to keep things simple). Let the vertices of $G$ be numbered $0,1,\cdots,v-1.$ Now make two graphs $G_1$ (not bipartite) and $G_2$ (bipartite) with vertex sets $0,1,\cdots,2v-1$ and matrices $A_1$ and $A_2$. For each edge $(i,j)$ of $G$ add edges $(i,j)$ and $(i+v,j+v)$ to $G_1$ and also edges $(i,j+v)$ and $(i+v,j)$ to $G_2.$ With this numbering we have $A_1^2=A_2^2$ so even knowing the exact matrix $A^2$ does not tell you the eigenvalues of $A$.

If the largest eigenvalue of $A^2$ is $\alpha$ with multiplicity $m$ then $A$ has eigenvalue $+\sqrt{\alpha}$ with multiplicity at least $\frac{m}2.$

If we do not allow loops then we do know that the sum (with multiplicities) of the eigenvalues is $0$.

Here are a couple of explicit variations of the example above which easily generalize (in case you don't want disconnected graphs or don't want a purely bipartite graph). If numbered correctly, they also preserve the $A_1^2=A_2^2$ feature (or $A-1^2=A_2^2=A_3^2$ in the second.)

  • Add a seventh vertex connected to each of the six others. Then the eigenvalues are $[1+\sqrt{7},1-\sqrt{7},2,-1,-1,-1,-1]$ for two copies of $K_3$ but $[1+\sqrt{7},1-\sqrt{7},-2,1,1,-1,-1]$ for $K_6$

  • Here are three different graphs each with $12$ vertices and every one of the first $6$ connected to every one of the second $6$: For the first and second sets of $6$ vertices put in edges to make two copies of $K_3$ in each OR $K_6$ in each OR $K_6$ for one and two copies of $K_3$ for the other. Then the eigenvalues are $[ 8,-4,2,2,-1^{8}]$ OR $[8,-4,-2,-2,1^4,-1^4 ]$ OR $[8,-4,2,-2,1^4,-1^4]$

Even this second example can be further generalized to give huge sets of graphs all with distinct spectrums but all having the same $A^2$: Take any graph you like, say $H$ with $w$ vertices, Make (lots of) new graphs with $2vw$ vertices by replacing some vertices by $G_1$ from above and others by $G_2$. Replace each edge of $H$ by $(2v)^2$ edges constituting all possible edges between corresponding copies of $G_i$.

Just to build on the answer which Chris gave, one can replace two disjoint copies $K_3$ with two disjoint copies of any graph $G$ (which is not bipartite, just to keep things simple). Let the vertices of $G$ be numbered $0,1,\cdots,v-1.$ Now make two graphs $G_1$ (not bipartite) and $G_2$ (bipartite) with vertex sets $0,1,\cdots,2v-1$ and matrices $A_1$ and $A_2$. For each edge $(i,j)$ of $G$ add edges $(i,j)$ and $(i+v,j+v)$ to $G_1$ and also edges $(i,j+v)$ and $(i+v,j)$ to $G_2.$ With this numbering we have $A_1^2=A_2^2$ so even knowing the exact matrix $A^2$ does not tell you the eigenvalues of $A$.

If the largest eigenvalue of $A^2$ is $\alpha$ with multiplicity $m$ then $A$ has eigenvalue $+\sqrt{\alpha}$ with multiplicity at least $\frac{m}2.$

If we do not allow loops then we do know that the sum (with multiplicities) of the eigenvalues is $0$.

Here are a couple of explicit variations of the example above which easily generalize (in case you don't want disconnected graphs or don't want a purely bipartite graph). If numbered correctly, they also preserve the $A_1^2=A_2^2$ feature (or $A_1^2=A_2^2=A_3^2$ in the second.)

  • Add a seventh vertex connected to each of the six others. Then the eigenvalues are $[1+\sqrt{7},1-\sqrt{7},2,-1,-1,-1,-1]$ for two copies of $K_3$ but $[1+\sqrt{7},1-\sqrt{7},-2,1,1,-1,-1]$ for $K_6$

  • Here are three different graphs each with $12$ vertices and every one of the first $6$ connected to every one of the second $6$: For the first and second sets of $6$ vertices put in edges to make two copies of $K_3$ in each OR $K_6$ in each OR $K_6$ for one and two copies of $K_3$ for the other. Then the eigenvalues are $[ 8,-4,2,2,-1^{8}]$ OR $[8,-4,-2,-2,1^4,-1^4 ]$ OR $[8,-4,2,-2,1^4,-1^4]$

Even this second example can be further generalized to give huge sets of graphs all with distinct spectrums but all having the same $A^2$: Take any graph you like, say $H$ with $w$ vertices, Make (lots of) new graphs with $2vw$ vertices by replacing some vertices by $G_1$ from above and others by $G_2$. Replace each edge of $H$ by $(2v)^2$ edges constituting all possible edges between corresponding copies of $G_i$.

Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Just to build on the answer which Chris gave, one can replace two disjoint copies $K_3$ with two disjoint copies of any graph $G$ (which is not bipartite, just to keep things simple). Let the vertices of $G$ be numbered $0,1,\cdots,v-1.$ Now make two graphs $G_1$ (not bipartite) and $G_2$ (bipartite) with vertex sets $0,1,\cdots,2v-1$ and matrices $A_1$ and $A_2$. For each edge $(i,j)$ of $G$ add edges $(i,j)$ and $(i+v,j+v)$ to $G_1$ and also edges $(i,j+v)$ and $(i+v,j)$ to $G_2.$ With this numbering we have $A_1^2=A_2^2$ so even knowing the exact matrix $A^2$ does not tell you the eigenvalues of $A$.

If the largest eigenvalue of $A^2$ is $\alpha$ with multiplicity $m$ then $A$ has eigenvalue $+\sqrt{\alpha}$ with multiplicity at least $\frac{m}2.$

If we do not allow loops then we do know that the sum (with multiplicities) of the eigenvalues is $0$.

Here are a couple of explicit variations of the example above which easily generalize (in case you don't want disconnected graphs or don't want a purely bipartite graph). If numbered correctly, they also preserve the $A_1^2=A_2^2$ feature (or $A-1^2=A_2^2=A_3^2$ in the second.)

  • Add a seventh vertex connected to each of the six others. Then the eigenvalues are $[1+\sqrt{7},1-\sqrt{7},2,-1,-1,-1,-1]$ for two copies of $K_3$ but $[1+\sqrt{7},1-\sqrt{7},-2,1,1,-1,-1]$ for $K_6$

  • Here are three different graphs each with $12$ vertices and every one of the first $6$ connected to every one of the second $6$: For the first and second sets of $6$ vertices put in edges to make two copies of $K_3$ in each OR $K_6$ in each OR $K_6$ for one and two copies of $K_3$ for the other. Then the eigenvalues are $[ 8,-4,2,2,-1^{8}]$ OR $[8,-4,-2,-2,1^4,-1^4 ]$ OR $[8,-4,2,-2,1^4,-1^4]$

Even this second example can be further generalized to give huge sets of graphs all with distinct spectrums but all having the same $A^2$: Take any graph you like, say $H$ with $w$ vertices, Make (lots of) new graphs with $2vw$ vertices by replacing some vertices by $G_1$ from above and others by $G_2$. Replace each edge of $H$ by $(2v)^2$ edges constituting all possible edges between corresponding copies of $G_i$.