Are the eigenvectors of vertex transitive graphs bounded

Question

For a connected and regular graph $G$ with degree $ d $ at each vertex and adjacency matrix $A$, the normalized Laplacian of $G$ is defined as $L = I-\frac{1}{d}M$. Let $\psi$ be an eigenvector of $L$ with $ \sum_{v \in G } \psi(v) \psi(v) = |V(G)| $. Clearly, this implies that $\| \psi \|_\infty = \max_{v \in V(G)}|\psi(v)| < \sqrt{|V(G)|}$. If $G$ is vertex transitive, in addition to being regular, is something stronger true, i.e. is there some constant ( C ) such that $ \| \psi \|_\infty < C $ for any such vertex transitive graph $G$?

Answer 1

Let $X$ be the graph of an $n\times n$ Latin square. The vertices of $X$ are the $n^2$ positions in the square, two positions are adjacenct if they are in the same row, or in the same column, or contain the same entry. This graph is regular with valency $3n-3$, in fact it is strongly regular and so it is known that its eigenvalues are $3n-3$, $n-3$ and $-3$. If your Latin square is the addition table for $\mathbb{Z}_n$, the graph is vertex transitive.

Since the graph is regular, its adjacency matrix has the same eigenvectors as its normalized Laplacian, so I work with the adjacency matrix.

The vector that takes the value $1$ on the $(1,1)$-position, $-1/(n-1)$ on the neighbours of this position and $2/(n-1)(n-2)$ on the rest is an eigenvector with eigenvalue $-3$. The squared norm of this vector is $$ 1 + \frac{3n-3}{(n-1)^2} +\frac{4(n-1)(n-2)}{(n-1)^2(n-2)^2} = 1 +\frac{3n-6}{(n-1)(n-2)} +\frac{4}{(n-1)(n-2)} = \frac{n^2}{(n-1)(n-2)}. $$ So under your normalization the largest entry of the vector is $\sqrt{(n-1)(n-2)}$. This shows your bound cannot be improved.

Answer 2

I am not sure why a property such as vertex transitive may result in such a constant, perhaps you can explain your intuition. My suggestion here does not require such an assumption but may be helpful.

I believe the matrix $M$ is somehow related to the adjacency matrix, so I will assume it is simply $A$. Notice that, the all ones vector, which is an eigenvector of $L$ with eigenvalue zero fits the above description.

Let $\phi$ be the eigenvector corresponding to the first non-zero eigenvalue of $L$. It is orthogonal to the all ones vector and thus the sum of its entries equal to one. This vector is known as the Fiedler vector and it has the nice property that it partition the graph into roughly two equal partitions (entry wise, it will be +1s over one partition and -1s over the other). My intuition is that

$ || \phi ||_{\infty} < \sqrt{|S|} $.

where $S$ is the size of the partition. If this is true, then I don't see a reason why this argument can't be generalised to higher harmonics (i.e. higher eigenvectors of $L$).