# Projects on graphs and matrices

This page includes some potential projects on graphs and matrices. Here are some textbooks and learning resources on related topics. You may obtain an electronic copy from the school library for most of them.

**Linear Algebra**
- *[Linear Algebra](https://jephianlin.github.io/LA-notebook/)* by Jim Hefferon
- *[Essence of linear algebra](https://www.youtube.com/watch?v=fNk_zzaMoSs&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab)* by 3Blue1Brown

**Graph Theory**
- *[Applied Combinatorics](https://appliedcombinatorics.org/appcomb/)* by Mitchel T. Keller and William T. Trotter
- *Graph Theory* by Reinhard Diestel

**Spectral graph theory**
- *Graphs and Matrices* by Ravindra B. Bapat
- *Spectra of Graphs* by Andries E. Brouwer and Willem H. Haemers
- *A Combinatorial Approach to Matrix Theory and Its Applications* by Richard A. Brualdi and Dragoš Cvetković
- *Laplacian Eigenvectors of Graphs: Perron--Frobenius and Faber--Krahn Type Theorems* by Türker Biyikoglu, Josef Leydold, Peter F. Stadler

**Programming**
- *[Sage Tutorial](https://doc.sagemath.org/html/en/tutorial/)*
- *[Explorations in Algebraic Graph Theory with Sage](http://buzzard.pugetsound.edu/sage-practice/)* by Chris Godsil and Robert A. Beezer.
- *[A Whirlwind Tour of Python](https://jakevdp.github.io/WhirlwindTourOfPython/)* by Jake VanderPlas
- *[Python Data Science Handbook](https://jakevdp.github.io/PythonDataScienceHandbook/)* by Jake VanderPlas

## Kirchhoff's matrix tree theorem

Let $G$ be a simple graph. A *spanning tree* of $G$ is a subgraph of $G$ that uses all vertices (spanning) and is a tree. A spanning tree can be viewed as a backbone of a graph. It is a minimal subgraph connecting all vertices. How many spanning tree are there in $G$? Surprisingly, the number is equal to $\det(L(1))$, where $L(1)$ is the matrix obtained from the Laplacian matrix $L$ of $G$ by removing its first row and first column.

- [Wikipedia: Kirchhoff's theorem](https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem)
- *Graphs and Matrices* by Ravindra B. Bapat

## Strongly regular graphs and friendship theorem

A $k$-regular graph is a graph such that each of its vertex has degree $k$. There are tons of regular graphs. What if we put more restrictions on the graph? A *strongly regular graph* with parameters $(n,k,a,c)$ is a graph such that:

* it has $n$ vertices,
* it is $k$-regular,
* it is neighter complete, nor empty,
* any two adjacent vertices have $a$ common neighbors, and
* any two non-adjacent vertices have $c$ common neighbors.

The strongly regular graphs becomes very limited. Can we find all the strongly regular graphs? It turns out that the adjacency eigenvalues can be obtained from the parameters $(n,k,a,c)$, and they provide hints on possible $(n,k,a,c)$.

- [Wikipedia: Strongly regular graph](https://en.wikipedia.org/wiki/Strongly_regular_graph)
- *Graphs and Matrices* by Ravindra B. Bapat

## Algebraic connectivity

Let $G$ be a simple graph and $L$ its Laplacian matrix. Let $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ be the eigenvalues of $L$. It is known that $\lambda_1 = 0$ for any graph. Interestingly, $\lambda_2$ reveals some information about the connectivity of $G$. For example, it is known that $\lambda_2 = 0$ if and only if $G$ is disconnected. Also, $\lambda_2 \leq \kappa(G)$, where $\kappa(G)$ is the vertex connectivity of $G$.

- *Graphs and Matrices* by Ravindra B. Bapat
- M. Fiedler, Algebraic connectivity of graphs, *Czech. Math. J.* 23 (1973) 298–305. https://doi.org/10.21136/CMJ.1973.101168.

## Characteristic edge and characteristic vertex of a tree

Let $G$ be a tree. Where is the "center" of $G$? For $P_5$, most people will pick the third vertex intuitively. For $P_4$, we may pick the second and the third vertices. How about other trees? The Laplacian eigenvector of $G$ offers a potential solution.

- *Graphs and Matrices* by Ravindra B. Bapat
- S. Kirkland, M. Neumann, B.L. Shader, Characteristic vertices of weighted trees via perron values, *Linear and Multilinear Algebra* 40 (1996) 311–325. https://doi.org/10.1080/03081089608818448.
- N. Abreu, E. Fritscher, C. Justel, S. Kirkland, On the characteristic set, centroid, and centre for a tree, *Linear and Multilinear Algebra* 65 (2017) 2046–2063. https://doi.org/10.1080/03081087.2017.1304520.
- M. Fiedler, Eigenvectors of acyclic matrices, *Czechoslovak Mathematical Journal* 25 (1975) 607–618. https://dml.cz/handle/10338.dmlcz/101356.
- M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, *Czechoslovak Mathematical Journal* 25 (1975) 619–633. https://dml.cz/handle/10338.dmlcz/101357.

## Spectral center of a tree

While the Laplacian eigenvector defines a potential center for a tree, the adjacency matrix offers another possibility, called the *spectral center*, through its largest and second largest eigenvalue.

- *Spectra of Graphs* by Andries E. Brouwer and Willem H. Haemers
- N. Abreu, E. Fritscher, C. Justel, S. Kirkland, On the characteristic set, centroid, and centre for a tree, *Linear and Multilinear Algebra* 65 (2017) 2046–2063. https://doi.org/10.1080/03081087.2017.1304520.

## Fiedler vector

Let $G$ be a graph and $L$ its Laplacian matrix. While $\lambda_2$ of $L$ is the algebraic connectivity and provides information about the connectivity of $G$, the corresponding eigenvector $\mathbf{v}_2$ is called the *Fiedler vector* and offers hints on graph partitioning.

- *Graphs and Matrices* by Ravindra B. Bapat
- M. Fiedler, Eigenvectors of acyclic matrices, *Czechoslovak Mathematical Journal* 25 (1975) 607–618. https://dml.cz/handle/10338.dmlcz/101356.
- M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, *Czechoslovak Mathematical Journal* 25 (1975) 619–633. https://dml.cz/handle/10338.dmlcz/101357.

## Courant's nodal domain theorem

Let $G$ be a graph and $L$ its Laplacian matrix. The algebraic connectivity $\lambda_2$ and the Fiedler vector $\mathbf{v}_2$ are useful for partitioning the graph into two parts. By Courant's nodal domain theorem, other eigenvectors $\mathbf{v}_k$ offers information about partitioning the graphs into $k$ parts.

- *Laplacian Eigenvectors of Graphs: Perron--Frobenius and Faber--Krahn Type Theorems* by Türker Biyikoglu, Josef Leydold, Peter F. Stadler

## Spectral embedding

How to draw a graph properly? By definition, a graph contains the vertices and the edges but not any information about the position of the vertices. Let $G$ be a simple graph. Using the spectral decomposition of the Laplacian matrix of $G$, it generates an embedding $f: V(G) \to \mathbb{R}^2$ so that one draw the graph on the plane. Such a mapping is called the *spectral embedding*, and it helps us to visualize the graph and leads to some machine learning algorithms, such as the Laplacian eigenmap and the spectral clustering.

- Y. Koren, Drawing graphs by eigenvectors: theory and practice, *Computers & Mathematics with Applications* 49 (2005) 1867–1888. https://doi.org/10.1016/j.camwa.2004.08.015.
- M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation, *Neural Computation* 15 (2003) 1373–1396. https://doi.org/10.1162/089976603321780317.
- J. Shi, J. Malik, *Normalized cuts and image segmentation*, IEEE Transactions on Pattern Analysis and Machine Intelligence 22 (2000) 888–905. https://doi.org/10.1109/34.868688.

## Resistance Distance

Let $(G,w)$ be a weighted simple graph such that $w: E(G) \rightarrow \mathbb{R}_+$ assigns a positive weight to each edge. Imagine that $G$ is a circuit such that each edge $e$ is a wire with resistance $r(e) = \frac{1}{w(e)}$. We have learned some basic rules regarding the total resistance of a series or a parallel circuits. How about some more complicated circuit? Consider two vertices $i,j\in V(G)$. Suppose the current of $1$ A flows in at $i$ and flows out from $j$. The total votage potential loss $V$ gives the total resistance by Ohm's law $R = \frac{V}{I} = V$. The weighted Laplacian matrix $L$ of $G$ governs this model and provides an efficient way to calculate all the details, including the resistance, current, and voltage.

- [Wikipedia: Series and parallel circuits](https://en.wikipedia.org/wiki/Series_and_parallel_circuits)
- *Graphs and Matrices* by Ravindra B. Bapat
all centers

## Graham and Pollak's theorem

The *distance matrix* of a graph $G$ on $n$ vertices is an $n\times n$ symmetric matrix whose $i,j$-entry is the distance on $G$ from $i$ to $j$. Naturally, the distance matrix depends on the structure of the graph. However, Graham and Pollak published a famous result that $\det(D) = (-1)^{n-1}(n-1)2^{n-2}$ for any tree on $n$ vertices, which does not depends on the structure of the tree!

- *Graphs and Matrices* by Ravindra B. Bapat
- M. Edelberg, M.R. Garey, R.L. Graham, On the distance matrix of a tree, *Discrete Mathematics* 14 (1976) 23–39. https://doi.org/10.1016/0012-365X(76)90003-0.
- W. Yan, Y.-N. Yeh, A simple proof of Graham and Pollak's theorem, *Journal of Combinatorial Theory, Series A* 113 (2006) 892–893. https://doi.org/10.1016/j.jcta.2005.07.005.

## Graphs with largest eigenvalue at most $2$

The largest adjacency eigenvalue of a graph $G$ is known as the *spectral radius* of $G$, denoted by $\rho(G)$. According to the Perron--Frobenius theorem, if $G$ is a subgraph of $H$, then $\rho(G) \leq \rho(H)$. From this point of view, graphs with $\rho(G) \leq 2$ should be some how limited. It turns out that these graphs can be chracterized is related to Dynkin diagrams.

- *Spectra of Graphs* by Andries E. Brouwer and Willem H. Haemers

## Chromatic number

The chromatic number, denoted by $\chi(G)$, is the minimum number of colors requierd to color a graph so that adjacent vertices have different colors Let $\theta_1 \geq \theta_2 \geq \cdots \geq \theta_n$ be the adjacency eigenvalues of $G$. The Wilf's theorem states that $\chi(G) \leq 1 + \theta_1$, while Hoffman's ratio bound states that $\chi(G) \geq 1 - \frac{\theta_1}{\theta_n}$. These results provide efficient bounds for the chromatic number and led to an elegant proof of the sensitivity conjecure.

- *Spectra of Graphs* by Andries E. Brouwer and Willem H. Haemers

## PageRank algorithm

When you search for a keywords, Google not only show related websites to you, but also sort them in terms of importance so that you can see the major results first. But how does Google decide one website is more important than the other? The idea is simply. Imagine you put billions of robots on the internet and let them go to links on each page randomly. Ideally, important websites are linked by more pages, so more robots will gather more there. Such an algorithm is called the PageRank algorithm.

- *Spectra of Graphs* by Andries E. Brouwer and Willem H. Haemers

## A combinatorial proof of the Cayley--Hamilton theorem

Let $A$ be a square matrix with its characteristic polynomial $p(x)$. The Cayley--Hamilton theorem states that $p(A) = O$. How do you prove it? Aside from the algebraic approach, there is an elegant combinatorial proof simply counting the numbers and showing that all summands cancels.

- *A Combinatorial Approach to Matrix Theory and Its Applications* by Richard A. Brualdi and Dragoš Cvetković