Expanding Graphs and Balanced Separators

Submitted by admin on Thu, 03/10/2019 - 17:39
Aikaterini Niklanovits
Date of Defense
Three-member Committee
Michael C. Dracopoulos
Archontia C. Giannopoulou
Dimitrios M. Thilikos (Advisor)

A graph is an expander if it is sparse and has strong connectivity properties. Expanders are widely studied graphs, mainly due to their numerous applications in many different mathematical fields. The purpose of this thesis is to analyze the connections between expanders and other notions of graph theory, and study their substructures. Specifically, we will focus on the connection of balanced separators and expanders and provide an introduction on how the expansion of a graph is connected to the eigenvalues of its adjacency matrix. We will also study in detail the minors one can find in expanders.