Skip to main content
MathOverflow

Return to Answer

added 1803 characters in body
Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

even laterfinal thoughts Let us start with a vector (or just specify the distinct entries) and then try to build a graph. With only 2 distinct entries the partition does need to be almost equitable. I think that it is easy to create high irregularity if some entries are 0. Here is an example cobbled up ad hoc (goals three distinct entries, none being zero. every vertex has neighbors with the other two labels, every label showing two types of vertices): Suppose that the entries are $1$,$2$,$-3$ (how many times each to be determined later). We can ignore edges between vertices with the same label. Suppose $u,v$ are two vertices labeled $1$ , that $u$ has $a$ and $b$ neighbors labeled $2$ and $-3$. Then the eigenvalue is $1(a+b)-2a+3b=-a+4b$ I'll pick $a=1$ and $b=5$ giving eigenvalue $19.$ Then $-c+4d=19$ where $c$ and $d$ are the number of edges from $v$ to vertices labelled $2$ and $-3$ I'll say that some have $c=5$ and $d=6$. Similar calculations and choices lead to this possible situation

  • $[p;1 \rightarrow 2^1,-3^5]$ meaning $p$ vertices labeled 1 each having 1 neighbor labeled 2 and 5 labeled -3
  • $[q;1 \rightarrow 2^5,-3^6]$
  • $[r;2 \rightarrow 1^3,-3^7]$
  • $[s,2 \rightarrow 1^8,-3^6]$-
  • $[t,-3 \rightarrow 1^{13},2^1]$
  • $[u,-3 \rightarrow 1^8,2^5]$ meaning $u$ vertices labelled -3 with 8 and 5 neighbors labeled 1 and 2 respectively

Now we have 6 equations in the (positive integer) variables which will need to be satisfied. Counting in two ways edges with ends labelled 1 and -3 gives $5p+6q=13t+8u$ If my calculations are correct then one possible solution is $[p,q,r,s,t,u]=[21m,4m,3m,4m,5m,8m]$ I do not think that there would be any problem (other than tedium) in assigning edges to make that work (say with m=10 or 20). At any rate, the idea is clear.

later thoughts You rephrase your question as (essentially) "what conditions on a graph are necessary for it to have at least one positive eigenvalue (for the Laplacian) with at least one eigenvector with at least one repeated entry?" I don't think that is exactly what you intended but for that question I don't expect a satisfying answer. However many conditions are sufficient.

 

even later thoughts You rephrase your question as (essentially) "what conditions on a graph are necessary for it to have at least one positive eigenvalue (for the Laplacian) with at least one eigenvector with at least one repeated entry?" I don't think that is exactly what you intended but for that question I don't expect a satisfying answer. However many conditions are sufficient.

final thoughts Let us start with a vector (or just specify the distinct entries) and then try to build a graph. With only 2 distinct entries the partition does need to be almost equitable. I think that it is easy to create high irregularity if some entries are 0. Here is an example cobbled up ad hoc (goals three distinct entries, none being zero. every vertex has neighbors with the other two labels, every label showing two types of vertices): Suppose that the entries are $1$,$2$,$-3$ (how many times each to be determined later). We can ignore edges between vertices with the same label. Suppose $u,v$ are two vertices labeled $1$ , that $u$ has $a$ and $b$ neighbors labeled $2$ and $-3$. Then the eigenvalue is $1(a+b)-2a+3b=-a+4b$ I'll pick $a=1$ and $b=5$ giving eigenvalue $19.$ Then $-c+4d=19$ where $c$ and $d$ are the number of edges from $v$ to vertices labelled $2$ and $-3$ I'll say that some have $c=5$ and $d=6$. Similar calculations and choices lead to this possible situation

  • $[p;1 \rightarrow 2^1,-3^5]$ meaning $p$ vertices labeled 1 each having 1 neighbor labeled 2 and 5 labeled -3
  • $[q;1 \rightarrow 2^5,-3^6]$
  • $[r;2 \rightarrow 1^3,-3^7]$
  • $[s,2 \rightarrow 1^8,-3^6]$-
  • $[t,-3 \rightarrow 1^{13},2^1]$
  • $[u,-3 \rightarrow 1^8,2^5]$ meaning $u$ vertices labelled -3 with 8 and 5 neighbors labeled 1 and 2 respectively

Now we have 6 equations in the (positive integer) variables which will need to be satisfied. Counting in two ways edges with ends labelled 1 and -3 gives $5p+6q=13t+8u$ If my calculations are correct then one possible solution is $[p,q,r,s,t,u]=[21m,4m,3m,4m,5m,8m]$ I do not think that there would be any problem (other than tedium) in assigning edges to make that work (say with m=10 or 20). At any rate, the idea is clear.

later thoughts You rephrase your question as (essentially) "what conditions on a graph are necessary for it to have at least one positive eigenvalue (for the Laplacian) with at least one eigenvector with at least one repeated entry?" I don't think that is exactly what you intended but for that question I don't expect a satisfying answer. However many conditions are sufficient.

 
added 1938 characters in body
Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

even later thoughts You rephrase your question as (essentially) "what conditions on a graph are necessary for it to have at least one positive eigenvalue (for the Laplacian) with at least one eigenvector with at least one repeated entry?" I don't think that is exactly what you intended but for that question I don't expect a satisfying answer. However many conditions are sufficient.

In your example of $[a,a,-a,-a,0,0,0,0]$ the corresponding graph does have the equitable partition with 6 singleton cells along with $\lbrace6,8\rbrace$ and that partition does support the eigenvector. Every vertex is adjacent to both or neither of $6,8$ so one also has the eigenvector $[0,0,0,0,0,1,0,-1]$ for $3$ (as $6$ and $8$ are not connected and have degree $3$) This means that every eigenvector for other eigenvalues does have equal entries in positions 6 and 8 (as they will be orthogonal to that one).

It turns out that $\lbrace 1,4\rbrace,\lbrace2,3,6,8\rbrace,\lbrace5\rbrace,\lbrace7\rbrace$ is almost equitable. This means that it supports $4$ eigenvalues with eigenvectors. Leaving out the edges inside each part gives a bipartite graph with those same eigenvalues and eigenvectors and a nice structure.

Any time you have an eigenvalue of multiplicity greater than 1 you can arrange for it to have an eigenvector with some repeated entry by taking the right linear combination of two independent eigenvectors. Your graph has $3$ and $\frac{7 \pm \sqrt{17}}{2}$ as eigenvalues of multiplicity $2$ along with $0$ and $4$ of multiplicity $1$.

Given your comments, your question seems to be better put as: What conditions on a partition of the vertices is necessary for it to support an eigenvector for (a positive eigenvalue of) the Laplacian? Perhaps you wish to add the condition that the eigenvector takes distinct values on distinct cells. There i don't know but I still don't expect much.

earlier I am having trouble editing my previous answer so here are later thoughts.

I am having trouble editing my previous answer so here are later thoughts.

even later thoughts You rephrase your question as (essentially) "what conditions on a graph are necessary for it to have at least one positive eigenvalue (for the Laplacian) with at least one eigenvector with at least one repeated entry?" I don't think that is exactly what you intended but for that question I don't expect a satisfying answer. However many conditions are sufficient.

In your example of $[a,a,-a,-a,0,0,0,0]$ the corresponding graph does have the equitable partition with 6 singleton cells along with $\lbrace6,8\rbrace$ and that partition does support the eigenvector. Every vertex is adjacent to both or neither of $6,8$ so one also has the eigenvector $[0,0,0,0,0,1,0,-1]$ for $3$ (as $6$ and $8$ are not connected and have degree $3$) This means that every eigenvector for other eigenvalues does have equal entries in positions 6 and 8 (as they will be orthogonal to that one).

It turns out that $\lbrace 1,4\rbrace,\lbrace2,3,6,8\rbrace,\lbrace5\rbrace,\lbrace7\rbrace$ is almost equitable. This means that it supports $4$ eigenvalues with eigenvectors. Leaving out the edges inside each part gives a bipartite graph with those same eigenvalues and eigenvectors and a nice structure.

Any time you have an eigenvalue of multiplicity greater than 1 you can arrange for it to have an eigenvector with some repeated entry by taking the right linear combination of two independent eigenvectors. Your graph has $3$ and $\frac{7 \pm \sqrt{17}}{2}$ as eigenvalues of multiplicity $2$ along with $0$ and $4$ of multiplicity $1$.

Given your comments, your question seems to be better put as: What conditions on a partition of the vertices is necessary for it to support an eigenvector for (a positive eigenvalue of) the Laplacian? Perhaps you wish to add the condition that the eigenvector takes distinct values on distinct cells. There i don't know but I still don't expect much.

earlier I am having trouble editing my previous answer so here are later thoughts.

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

I am having trouble editing my previous answer so here are later thoughts.

With regard to the Laplacian Matrix:

  • For any graph the all $1$'s vector is an eigenvector of the Laplacian matrix although the partition with one class is only equitable if the graph is regular.

  • Consider a graph and an eigenvector $v$ of its Laplacian matrix which has a healthy number of repeated values (perhaps due to an underlying equitable partition) now freely add and delete edges joining vertices with the same value. I claim that for the new graph the vector $v$ will still be an eigenvector for the same eigenvalue although the partition need not be especially nicely behaved.

  • If one has an equitable partition into $k$ parts then not only does it have an eigenvector of the form you mention but it has $k$ such eigenvectors (with multiplicity). However the same argument as above shows that you can change the graph by arbitrary changes of edges within each part and have the same eigenvectors for the same eigenvalues.

  • Consider a graph with $n$ vertices which has an eigenvalue with multiplicity $m>1$ ( say that $W$ is the space of eigenvectors for that value) then for any $p<m$ vertices the space of vectors which take the same value on those $p$ points (call it $U$) has dimension $n-p+1$ contains a subspace (the intersection of $W$ with $U$) of dimension at least $m-p$ of eigenvectors for that eigenvalue. If the $p$ chosen points do not have the same degree, the partition is not equitable.

  • start with a graph and an eigenvector for an eigenvalue $\lambda>0$. Partition the vertices into subsets (preferably, many small ones) each with sum of corresponding entries 0. Now assign to each subset a new vertex joined to all its members and getting the weight 0. The new vector is an eigenvaue for the new matrix for eigenvalue $\lambda+1.$

  • If an eigenvector has one or more $0$'s then one can hang off of them any structure of further edges and vertices which all get a value of zero and this gives an eigenvector for the new graph.

With regard to the incidence matrix: I think that my argument in the previous answer does show that a partition into $k$ parts is equitable if and only if it supports $k$ linearly independent eigenvectors.