Prof. Cioaba receives NSA Young Investigator Grant

Prof. Sebastian Cioaba has been awarded a Young Investigator grant from the National Security Agency, for his project entitled "Problems in Algebraic and Extremal Graph Theory".

Graph theory is the main tool for investigating large information networks including the web graph, social or biological networks and is useful in many applications such as network design, web-page ranking or routing network trac. The size of such networks is often very large (ranging from hundreds of thousands to billions of nodes) and analyzing their structure by brute force is not feasible. The challenge is to use a small number of parameters who capture the shape of the network. Spectral graph theory (the study of eigenvalues of graphs) provides important algebraic tools for studying structural properties of graphs and has connections to other areas such as expander graphs, computer science, ranking, network design and error-correcting codes. Eigenvalue interlacing gives information about substructures in networks. In this project, Prof. Cioaba is using algebraic, combinatorial and geometric techniques to investigate the structure of minimum (non-local) disconnecting sets of nodes in networks, to determine the expansion properties of graphs constructed from certain linear systems of equations and to study the decomposition of (hyper)graphs into minimum number of cuts or bicliques.