Expanders, Sheaves on Graphs, and Applications

点击翻译按钮获取中文摘要

Theoretical computer science has given rise to a number of important problems***that can be attacked with techniques of the subfield of mathematics known as***linear algebra. Our proposal is to use a number of related techniques in***linear algebra applied to "graph theory", to study such problems. The***connection of linear algebra to such problems is well known. Our proposal***seeks to strengthen the known techniques in linear algebra, with a view towards***their applications, to solve problems in theoretical computer science.******Such techniques can be used also to solve problems in a number of fields of***mathematics; indeed, the problems in computer science of interest to us are***related to a number of areas of mathematics and physics. In the other***direction, these related areas have research results which we can sometimes***borrow to enhance our knowledge of the parts of linear algebra and computer***science of interest to us.******Our proposed research is motived by two areas of theoretical computer science,***one known as "expander graphs", another known as "complexity theory". The***areas of linear algebra that we work with are the "eigenvalues" and "spectral***theory" of certain matrices arising in to "graph theory", and the related***notion of "sheaf theory". While sheaf theory is often viewed as a field of***algebraic topology, our interest in sheaf theory is in "sheaves of vector***spaces," which is a type of linear algebra that is enhanced by the structure of***a graph.******Our research in "expander graphs" focuses on "relative expansion," which is a***way of building larger networks from smaller ones, in a way where one can***understand expansion of the large network in terms of the smaller network and***the way the large network lies "over" the smaller one. Recently there has been***a lot of results and constructions of new networks from smaller ones. The***foundations of relative expansion began in a paper of ours from 2003, motivated***by work of Alexander Grothendieck in topology and algebraic geometry.******Our research in sheaf theory allows us to compare structures in linear algebra***that lie over the same graph; this type of sheaf theory is in its infancy. We***began to study this theory motivated by complexity theory, but have used it to***solve the Hanna Neumann Conjecture of the 1950's regarding group theory. This***sheaf theory was inspired by work of Grothendieck and his colleagues.******Hence our project exploits the fruitful connection between areas of computer***science and mathematics.