Let $G=(V,E)$ be a connected (finite simple) graph with vertex set $V=\{1,...,n\}$ and let $\theta_2\in\Bbb R$ be the second-largest eigenvalue of its adjacency matrix. I wonder about the following question:

Fix an edge $ij\in E$.

Suppose that there are $\theta_2$-eigenvectors $u_i,u_j\in\mathrm{Eig}_G(\theta_2)\subseteq\Bbb R^n$ so that the largest component of $u_i$ is the $i$-th component, and the largest component of $u_j$ is the $j$-th component.

Question: Is there an eigenvector $u_{ij}\in\mathrm{Eig}_G(\theta_2)\subseteq\Bbb R^n$ with exactly two identical largest components, namely, the $i$-th component and the $j$-th component?

I think (but I do not know) that if it is possible at all, then one can choose $u_{ij}=\alpha u_i + \beta u_j$ as a convex combination.

If you are familiar with the term eigenpolytope, then this can be formulated as follows: if $i$ and $j$ are embedded as vertices of the $\theta_2$-eigenpolytope, then is $ij\in E$ embedded as an edge of the eigenpolytope?

The choice of the second-largest eigenvalue is important: it is not generally true for any other eigenvalue (except, trivially, for the largest eigenvalue $\theta_1$, or any other eigenvalue of multiplicity 1). In contrast, I have not found a single counterexample for $\theta_2$. It has been proven in special cases, e.g. for distance-regular graphs. It is easy to construct counter-examples if one allows edge-weights on $G$.

  • $\begingroup$ @dodd Correct me if I am wrong, but I think this follows from the Theorem of Perron-Frobenius, at least for connected graphs. If it makes a difference, I should restrict my question to connected graphs, but I do not think so. $\endgroup$
    – M. Winter
    Jan 5 at 2:02
  • $\begingroup$ Try the graph with two vertices and no edges. It has one eigenvalue of multiplicity 2. $\endgroup$
    – markvs
    Jan 5 at 2:16
  • $\begingroup$ @dodd I restricted the question to connected graphs now. $\endgroup$
    – M. Winter
    Jan 5 at 2:18
  • $\begingroup$ @dodd This subspace is not just any subspace, but it is a very special eigenspace of an irreducible symmetric 01-matrix, and I ask for the existence of $u_{ij}$ only if the $(i,j)$-entry of that matrix is one. I consider the formulation in terms of graphs more natural than just talking about this matrix (and I do not see how this can be reasonably formulated just in terms of subspaces). Of course, I am happy with an answer in any language, whether graphs, matrices, subspaces, etc. $\endgroup$
    – M. Winter
    Jan 5 at 2:38
  • $\begingroup$ @dodd For an arbitrary subspace there is no meaning in "an edge $ij\in E$". But you could consider the smallest eigenvalue (that is, the corresponding eigenspace) of the 5-cycle graph. Then the $u_i$ exist for all vertices, but $u_{ij}$ exists for no edge. $\endgroup$
    – M. Winter
    Jan 5 at 10:30

I found a counter-example.

Consider the edge-graph of the dodecahedron, but add in a pentagram in each of its 12 faces.


It turns out that this exact figure depicts the spectral embedding of this graph to the second-largest eigenvalue $\theta_2$, and we see that some of its edges are not embedded in edges of the rsulting polytope, but merely in its faces.

So, for example, if $ij\in E$ are choose note as an edge of the dodecahedron, but as an edge of a pentagram, then the $\smash{u_i,u_j\in\mathrm{Eig}_G(\theta_2)}$ exist, but $u_{ij}$ does not.


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.