Extreme Values of the Fiedler Vector on Trees
Let $G$ be a connected tree on $n$ vertices and let $L = D-A$ denote the Laplacian matrix on $G$. The second-smallest eigenvalue $\lambda_{2}(G) > 0$, also known as the algebraic connectivity, as well as the associated eigenvector $\phi_2$ have been of substantial interest. We investigate the question of when the maxima and minima of $\phi_2$ are assumed at the endpoints of the longest path in $G$. Our results also apply to more general graphs that `behave globally' like a tree but can exhibit more complicated local structure. The crucial new ingredient is a reproducing formula for the eigenvector $\phi_k$.
\section{Introduction}
\subsection{Introduction.} 
Let $G=(V,E)$ be a simple, undirected, connected tree on $n$ vertices $\left\{v_1, \dots, v_n\right\}$. The degree matrix $D$ is the diagonal matrix $d_{ii} = \deg(v_i)$, the adjacency matrix $A$ encodes the connections between the
vertices. The matrix
$$ L = D - A$$
is known as the Laplacian matrix of $G$. It is symmetric and has eigenvalues that we order by their size
$$ \lambda_n(G) \geq \lambda_{n-1}(G) \geq \dots \geq \lambda_{2}(G) \geq \lambda_1(G) = 0.$$
We refer to \cite{chung, davies, mohar} for an introduction to the spectral theory on graphs.
It is not difficult to see that the unique eigenvector associated to the eigenvalue $\lambda_1(G)=0$ is the vector having constant entries and that 
\begin{equation} \label{one}
 \lambda_{2}(G) = \min_{x \perp \textbf{1}} \frac{\sum_{v_i \sim_E v_j}{(x_i - x_j)^2}}{\sum_{i=1}^{n}{x_i^2}}.
 \end{equation}
This shows that $\lambda_{2}(G) > 0$ if and only if $G$ is connected. The eigenvector $\phi_2$ associated to the second smallest eigenvalue is
also known as the Fiedler vector \cite{fiedler1, fiedler2, fiedler3, gern, stone}.  The following crucial result is due to Fiedler \cite{fiedler3}.

\begin{thm}[Fiedler] The induced subgraph on $\left\{v \in V: \phi_2(v) \geq 0\right\}$ is connected.
\end{thm}

This, together with many other desirable properties, motivates the classical spectral cut whereby the sign of $\phi_2$ is used to decompose a graph. Overall, relatively little seems to be known about the actual behavior of the Fiedler vector:
\begin{quote}
However, apart from the original results from M. Fiedler, very few is known about the
Fiedler vector and its connection to topological properties of the underlying graph [...] (\cite{gern}, 2018)
\end{quote}

Simultaneously, these types of questions have become increasingly important in the framework of Graph Signal Processing, we refer to \cite{ham, irion, or, per, saito, shu, shu2, shu3} for an introduction into recent work.


\subsection{The Problem}
Let $G=(V,E)$ be a tree. Equation (\ref{one}) suggests that $\phi_2$ is the `smoothest' vector that is orthogonal to the constants, so maximum and minimum of $\phi_2$ should be attained
at the points of largest distance. This was explicitly conjectured in \cite{moo}, a counterexample was then produced by Evans \cite{evans} and is shown in Figure 1.  Maximum and minimum
are assumed far away from one another but not at the two points of maximum distance from one another. A natural question that remains is (1) to understand
the behavior of the Fiedler vector and, as discussed by Lef\`evre \cite{lef} and Gernandt \& Pade \cite{gern}, (2) to understand under which conditions such a
result might still be true.


\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}
\filldraw (0,0) circle (0.07cm);
\filldraw (1,0) circle (0.07cm);
\filldraw (2,0) circle (0.07cm);
\filldraw (3,0) circle (0.07cm);
\filldraw (4,0) circle (0.07cm);
\filldraw (5,0) circle (0.07cm);
\filldraw (6,0) circle (0.07cm);
\filldraw (6,0) circle (0.07cm);
\filldraw (7,0) circle (0.07cm);
\filldraw (8,0) circle (0.07cm);
\filldraw (9,0) circle (0.07cm);
\draw [thick] (0,0) -- (9,0);
\filldraw (3,-1) circle (0.07cm);
\filldraw (2,-2) circle (0.07cm);
\filldraw (2.2,-2) circle (0.07cm);
\filldraw (2.4,-2) circle (0.07cm);
\filldraw (2.6,-2) circle (0.07cm);
\filldraw (2.8,-2) circle (0.07cm);
\filldraw (3,-2) circle (0.07cm);
\filldraw (3.2,-2) circle (0.07cm);
\filldraw (3.4,-2) circle (0.07cm);
\filldraw (3.6,-2) circle (0.07cm);
\filldraw (3.8,-2) circle (0.07cm);
\filldraw (4,-2) circle (0.07cm);
\draw [thick] (3,0) -- (3,-1);
\draw [thick] (2,-2) -- (3,-1);
\draw [thick] (2.2,-2) -- (3,-1);
\draw [thick] (2.4,-2) -- (3,-1);
\draw [thick] (2.6,-2) -- (3,-1);
\draw [thick] (2.8,-2) -- (3,-1);
\draw [thick] (3,-2) -- (3,-1);
\draw [thick] (3.2,-2) -- (3,-1);
\draw [thick] (3.4,-2) -- (3,-1);
\draw [thick] (3.6,-2) -- (3,-1);
\draw [thick] (3.8,-2) -- (3,-1);
\draw [thick] (4,-2) -- (3,-1);
\node at (3, -2.5) {minimum assumed here};
\node at (9, -1) {maximum assumed here};
\draw [thick, ->] (9, -0.8) -- (9, -0.3);
\end{tikzpicture}
\end{center}
\caption{The `Fiedler rose' counterexample of Evans \cite{evans}.}
\end{figure}

We hope that our paper contributes to both problems and can be helpful in clarifying the situation; we also raise a number of questions.

\subsection{The Continuous Case.}
Let $\Omega \subset \mathbb{R}^2$ be a domain and consider the second smallest eigenfunction of the Laplace operator $-\Delta$ with Neumann boundary conditions, i.e. the equation
\begin{align*}
-\Delta \phi_2 &= \mu_2 \phi_2 \quad \mbox{in}~ \Omega\\
\frac{\partial \phi_2}{\partial \nu} &= 0 \quad \mbox{on}~\partial \Omega. 
\end{align*}
Rauch conjectured in 1974 that the maximum and the minimum are assumed at the boundary. This is known to fail at this level of generality \cite{b25, b4} but widely assumed to be true for convex domains $\Omega$. 
The second author \cite{stein} recently showed that if $x_1, x_2 \in \Omega$ satisfy 
$\|x_1 - x_2\| = \mbox{diam}(\Omega)$, then every maximum and minimum is
assumed within distance $c\cdot \mbox{inrad}(\Omega)$ of $x_1$ and $x_2$, where $c$ is a universal constant (which is the optimal scaling up to the value of $c$). Therefore, up to an inradius, the maximum and minimum are essentially assumed at maximum distance.


\section{Main Results}

We present two main results: the first is a representation formula for $\phi_2$ that is very useful. It allows to quickly recover some of the existing results and gives a better understanding of the behavior of $\phi_2$.
In particular, it will explain that for generic trees there is little to no reason to assume that the extrema of $\phi_2$ are assumed at vertices that are at distance $\mbox{diam}(G)$. We hope that the representation formula will also be useful in other settings. The second contribution is an explicit application of the representation formula to construct families of trees on which the desired statement indeed holds: the extrema of the Fiedler vector are assumed at vertices which are distance $\mbox{diam}(G)$ apart.



\subsection{A Representation Formula}\label{sec:game}
Let us fix $G=(V,E)$ to be a Graph on $n$ vertices.
Let $v_{s}, v_{t}$ be two arbitrary vertices. We introduce a game that results in a representation formula for any eigenvector $\phi_k$ associated to the eigenvalue $\lambda_k$.
\begin{enumerate}
\item You start with zero payoff and in the vertex $v_s$. 
\item If you find yourself in a vertex $w \neq v_t$,
\begin{enumerate}
\item add $\lambda_{k}\cdot\phi_k(w)/\mbox{deg}(w)$ to your payoff and
\item then jump to a randomly chosen neighbor of $w$.
 \end{enumerate}
 \item If you find yourself in the vertex $w = v_t$, the game ends.
\end{enumerate}
We note that the game ends in finite time almost surely.

\begin{theorem} The expected payoff of the game satisfies
$$ \mathbb{E}\left(\emph{payoff}\right) = \phi_k(v_s) - \phi_k(v_t).$$
\end{theorem}

Throughout the rest of the paper, we will only use this result for $k=2$ (since only then do we have Fiedler's theorem at our disposal).
Results of such a flavor are very easy to obtain for the random walk normalized Laplacian $A^{-1}D$ (which, by its very nature, is strongly tied to random walks). Our game adjusts for the canonical
Laplacian $L = D-A$. The game could also be interpreted as a discretized version of the Feynman-Kac formula (see e.g. \cite{taylor}).
We believe that this representation theorem has a substantial amount of explanatory power. A simple example is the following (known) Corollary: a simple form of monotonicity of the second eigenvector along paths in a tree.

\begin{corollary}[see also \cite{gern, lef}] Let $\Gamma$ be a path in the tree such that $\phi_2$ only assumes positive values on the path. If $v,w$ are two vertices on the path and $v$ is at a greater distance than $w$ from the closest vertex where $\phi_2$ is negative, then
$$ \phi_2(v) > \phi_2(w).$$
In particular,  maxima and minima are assumed in vertices with degree 1.
\end{corollary}
\begin{proof} Let $v_1$ be the vertex where $\phi_2$ is negative but where $\phi_2$ is positive for one of the neighbors. By Fiedler's theorem, that vertex is unique. Let us now assume $v_2$ and $v_3$ are vertices on a path and $v_3$ is from a greater distance from $v_1$ than $v_2$.

\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}[scale=1]
\filldraw (0,0) circle (0.06cm);
\filldraw (1,0) circle (0.06cm);
\filldraw (2,1) circle (0.06cm);
\filldraw (2,0) circle (0.06cm);
\filldraw (2,-1) circle (0.06cm);
\filldraw (3,1) circle (0.06cm);
\draw [very thick, dashed] (0,0) -- (1,0);
\draw [very thick] (1,0) -- (2,-1);
\draw [very thick] (1,0) -- (2,0);
\draw [very thick, dashed] (2,-1) -- (3,-1.5);
\draw [very thick] (1,0) -- (2,1);
\draw [very thick] (2,1) -- (3,1);
\draw [very thick, dashed] (0,0) -- (-1,0);
\draw [very thick, dashed] (2,0) -- (3,0);
\draw [very thick, dashed] (3,1) -- (4,1);
\node at (0, -0.3) {\Large $v_1$};
\node at (2, 1.3) {\Large $v_2$};
\node at (3, 1.3) {\Large $v_3$};
\end{tikzpicture}
\end{center}
\end{figure}

We use Theorem 1 and start the game in the vertex $v_3$. We then collect payoff in every run of the game and thus in expectation and therefore $\phi_2(v_3) > \phi_2(v_2)$ as desired.
\end{proof}



\subsection{How to produce counterexamples.} We now return to the original question from \cite{moo}: whether the second eigenvector assumes maximum and minimum at the endpoints of the longest path in the tree.
This was disproven by Evans \cite{evans} by means of an explicit example. The question has also been studied by \cite{gern, lef}. The purpose of this subsection is to argue that our representation formula from Theorem 1 allows to heuristically explain why, generally, there is no reason the second eigenvector should assume extreme values at the endpoints of the longest path -- it shows that Evans' counterexample is actually representative of one of the main driving forces behind localization of large values of the Fiedler vector in sub-structures. We are not making any precise claims at this point, this section tries to provide a good working heuristic that (a) allows to contruct counterexamples quite easily and (b) will underlie all our formal arguments later in the paper.\\


One of the crucial ingredients in the representation formula is the number of steps a typical random walk will need to reach another vertex: if the tree has a complicated structure (say, many vertices with large degree), then it will take a very long time for a random walk to reach a specific vertex (this principle is already embodied in Evans' counterexample \cite{evans} shown in Figure 1). Put differently, distance is not so crucial as complexity -- this immediately implies a large family of counterexamples whose type is shown in Figure 4: we consider a path graph of length $d$ and attach a tree $T$ to vertex $d/4$. We assume the tree $T$ has diameter much smaller than $d/4$ but has vertices of very large degree.


\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}
\draw [very thick] (0,0) -- (8,0);
\draw[very thick] (2.5,1.5) circle (0.6cm);
\draw [thick] (2.5,0) -- (2.5,0.9);
\node at (2.5, 1.5) {$T$};
\node at (5.5, -0.4) {path of length $d$};
\node at (2.5, -0.3) {$d/4$};
\node at (5.5, 1.5) {tree that traps random walk};
\node at (5.5, 1) {and has diameter $\ll d$};
\end{tikzpicture}
\end{center}
\caption{A generic counterexample.}
\end{figure}

The game then suggests that, if the tree has vertices of sufficiently large degree, one extremum is at the `most remote' part off the path in the tree $T$ -- in particular, one of the two extrema would not be on the path and thus not at the endpoints of the longest path in the Graph. The distance between the extrema would be
$$ d(v_{\max}, v_{\min}) \leq \frac{3d}{4} + \mbox{diam}(T) < d.$$
A sketch of the argument to show that this type of construction works is as follows. There are two cases: either the sign change of the second eigenvector happens inside $T$ or it happens on the path. If the diameter of $T$ is sufficiently small compared to $d$, known inequalities on the eigenvalue $\lambda_2$ (which we use below) suggest that the first case cannot occur. This means that the sign change happens on the path. If the value of the eigenvector in the vertex $v$ that connects to $T$ is nonzero, we can play the game with vertices starting in $T$ and ending in $v$. Corollary 1 shows that the values of the eigenfunction inside $T$ are (in absolute value) at least as big as the value in $v$. Then the game leads to a nonzero contribution for each step of the random walk that is not arbitrarily small. This means that in order to ensure large (absolute) values inside the tree, the quantity to maximize is the expected number of steps in the game -- this, in turn, can be achieved by having vertices of large degree. We emphasize that this heuristic is non-rigorous but quickly motivates the construction of many counterexamples. All the positive results in our paper can be understood as ensuring the absence of such a structure.\\




\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}[scale=0.8]
\draw [very thick] (0,0) -- (8,0);
\draw [thick] (4,0) -- (4,2);
\node at (6.5, -0.4) {path of length $d$};
\node at (4, -0.4) {$d/2$};
\node at (5.5, 1) {height $\sim d/3$};
\end{tikzpicture}
\end{center}
\caption{Another type of counterexample: extrema are assumed at the end of the long path.}
\end{figure}

To build further intuition, we quickly sketch another type of counterexample. Take a path graph of length $d$ and
add a path graph of length $d/3$ to the middle vertex. What we observe is that the eigenvector changes along the
long path, that it assumes extrema at its end and that the eigenvector is small and changes slowly on the little path in the middle.

\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}[scale=0.8]
\draw [very thick] (0,0) -- (8,0);
\draw [thick] (4,0) -- (4,2);
\node at (6.5, -0.4) {path of length $d$};
\node at (4, -0.4) {$d/2$};
\node at (5.5, 1) {height $\sim d/3$};
\draw [thick] (4,1) -- (4.2, 1.2);
\draw [thick] (4,1) -- (4-0.2, 1.2);
\draw [thick] (4,1) -- (4-0.2, 0.8);
\draw [thick] (4,1.5) -- (4.2, 1.7);
\draw [thick] (4,1.5) -- (4-0.2, 1.3);
\draw [thick] (4,0.7) -- (4.2, 0.7);
\draw [thick] (4,0.7) -- (3.8, 0.5);
\draw [thick] (4,0.7) -- (3.8, 0.7);
\end{tikzpicture}
\end{center}
\caption{Another type of counterexample: adding little trees to the path in the middle leads to a counterexample.}
\end{figure}

However, if we start adding paths of length 1 to the vertices of the short path in the middle (or short trees, even ones with bounded
diameter), then after a while the eigenvector flips and assumes an extremum in the tip of short path in the middle.
Perhaps the main contribution of our paper is a framework that clearly establishes \textit{why} this happens. The
theorems we give are one way of capturing the phenomenon but presumably there are many other possible formulations
that could be proven by formalizing the same kind of mechanism that we use here.\\

A particular consequence of these ideas is that a generic tree should not have the desired property of $\phi_2$ assuming its extrema
at the endpoints of a path of length $\mbox{diam}(G)$. We refer to numerical work done by Lef\`evre \cite{lef} showing that all trees
with $n \leq 11$ vertices do have the property but already $2\%$ of trees with $n=20$ vertices do not. Lef\`evre specifically asks
whether a typical tree on $n$ vertices does not have the property as $n$ becomes large and we also consider this to be an interesting
problem.

\subsection{An Admissible Class.}
The purpose of this section is to construct a large family of tree-like graphs for which the following statement is true: the second eigenvector of the Graph Laplacian does indeed assume maximum and minimum at the endpoints of the longest path. We assume that we are given a Graph that can be constructed by taking a path of length $\mbox{diam}(G)$ and then possibly adding to each vertex one or several attached graphs that are isolated from each other except for being connected to the path. Of course, trees have this property. 
\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}[scale=1]
\filldraw (0,0) circle (0.06cm);
\filldraw (1,0) circle (0.06cm);
\filldraw (2,0) circle (0.06cm);
\filldraw (3,0) circle (0.06cm);
\filldraw (4,0) circle (0.06cm);
\filldraw (5,0) circle (0.06cm);
\filldraw (6,0) circle (0.06cm);
\filldraw (7,0) circle (0.06cm);
\filldraw (8,0) circle (0.06cm);
\filldraw (9,0) circle (0.06cm);
\filldraw (9,0) circle (0.06cm);
\draw [very thick] (0,0) -- (4,0);
\draw [very thick, dashed] (4,0) -- (6,0);
\draw [very thick] (6,0) -- (9,0);
\node at (0, -0.5) {1};
\node at (1, -0.5) {2};
\node at (9,-0.5) {$\mbox{diam}(G)$};
\node at (5,-0.5) {$k$};
\draw [thick] (5,0) to[out=60, in=270] (5.5, 1) to[out=90, in=0] (5, 2) to[out=180, in=90] (4.5, 1) to[out=270, in=120] (5, 0);
\node at (5,1) {$G_{k,1}$};
\draw [thick] (5,0) to[out=30, in=270] (6.5,1) to[out=90, in=0] (6,2) to[out=180, in=90] (5.8, 1.5) to[out=270, in=40] (5,0);
\node at (6.1,1) {$G_{k,2}$};
\end{tikzpicture}
\end{center}
\caption{The class of admissible graphs: a long path whose attached graphs are connected to exactly one vertex on the path and do not have any connections between them.}
\end{figure}

We will now assign to each such Graph $G_{k,i}$ a natural quantity: for any vertex $v \in G_{k,i}$, we can consider a random walk started in $v$ that jumps uniformly at random to an adjacent vertex until it hits the path. We can then, for each such vertex $v$, compute the expected hitting time $\mbox{hit}(v)$ (that is: the expected number of steps in the random walk until one hits the path) and define
$$ \mbox{hit}(G_{k,i}) = \max_{v \in G_{k,i}} \mbox{hit}(v).$$
We argue that this quantity, in a certain sense, captures the essence of the underlying dynamics. We refer to \cite{xiu} for a paper where the same quantity has been used in a similar way. To get a feeling for the scaling of things, we observe that if $G_{k,i}$ is itself a path Graph, then 
\begin{equation}\label{eq:path:time}
  \mbox{hit}(G_{k,i})  \sim \mbox{diam}(G_{k,i})^2.
\end{equation}



 This classical scaling result follows easily from observing that the problem is structurally similar to a random walk on the lattice $\mathbb{Z}$ and that the standard random walk on $\mathbb{Z}$
 after $\ell$ random steps has variance $\ell$ (and thus standard deviation $\sim \sqrt{\ell}$).


\begin{theorem} Let $G$ be a graph whose longest path of length $\emph{diam}(G)$ has the following property: the graphs attached to the vertices on the path are isolated (any path from any vertex in $G_{k,i}$ to the complement goes through $k$) and each graph $G_{k,i}$ attached to vertex $k$ satisfies
\begin{enumerate}
\item the attached Graph $G_{k,i}$ does not have too many vertices
$$  |G_{k,i}|   \leq \frac{\emph{diam}(G)}{32}.$$
\item and the hitting time is not too large
$$  \emph{hit}(G_{k,i}) \leq   \frac{1}{50}  \min\left\{ k, \emph{diam}(G) - k \right\}^{2}.$$
\end{enumerate}
Then the second eigenvector of the Graph Laplacian assumes its extrema at the endpoints of the graph.
\end{theorem}
The structure of the proof in \S 3.3. exploits the heuristic developed in \S 2.2. By considering a path of length $\mbox{diam}(G)$ and then attaching another path of length $k$ to the $k-$th vertex on the long path, we see that both assumptions are optimal up to the values of the constants. We point out that it would be of interest to obtain inverse results: explicit conditions under which one of the extrema is not attained at the endpoints of the longest path.
We give one sample application of Theorem 2 to Evans' counterexample and consider what he called the Fiedler rose (see Fig. 6): let $G$ denote the Fiedler rose with $n+2$ vertices. If we start in an outermost vertex, then one step of the random walk leads to the center and the next step leads to the path with likelihood $p=1/(n+1)$. This means that the expected number of steps required until one hits the path is
\begin{align*}
\mbox{hit}(\mbox{Rose}) &= 2 \frac{1}{n+1} + 4 \frac{1}{n+1} \left(1- \frac{1}{n+1}\right) + 6 \frac{1}{n+1} \left(1- \frac{1}{n+1}\right) ^2 + \dots\\
&= \frac{2}{n+1} \sum_{k=0}^{\infty} (k+1) \left(1- \frac{1}{n+1}\right) ^k = 2n +2.
\end{align*}


\begin{figure}[h!] 
\begin{center}
\begin{tikzpicture}
\filldraw (3,0) circle (0.07cm);
\draw [thick] (0,0) -- (6,0);
\filldraw (3,-1) circle (0.07cm);
\filldraw (2,-2) circle (0.07cm);
\filldraw (2.2,-2) circle (0.07cm);
\filldraw (2.4,-2) circle (0.07cm);
\filldraw (2.6,-2) circle (0.07cm);
\node at (3,-2) {$\dots$};
\filldraw (3.4,-2) circle (0.07cm);
\filldraw (3.6,-2) circle (0.07cm);
\filldraw (3.8,-2) circle (0.07cm);
\filldraw (4,-2) circle (0.07cm);
\draw [thick] (3,0) -- (3,-1);
\draw [thick] (2,-2) -- (3,-1);
\draw [thick] (2.2,-2) -- (3,-1);
\draw [thick] (2.4,-2) -- (3,-1);
\draw [thick] (2.6,-2) -- (3,-1);
\draw [thick] (3.4,-2) -- (3,-1);
\draw [thick] (3.6,-2) -- (3,-1);
\draw [thick] (3.8,-2) -- (3,-1);
\draw [thick] (4,-2) -- (3,-1);
\node at (7, -2) {$n$ vertices here};
\draw [->] (5.7,-2) -- (4.5, -2);
\end{tikzpicture}
\end{center}
\caption{The `Fiedler rose' counterexample of Evans \cite{evans}. }
\end{figure}

This means that if we have a path graph of length $\mbox{diam}(G)$ and attach a Fiedler rose with $n$ vertices to
the middle point of the path graph, then the rose can have up to $n \leq \mbox{diam}(G)/120$ vertices without violating
the result. Much more precise asymptotics for this special case were given by Lef\`evre \cite{lef}.




\subsection{A Hitting Time Bound.} The purpose of this section is to establish bounds on hitting times under an assumption on the maximum degree. Let $T$ be a connected graph and assume that vertex $v_1$ is marked (in the setting above, $v_1$ is the vertex that lies on the long path). Evans' counterexample shows that we necessarily need to make some assumptions on the maximum degree of $T$ and we introduce
$$ \Delta  = \max_{v \in T}~ \mbox{deg}(v).$$
\begin{proposition} Let $T$ be a connected graph with maximum degree $\Delta$ and marked vertex $v_1$. The maximum expected time of a random walk started in a vertex in $T$ until it hits $v_1$ can be bounded by
$$  \emph{hit}(T) \leq c_{\Delta} e^{ c_{\Delta} \emph{diam}(T)},$$
where $c_{\Delta} > 0$ is a constant that depends only on $\Delta$.
\end{proposition}
Revisiting Theorem 2, if we only have an assumption on the maximal degree, then we are allowed to attach graphs of diameter up to at most $c_{\Delta} \sqrt{\log{\mbox{diam}(G)}}$. In light of Evans' counterexample, this estimate is perhaps not surprising (one can attach Fiedler roses on top of Fiedler roses on top of Fiedler roses etc. to the desired effect). However, we also point out that if the graphs do not have a `labyrinth-' type structure where random walkers can easily get lost (in the sense of hitting time being large), then one could attach graphs of larger diameter without violating the conditions of Theorem 2.

\subsection{Caterpillar graphs.} We conclude with a simple example: a caterpillar graph \cite{cat2, cat1} is path of length $n$ where to each vertex we may add trees of size 1 (alternatively: after removing all vertices of degree 1, a path graph remains).  Gernandt \& Pade \cite{gern} proved that the extrema of the second eigenvector are assumed at the endpoints of the longest graph and established various generalizations of this result. We give another one.

\begin{corollary} Let $G$ be a path graph of length $n$ with vertices order $1, 2, \dots, n$. Suppose we attach to the vertex $k$
an arbitrary number of paths of length at most $f(k)$, where
$$ f(k) \leq  \frac{1}{20}  \min\left\{ k, n-k\right\}^{}.$$
Then the global extrema are assumed at the endpoints of the longest path.
\end{corollary}
This Corollary follows almost immediately from Theorem 2 and the behavior of hitting times for path graphs. It is natural to conjecture that stronger results should be true, maybe even
$f(k) = \min\left\{k, n-k\right\} - 1.$

\subsection{A Hitting Time Problem.} 
An interesting question is the following: suppose $G=(V,E)$ is a connected Graph with a marked vertex $v_1$ and $h:V \rightarrow \mathbb{R}$
is a function such that $h(v)$ the expected number of steps a random walk started in $v$ takes until it hits $v_1$. What bounds (both from above and from below) can be proven
on 
$$ \mbox{hit}_{v_1}(G) = \max_{v \in V}{h(v)} ?$$
A trivial bound is 
$$ \mbox{hit}_{v_1}(G) \geq \max_{v \in V}{ d(v,v_1)}.$$
Amusingly, this might be close to optimal. Fix a degree $\Delta$ and consider the following type of Graph where each vertex has the maximal number of children ($\Delta -1$) up to a certain level. Let us then connect all the vertices in the last level to the root of the tree. The induced random walk can be regarded as a biased random walk in terms of the level and will quickly lead to the root of the tree.

\begin{figure}[h!] 
\begin{center}
\begin{tikzpicture}
\filldraw (0,0) circle (0.07cm);
\filldraw (1,1) circle (0.07cm);
\filldraw (1,0) circle (0.07cm);
\filldraw (1,-1) circle (0.07cm);
\draw [thick] (0,0) -- (1,1);
\draw [thick] (0,0) -- (1,0);
\draw [thick] (0,0) -- (1,-1);
\filldraw (2,1.3) circle (0.07cm);
\filldraw (2,1) circle (0.07cm);
\filldraw (2,0.7) circle (0.07cm);
\draw [thick] (1,1) -- (2,1.3);
\draw [thick] (1,1) -- (2,1);
\draw [thick] (1,1) -- (2,0.7);
\filldraw (2,0.3) circle (0.07cm);
\filldraw (2,0) circle (0.07cm);
\filldraw (2,-0.3) circle (0.07cm);
\filldraw (2,-1.3) circle (0.07cm);
\filldraw (2,-1) circle (0.07cm);
\filldraw (2,-0.7) circle (0.07cm);
\draw [thick] (1,0) -- (2,0.3);
\draw [thick] (1,0) -- (2,0);
\draw [thick] (1,0) -- (2,-0.3);
\draw [thick] (1,-1) -- (2,-1.3);
\draw [thick] (1,-1) -- (2,-1);
\draw [thick] (1,-1) -- (2,-0.7);
\foreach \x in {0,...,12}
{
\filldraw (4,1.5-\x/4) circle (0.07cm);
};
\node at (3,0) {$\dots$};
\end{tikzpicture}
\end{center}
\caption{An example with an induced drift on the random walk.}
\end{figure}
A simple question is the following: what sort of hitting time bounds are possible and how do they depend on the graph. For example, if $G$ is a tree, then we have
$ \mbox{hit}_{v_1}(G) \gtrsim \mbox{diam}(G)^2$. What other results are possible?



\section{Proofs}
\subsection{Proof of Theorem 1}
\begin{proof}
 Recall that $L \phi_2 = \lambda_2 \phi_2$ or
$$ (D-A) \phi_2 = \lambda_2 \phi_2.$$
Evaluating this equation in a single vertex means that
$$ \phi_2(v_1) = \frac{\lambda_2 \phi_2(v_1)}{\mbox{deg}(v)} + \frac{1}{\mbox{deg}(v_1)} \sum_{w \sim_{E} v}{ \phi_2(w)}.$$
This can be interpreted as one step of the game: you add $\lambda_2 \phi_2(v_1)/\mbox{deg}(v_1)$ to your account and then jump to a random neighbor (`random' because we properly normalized the sum) and evaluate the function there. We now iteratively apply this identity to every term involving $\phi_2$ except for those involving $\phi_2(v_2)$ which we keep. 
The arising terms can be bijectively mapped to the random walks in the game.
\end{proof}


\subsection{Some Preliminary Considerations}

Before embarking on the proof of Theorem 2, we recall several helpful statements.  A result of McKay \cite{mohar2} states that
$$ \lambda_2 \geq \frac{4}{|V| \cdot \mbox{diam}(G)}.$$
We also know, from the variational characterization
$$ \lambda_{2}(G) = \min_{x \perp \textbf{1}} \frac{\sum_{v_i \sim_E v_j}{(x_i - x_j)^2}}{\sum_{i=1}^{n}{x_i^2}},$$
 that the eigenvalue decreases if the Graph is enlarged. Since the Graph contains a path of length $\mbox{diam}(G)$, we can use the
second eigenvalue of the path graph as an upper bound. It is known (see e.g. \cite{chung}) that
$$ \lambda_2(P_n)= 2 \left( 1 - \cos{\left( \frac{\pi}{n} \right)} \right) \leq \frac{10}{n^2}$$
and therefore

\begin{equation}\label{eq:eig2bound}
  \lambda_2(G) \leq \frac{10}{\mbox{diam}(G)^2}.
  \end{equation}
McKay's bound shows that this upper bound using only the diameter is optimal up to constants. These facts are well known (see e.g. \cite{mohar2, mohar}).
We also observe that $\phi_2$ changes sign. This means that for every vertex $v$, we can estimate the size of $v$ by summing over a path $\pi$ from $v$
to the nearest vertex where $\phi_2$ is negative. For a normalized eigenvector $\phi_2$, this shows that
\begin{align*}
 \max_{v \in V}{ \phi_2(v)} &\leq \sum_{(i,j) \in \pi}{ | \phi_2(i) - \phi_2(j)|} \\
 &\leq \left( \sum_{(i,j) \in \pi}{ | \phi_2(i) - \phi_2(j)|^2}\right)^{1/2} \left( \mbox{length of}~\pi\right)^{1/2}\\
 &\leq \left( \sum_{(i,j) \in E}{ | \phi_2(i) - \phi_2(j)|^2}\right)^{1/2} \mbox{diam}(G)^{1/2}\\
 &\leq \lambda_2^{1/2} \mbox{diam}(G)^{1/2}\\
  &\leq \left( \frac{10}{\mbox{diam}(G)^2}\right)^{1/2} \mbox{diam}(G)^{1/2} \leq \frac{4}{\mbox{diam}(G)^{1/2}},
\end{align*}
where the second line uses the Cauchy--Schwarz inequality, the fourth line uses equation (\ref{one}) and the fifth line uses equation (\ref{eq:eig2bound}).
Since this holds for every vertex, we have 
\begin{equation}\label{eq:linf}
  \| \phi_2\|_{\ell^{\infty}} \leq \frac{4}{\mbox{diam}(G)^{1/2}}.
  \end{equation}
The normalization in $\ell^2$ of  $\phi_2$ implies by the H\"{o}lder inequality that
$$ 1 = \sum_{v \in V}{\phi_2(v)^2} \leq \| \phi\|_{\ell^{\infty}} \| \phi\|_{\ell^1} $$
and therefore, by equation (\ref{eq:linf}):
$$ \|\phi\|_{\ell^1} \geq \frac{\mbox{diam}(G)^{1/2}}{4}.$$
Moreover, $\phi$ has mean value 0 and therefore the positive part and the negative part cancel out and therefore
\begin{equation}\label{eq:maxphi}
  \sum_{v \in V}{ \max\left\{ \phi_2(v), 0 \right\}} \geq \frac{\mbox{diam}(G)^{1/2}}{8}.
\end{equation}


It is known that the expected hitting time of a path graph $P_k$ of length $k$ is 
\begin{equation}\label{eq:blum}
  \mbox{hit}(P_k) = (k-1)^2.
\end{equation}
For a proof, see \cite{blum}.

\subsection{Proof of Theorem 2}
\begin{proof}
The proof decuples into two parts: first, we show that the sign change of the second eigenfunction occurs somewhere on the long path and not within any attached Graph $G_{k, i}$ (see Fig. 5). The second part of the proof makes use of the Game Interpretation. We start by assuming that $\phi_2$ is the $\ell^2-$normalized eigenvector associated to the smallest nontrivial eigenvalue $\lambda_2 > 0$.
We now assume that the statement is false and that the sign change occurs somewhere inside the Graph $G_{k,i}$. In particular, appealing to Fiedler's theorem, the eigenvector has the same sign everywhere on the long path which we can assume without loss of generality to be negative.\\

{\bf Part 1:}
The argument is rather simple and exploits the bounds derived in \S 3.2. Let us assume that $\phi_2$ changes sign in $G_{k,i}$. Then, by Fiedler's theorem, all the positive values are attained inside $G_{k,i}$.
Then, however, by Equation (\ref{eq:maxphi}), we have 
\begin{align*}
 \frac{\mbox{diam}(G)^{1/2}}{8} &\leq \sum_{v \in V}{ \max\left\{ \phi_2(v), 0 \right\}}\\
 &\leq \sum_{v \in G_{k,i}}{ \max\left\{ \phi_2(v), 0 \right\}} \\
 &\leq |G_{k,i}| \|\phi_2\|_{\ell^{\infty}} \leq \frac{4 |G_{k,i}|}{\mbox{diam}(G)^{1/2}}
\end{align*}
and thus
$$ |G_{k,i}| \geq \frac{\mbox{diam}(G)}{32}$$
which is a contradiction to the assumption (1) in the Theorem.\\


{\bf Part 2:} It remains to show that the maxima occur at the endpoints of the path under the assumption that there is a sign change on the long path. Let us
assume that this is not the case and that, without loss of generality, the maximum is assumed in $G_{k,1}$.
Since there is exactly one sign change along the long path, one of the endpoints of the long path also
has a positive value; since we have not specified anything about the value of $k$, we can assume without loss of generality that
$\phi_2(1)$ is positive (see Fig. \ref{fig:thm2part2}). By Fiedler's theorem, we have that $\phi_2(k)$ is nonnegative and so are
$\phi_2(2), \dots, \phi_2(k-1)$ and the values in all the attached graphs.\\



\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}
\filldraw (0,0) circle (0.06cm);
\filldraw (1,0) circle (0.06cm);
\filldraw (2,0) circle (0.06cm);
\filldraw (3,0) circle (0.06cm);
\filldraw (4,0) circle (0.06cm);
\filldraw (5,0) circle (0.06cm);
\filldraw (6,0) circle (0.06cm);
\filldraw (7,0) circle (0.06cm);
\filldraw (8,0) circle (0.06cm);
\filldraw (9,0) circle (0.06cm);
\filldraw (9,0) circle (0.06cm);
\draw [very thick] (0,0) -- (4,0);
\draw [very thick, dashed] (4,0) -- (6,0);
\draw [very thick] (6,0) -- (9,0);
\node at (0, -0.5) {1};
\node at (1, -0.5) {2};
\node at (9,-0.5) {$\mbox{diam}(G)$};
\node at (5,-0.5) {$k$};
\draw [thick] (5,0) to[out=60, in=270] (5.5, 1) to[out=90, in=0] (5, 2) to[out=180, in=90] (4.5, 1) to[out=270, in=120] (5, 0);
\node at (5,1) {$G_{k,1}$};
\draw [thick] (5,0) to[out=30, in=270] (6.5,1) to[out=90, in=0] (6,2) to[out=180, in=90] (5.8, 1.5) to[out=270, in=40] (5,0);
\node at (6.1,1) {$G_{k,2}$};
\node at (0,1) {positive here};
\draw [->] (0,0.8) -- (0,0.2);
\node at (2.2,2.1) {maximum here};
\draw [->] (3.4, 2) -- (4,1.8);
\end{tikzpicture}
\end{center}
\caption{Setup of part 2 of the proof }\label{fig:thm2part2}
\end{figure}
 


We now play the game twice: first to obtain an upper bound on the maximum of $\phi_2$ (under the assumption 
that this maximum is assumed in $G_{k,1}$) and then to obtain a lower bound on $\phi_2(1)$. The game in Section \ref{sec:game}
implies that
\begin{align}\label{eq:thm2:gamegraph}
\max_{j } \phi_2(j) - \phi_2(k) &= \mathbb{E} ~\mbox{payoff}\\
 &\leq  \lambda_{2} \cdot  \left(\max_{j} \phi_2(j) \right)  \cdot \mbox{hit}(G_{k,1})
\end{align}
where $k$ is the vertex on the path where $G_{k,1}$ is connected to the path.

Recall that, by Equation (\ref{eq:eig2bound}), $\lambda_2(G) \leq 10 \cdot \mbox{diam}(G)^{-2}$ and, by assumption 2 of the Theorem,
$$ \mbox{hit}(G_{k,1}) \leq \frac{\mbox{diam}(G)^2}{20}.$$
These imply that
\begin{equation} \label{eq:thm2:lambdahit}
  \lambda_2(G)\cdot \mbox{hit}(G_{k,1})  \leq \frac{1}{2}
  \end{equation}

By Equation (\ref{eq:thm2:gamegraph}),
\begin{align} \label{eq:thm2:upperphi}
\max_{j } \phi_2(j)  &\leq \frac{\phi(k)}{1 - \lambda_2 \cdot \mbox{hit}(G_{k,1})  },
\end{align}
with a positive denominator by Equation (\ref{eq:thm2:lambdahit}).
This implies that $\phi_2(k) > 0$.

We now start the game of  Section \ref{sec:game} in the vertex 1 and obtain
$$  \phi_2(1) - \phi_2(k) = \mathbb{E}~ \mbox{payoff}.$$
It remains to understand the game. We jump around randomly and add
$$ \lambda_2 \frac{\phi_2(v)}{\mbox{deg}(v)} \qquad \mbox{at every step.}$$
Suppose we are on the path and $\mbox{deg}(v) \geq 3$. This means that there
are graphs $G_{v,\cdot}$ attached and since there is a chance of going into these graphs
which we will show increasees the expected payoff. We will obtain a lower bound on the
expected number of times we encounter the vertex $1<v<k$ before going towards
the next one on the path. We have encountered this type of computation before when
computing hitting times for the Fielder rose. Introducing
$$ p = \frac{\mbox{deg}(v) - 2}{\mbox{deg}(v)}$$
 we can bound
\begin{align*}
\mathbb{E}~\mbox{\# encounter} &\geq 1(1-p) + 2 p (1-p) + 3 p^2 (1-p) + \dots \\
&= \sum_{q=1}^{\infty}{ q (1-p) p^{q-1}} = \frac{1}{1-p} = \frac{\mbox{deg}(v)}{2}.
\end{align*}
This means that in expectation, a visit to a vertex along the path would contribute at least
$\phi_2(v) \mbox{deg}(v) / 2\mbox{deg}(v) =  \phi_2(v)/2$ before we continue to the
next vertex on the path.
For comparison, if $\mbox{deg}(v)=2$, so that the vertex is not connected to any additional graph,
the vertex  contributes $\phi_2(v)/2$ to the game and in the next step we move to one of the two vertices attached.
Corollary 1 yields
$$\lambda_2 \phi_2(v) \geq \lambda_2 \phi_2(k).$$
Abbreviating the maximum hitting time on a path graph by $\mbox{hit}(P_k)$, we
have
$$  \phi_2(1) - \phi_2(k) \geq \frac{1}{2} \lambda_2\cdot \phi_2(k) \cdot \mbox{hit}(P_k),$$
and thus the lower bound
\begin{equation}\label{eq:thm2:lower}
\phi_2(1)  \geq \phi_2(k) \left( 1+\frac{1}{2} \lambda_2  \cdot \mbox{hit}(P_k) \right).
\end{equation}



Putting together Equations (\ref{eq:thm2:upperphi}) and (\ref{eq:thm2:lower}) and the assumption of part 2 of this proof, we have 
\begin{equation}
\phi_2(k) \left( 1+\frac{1}{2} \lambda_2  \cdot \mbox{hit}(P_k) \right) \leq \phi_2(1) < \max_{j} \phi_2(j) \leq \frac{\phi_2(k)}{1 - \lambda_2 \cdot \mbox{hit}(G_{k,1})  }
  \end{equation}
and since we observed that $\phi_2(k) > 0$,
\begin{equation}
\left( 1+\frac{1}{2} \lambda_2  \cdot \mbox{hit}(P_k) \right) \leq  \frac{1}{1 - \lambda_2 \cdot \mbox{hit}(G_{k,1})  }.
  \end{equation}

In other words, since the denominator is positive,
\begin{equation}
 1+\frac{1}{2} \lambda_2  \cdot \mbox{hit}(P_k) - \lambda_2 \cdot \mbox{hit}(G_{k,1}) - \frac{1}{2} \lambda_2^2 \cdot \mbox{hit}(G_{k,1})  \cdot \mbox{hit}(P_k) \leq  1 ,
  \end{equation}
and therefore
\begin{equation}
 \mbox{hit}(G_{k,1}) \geq     \frac{\mbox{hit}(P_k)}{2}    - \frac{\lambda_2  \cdot \mbox{hit}(P_k) \mbox{hit}(G_{k,1})} {2} .
  \end{equation}


By Equation (\ref{eq:eig2bound}) and Equation (\ref{eq:blum}),
\begin{equation}
 \lambda_2  \cdot \frac{\mbox{hit}(P_k)}{2} \leq 5.
  \end{equation}

Therefore,
\begin{equation}
 \mbox{hit}(G_{k,1}) \geq     \frac{\mbox{hit}(P_k)}{2}     - 5 \cdot \mbox{hit}(G_{k,1}) .
  \end{equation}
Thus,
\begin{equation}
 \mbox{hit}(G_{k,1}) \geq   \frac{  \mbox{hit}(P_k)}{12}.
  \end{equation}

Using the hitting time bound (\ref{eq:blum}) and the second assumption of Theorem 2,
\begin{equation}
\frac{k^2}{50} \geq \mbox{hit}(G_{k,1}) \geq   \frac{  \mbox{hit}(P_k)}{12} = \frac{(k-1)^2}{12},
  \end{equation}
wWhich is a contradiction. 



\end{proof}


\subsection{Proof of the Proposition.} 
\begin{proof}
  We give a simple estimate that does not yield the sharp constant (for which we refer to Aldous \& Fill \cite{aldous}). Wherever we are, there is always at least one adjacent vertices that decreases the distance to the marked vertex (because the Graph is connected). If we start anywhere, then the likelihood of going $\mbox{diam}(T)$ number of times into a direction that decreases the distances to the marked vertex is at least
$$p = \Delta^{-\mbox{ \tiny diam}(T)}.$$
This is not very likely, the expected number of runs until this happens is
\begin{align*}
\mbox{E}~\mbox{number of runs} &\leq \mbox{diam}(T) \left( p + 2 (1-p) p + 3 (1-p)^2 p + \dots\right) \\
&= \mbox{diam}(T) \sum_{k=1}^{\infty}{ p (1-p)^{k-1} k} = \mbox{diam}(T) p^{-1} \\
&= \mbox{diam}(T) \Delta^{\mbox{\tiny diam}(T)}.
\end{align*}
This, however, establishes the desired result. 
\end{proof}




2019-12-19T02:04:28.000
1912
1912.08327
en
https://arxiv.org/abs/1912.08327
Let $G$ be a connected tree on $n$ vertices and let $L = D-A$ denote the Laplacian matrix on $G$. The second-smallest eigenvalue $\lambda_{2}(G) > 0$, also known as the algebraic connectivity, as well as the associated eigenvector $\phi_2$ have been of substantial interest. We investigate the question of when the maxima and minima of $\phi_2$ are assumed at the endpoints of the longest path in $G$. Our results also apply to more general graphs that `behave globally' like a tree but can exhibit more complicated local structure. The crucial new ingredient is a reproducing formula for the eigenvector $\phi_k$.
Combinatorics (math.CO); Discrete Mathematics (cs.DM); Spectral Theory (math.SP)
Extreme Values of the Fiedler Vector on Trees
Qwen/Qwen-72B
1. YES
2. YES