0
$\begingroup$

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$.

Improve this question
$\endgroup$
5
  • $\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
    Commented Jan 5, 2021 at 2:02
  • $\begingroup$ Try the graph with two vertices and no edges. It has one eigenvalue of multiplicity 2. $\endgroup$
    – markvs
    Commented Jan 5, 2021 at 2:16
  • $\begingroup$ @dodd I restricted the question to connected graphs now. $\endgroup$
    – M. Winter
    Commented Jan 5, 2021 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
    Commented Jan 5, 2021 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
    Commented Jan 5, 2021 at 10:30

1 Answer 1

Reset to default
0
$\begingroup$

I found a counter-example.

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

$\quad\quad$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .