Abstract :

One of the natural representation of a graph is using its adjacency matrix. A lot of interesting graph theoretic properties can be better understood by studying the underlying matrix and its linear algebraic properties. We will introduce at least one such connection, i.e., the connection between second largest eigen value of the adjacency matrix and a graph theoretic parameter ``called expansion''. We will also see how to exploit these connections between algebraic / combinatorial parameters with some illustrative proofs and algorithms. As we are just starting off the seminar series the talk would be placed at an introductory level.