It's all in the Graphs

Mathematicians from the Einstein Institute of Mathematics used expander graphs to go back and forth between computer science and pure mathematics - and discovered new ways to enrich each field


Computer scientists rely heavily on pure mathematics for their research and applications. But there’s one particular field which has been raising special interest in recent years: the field of expander graphs.

Prof. Alex Lubotzky lecturing on his ERC
project "EXPANDERS"

Expander graphs, which were identified only in the early 1970s, are a family of sparse graphs that possess highly connective properties (in layman terms, they resemble a large and well-connected neural network). Their construction is a fundamental mathematical challenge, and they’ve been used mainly in computer science as a basis for networks of communication, code correction and data organization (among other things). However, pure mathematicians have also shown great interest in them, once they understood their importance as a fundamental mathematical concept, and realised their great potential.

The Einstein Institute of Mathematics at the Hebrew University has been at the forefront of expander graphs research. The university team, headed by Professor Alex Lubotzky, has already discovered a number of applications for both computer science and pure mathematics, and is continuously working on building a bridge between the two.

In computer science, the researchers' work has turned into basic building blocks for a number of applications, including the creation of newly symmetric error-correcting codes. Simultaneously, the graphs research allowed them to answer several problems in group theory, in number theory and in geometry. This method of solutions is quite surprising because the problems, ostensibly, have nothing to do with expander graphs.