Lecture series on graph theory 5

Let G be a finite graph. We consider a random walk on the vertices of G of the following type. Start at a vertex $v$ .(v could be chosen randomly according to some probably distribution or could be specified in advance). Among all edges incident to v, choose one uniformly at random( i.e. if $d_G(v)=d$, each of these edges is chosen with probability 1/d)

Problem: determine the probability of being at a given vertex after a given number steps.

Let M(G) be the matrix whose rows and columns are indexed by vertices $v1,\dots,v_n$, we assume that $m{ij}$ is the $(i,j)$-entry of M(G), which satisfies the following formula

$$m_{ij}=\frac{a_{ij}}{d_i}$$

where $a{ij}$ is the number of edges between $v_i$ and $v_j$. The $m{ij}$ is probability that if one starts at $v_i$ and then the next step will be at $v_j$.

Recall: the number of k-walks from $v_i$ to $v_j$= the $(i,j)$-entry of $A(G)^k$

$\exists vie_1v{i1}e_2v{i2}\cdots e_kv_j,\ P(v_ie_1v{i1}e_2v{i2}\cdots e_kv_j)=\frac{a{ii1}}{d_i}\frac{a{i1i_2}}{d{i1}}\cdots\frac{a{i{k-1}i_j}}{d{i{k-1}}}=m{ii1}m{i1i_2}\cdots m{i_{k-1}j}$

$$\begin{aligned} P(v_i\to v_j\ in\ k\ steps)&=\sum_{k-walk\ from\ v_i\to v_j} P(v_ie_1v_{i_1}e_2v_{i_2}\cdots e_kv_j)\\ &=\sum m_{ii_1}m_{i_1i_2}\cdots m_{i_{k-1}j}=(i,j)-entry\ of\ M(G)^k \end{aligned}$$

Assume the probability to pick $vi$ is $p(v_i)$ for $i\in{1,\dots,n}$ s.t. $\sum{i=1}^n p(v_i)=1$

Let $P=[\begin{matrix}p(v_1)&p(v_2)&\cdots&p(v_n)\end{matrix}]$. Then the probability of a walk ending up at $v_i$ in k steps is

$$P(there\ is\ a\ walk\ ending\ up\ at\ v_i\ in\ k\ steps)=[PM(G)^k]_i$$

If G is k regular ( every vertex has degree k) then $M(G)=\frac{1}{d}A(G)$

Then the eigenvalue $\beta_i$ of $M(G)$ satisfies $\beta_1=\frac{1}{d}\lambda_i$ where $\lambda_i$ is an eigenvalue of G.

$$P(\exists\ a\ closed\ k-walk\ starting\ v)=\beta_1^k+\cdots+\beta_n^k=\frac{1}{d^k}(\lambda_1^k+\cdots+\lambda_n^k)$$

Weighted graphs and digraphs

Let G be a graph. A weighted graph is a graph G associated with a weight function: $w:E(G)\to\mathbb{F}$ where $\mathbb{F}$ is a field, denote by $(G,w)$. Most of the time, we consider the case that $\mathbb{F}=\mathbb{R}$.

The adjacency matrix of a weighted graph is a real symmetric matrix $A(G,w)=(a{ij}){n\times n}$ with $a_{ij}=w(v_iv_j)$, the weight of the edge of $v_iv_j$.

Let H be a subgraph of $(G,w)$. The weight of H is defined as $w(H)=\sum_{e\in E(H)}w(e)$

For example, how to find a minimum weight path between two given vertices? How to find a minimum spanning tree or how to find a cycle or walk with large weight( so-called heavy cycles or walks)

A digraph is a graph with an orientation which assigns an orientation to each edge.

An orientation edge (or arc) from $v_i$ to $v_j$ is an ordered pair of vertices , denoted by $(v_i,v_j)$ where $v_i$ is called the tail and $v_j$ is called the head of arc. $$ A(D,w)=[a_{ij}]_{n\times n}\ where\ a_{ij}=\left\{\begin{aligned}& w(v_iv_j),\quad v_i\to v_j\\ &-w(v_iv_j),\quad v_j\to v_i\\ &0,\quad otherwise\end{aligned}\right. $$ Then $A(D,w)$ is no longer symmetric but skew-symmetric:$A+A^T=O$

For a given graph G, let D be an orientation of G, $\vec{B}$ is an oriented incidence matrix

$$\vec{B}\cdot \vec{f}=\vec{b}\ where\ \vec{b}\in\mathbb{R}^{|V(G)|},\ \vec{f}\in\mathbb{R}^{|E(G)|}$$

A solution to $\vec{B}\cdot \vec{f}=\vec{b}$ is called a network flow. $\vec{b}$ is called a boundary condition.

If $\vec{b}=\vec{0},\ \vec{B}\cdot \vec{f}=\vec{0}.\qquad(*)$

A vector $\vec{f}$ satisfies $(*)$ is called a circulation or real flow if $\vec{f}\in\mathbb{R}^{|E(G)|}$.

If a solution to $(*)$ satisfies $\vec{f}\in\mathbb{Z}^{|E(G)|}$, then $\vec{f}$ is called an integer flow.

Tutte's five-flow conjecture: For a graph without bridge, it has a nowhere zero 5-flow i.e. $\exists \vec{f}\in\mathbb{Z}^{|E(G)|}$ and every component of f is not zero and absolute value of every component is at most 4. $\vec{f}=[f_1, f_2,\cdots,f_m]$ where $m=|E(G)|,\ f_i\in\{-4,-3,-2,-1,0,1,2,3,4\}$

Eigenvalues and subgraphs

Let G be a graph with n vertices, $A(G)$ be the adjacency matrix.

All n eigenvalues of $A(G)$ are real because $A(G)$ is real and symmertic

$$\lambda_1(G)\geq\lambda_2(G)\geq\cdots\geq\lambda_{\lceil \frac{n+1}{2}\rceil}\geq\lambda_{\lfloor \frac{n+1}{2}\rfloor}\geq\lambda_n(G)$$

where $\lambda{\lceil \frac{n+1}{2}\rceil},\lambda{\lfloor \frac{n+1}{2}\rfloor}$ are median eigenvalues.

The largest eigenvalues $\lambda_1(G)$ is usually called the spectral radius of G.

Proposition. Let G be an n-vertex graph and A be its adjacency matrix.Let $\lambda1\geq\cdots\geq\lambda_n$ be the eigenvalues of A
Then 1. $\lambda_1 =\max{\vec{x}\not=\vec{0}}\frac{\vec{x}^TA\vec{x}}{\vec{x}^T\vec{x}}$, 2. $\lambda_1\geq|\lambda_n|$

---

Proof

1.The eigenvalues of A (say $\vec{u}_1,\vec{u}_2,\dots,\vec{u}_n$) can be chosen as a standard orthogonal basis of $\mathbb{R}^n$.

Assume that array ($x_1,x_2,\dots,x_n$) is the coordinate of $\vec{x}$ under this basis

$$\frac{\vec{x}^TA\vec{x}}{\vec{x}^T\vec{x}}=\frac{\lambda_1x_1^2+\cdots+\lambda_nx_n^2}{x_1^2+\cdots+x_n^2}\leq\lambda_1$$

with equality holds if and only if $x_1\not= 0$ and $x_i=0$ for $i={2,\cdots,n}$, i.e. $\vec{x}$ is exactly an eigenvector of $\lambda_1$.

1. Let $\vec{v}$ be get from $\vec{u}_n$ by convert each component into its absolute value (i.e. $\vec{v}=(|\vec{u}_n(1)|,|\vec{u}_n(2)|,\cdots,|\vec{u}_n(n)|)$)

   From proof of 1. we can write $\lambda_n$ as

   $$|\lambda_n|=|\frac{\vec{u}^T_nA\vec{u}_n}{\vec{u}_n^T\vec{u}_n}|=|\vec{u}^T_nA\vec{u}_n|\leq\sum_{i,j\in[n]}A(i,j)|\vec{u}_n(i)\vec{u}_n(j)|=|\frac{\vec{v}^TA\vec{v}}{\vec{v}^T\vec{v}}|\leq\lambda_1$$

   We have used triangle inequality at the first inequality and the result of 1. at the second inequality.

---

Propsition. Let G be a graph, and $\Delta (G)$ be the maximum degree and $d(G)$ be the average degree. Then we have

$$d(G)\leq\lambda_1\leq\Delta (G)$$

---

Proof

Note that, there exist $\vec{x}\not=\vec{0}$, s.t. $A\vec{x}=\lambda\vec{x}$ where A is the adjacency matrix.

$$\lambda_1=\sup\{\vec{x}^TA\vec{x}\Big|||\vec{x}||=1\ and\ \vec{x}\in\mathbb{R}^n\}$$

Let $\vec{x}_1=\frac{1}{\sqrt{n}}[\begin{matrix}1&1&\dots&1\end{matrix}]^T$, then

$$\begin{aligned}\lambda_1&\geq \vec{x}_1^TA\vec{x}_1=\frac{1}{\sqrt{n}}[\begin{matrix}1&1&\dots&1\end{matrix}]A\frac{1}{\sqrt{n}}[\begin{matrix}1&1&\dots&1\end{matrix}]^T\\ &=\frac{1}{n}[\begin{matrix}1&1&\dots&1\end{matrix}][\begin{matrix}d(v_1)&d(v_2)&\cdots&d(v_n)\end{matrix}]^T\\ &=\frac{1}{n}\sum_{i=1}^nd(v_i)=d(G)\end{aligned}$$

For the upper bound, let $\vec{x}$ s.t. $A\vec{x}=\lambda_1\vec{x}$ where $\vec{x}=[\begin{matrix}x_1&x_2&\cdots&x_n\end{matrix}]^T$

Let $x_i$ be the largest value among all components of $\vec{x}$. Then,

$$\lambda_1 x_i=\sum_{v_iv_j\in E(G)}x_j\leq\Delta(G)x_j$$

So $\lambda_1\leq\Delta (G)$ follows.

---

Corollary Let G be a k-regular graph. Then $\lambda_1(G)=k$

A signed graph $(G,\sigma)$ is a weighted graph s.t. $\sigma:\ E(G)\to{-1,1}$

$$A(G,\sigma)=[a_{ij}]_{n\times n}\ where\ a_{ij}=\left\{\begin{aligned}&\sigma(v_iv_j),\quad v_iv_j\in E(G)\\&0,\quad otherwise\end{aligned}\right.$$

So $A(G,\sigma)$ is a symmetric real matrix.

We can assume that $\lambda_1(G,\sigma)\geq\lambda_2(G,\sigma)\geq\cdots\geq\lambda_n(G,\sigma)$, but $\lambda_1(G,\sigma)\geq|\lambda_n(G,\sigma)|$ may not hold.

Prop. Let $(G,\sigma)$ be a signed graph with maximum degree $\Delta (G)$. Then

$$|\lambda(G,\sigma)|\leq\Delta(G)\ where\ \lambda(G,\sigma)\ is\ an\ eigenvalue\ of\ G$$

---

Proof

Let $\vec{x}$ be an eigenvector of $\lambda$ s.t. $\lambda\vec{x}=A\vec{x}$.

Let $\vec{x}=[\begin{matrix}x_1&x_2&\cdots&x_n\end{matrix}]^T$ and $x_i$ has the largest absolute value among all $x_j$’s.

Then

$$|\lambda x_i|=|(A\vec{x})_i|=|\sum_{v_iv_j\in E(G)}\sigma(v_iv_j)x_j|\leq\sum_{v_iv_j\in E(G)}|x_j|\leq\Delta(G)|x_i|$$

So $|\lambda|\leq\Delta(G)$

---

Thm A graph G is bipartite $\Leftrightarrow$ its spectrum is symmetric about the origin.

(i.e. $\lambda_i$ is an eigenvalue of G $\Leftrightarrow$ $-\lambda_i$ is an eigenvalue of G)

---

Proof

$\Rightarrow$ Assume that G is bipartite.Let A be The adjacency matrix of G.

$$A=\left[\begin{matrix}O&B\\B^T&O\end{matrix}\right]\ where\ B\ is\ the\ bipartite\ adjacency\ matrix.$$

Let $\lambda$ be an eigenvalue of G with $\vec{x}=(\begin{matrix}\vec{x}_1^T&\vec{x}_2^T\end{matrix})^T$

Then

$$A\vec{x}=\left(\begin{matrix}O&B\\B^T&O\end{matrix}\right)\left(\begin{matrix}\vec{x}_1\\\vec{x}_2\end{matrix}\right)=\left(\begin{matrix}B\vec{x}_2\\B^T\vec{x}_1\end{matrix}\right)=\lambda\left(\begin{matrix}\vec{x}_1\\\vec{x}_2\end{matrix}\right)$$

Then

$$A\left(\begin{matrix}\vec{x}_1\\-\vec{x}_2\end{matrix}\right)=\left(\begin{matrix}O&B\\B^T&O\end{matrix}\right)\left(\begin{matrix}\vec{x}_1\\-\vec{x}_2\end{matrix}\right)=\left(\begin{matrix}-B\vec{x}_2\\B^T\vec{x}_1\end{matrix}\right)=-\lambda\left(\begin{matrix}\vec{x}_1\\-\vec{x}_2\end{matrix}\right)$$

So $-\lambda$ is also an eigenvalue of A.

$\Leftarrow$ Let $\lambda1\geq\cdots\geq\lambda_n$ be all eigenvalues of G.(i.e. $\lambda_i=-\lambda{n-i+1}$)</font>

For any positive integer k, the matrix $A^k$ has eigenvalues $\lambda_1^k,\lambda_2^k,\cdots,\lambda_n^k$

Because G has symmetric specturm, it follows that $\lambda_1^k+\cdots+\lambda_n^k=0$ if k is an odd integer.

$$0=\lambda_1^k+\cdots+\lambda_n^k=w_k(G)$$ $w_k(G)$ is the total number of close k-walks.

So every closed walk have an even length. Therefore G is bipartite.

---

Problem: characterize graphs which satisfy # positive eigenvalues=# negative eigenvalues