Is the spectrum a fingerprint of a graph?

01 October 2018 → 30 September 2020
Regional and community funding: Special Research Fund
Research disciplines
  • Natural sciences
    • Analysis not elsewhere classified
    • Computer science
    • General mathematics
    • History and foundations not elsewhere classified
    • Other mathematical sciences not elsewhere classified
fingerprint graph
Project description

In 1966, Kac asked whether one can hear the shape of a drum, that is, weather two drums made of the same material can produce the same sound but have different shapes. He modeled the shape of the drum by a graph. Then the sound of that drum is characterized by the eigenvalues (spectrum) of the graph. Kac’s analogous question for graphs was posted by Günthard and Primas: can we hear the shape of a graph? Or equivalently: Is the spectrum a fingerprint of a graph? This question is the main focus of this project; since for almost all graphs the answer is still unknown. I propose to study under what conditions is a graph determined by its spectrum. This gives rise to difficult but important problems that are also useful in areas such as computer science, chemistry, and molecular biology. In these areas, complex structures are often modeled as graphs. However, the size of such structures is often very large and analyzing them by brute force is not feasible. The challenge is to use a small number of parameters (eigenvalues) for efficiently obtain relevant information about these complex structures.