Isomorphism of graphs with bounded eigenvalue multiplicity

By László Babai, D. Grigoryev, David M. Mount. 1982

Subfields: Graph Learning, Evaluation & Benchmarks

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Graph Learning

1. Sergei Evdokimov
2. Ilia N. Ponomarenko
3. B. Douglas

In Evaluation & Benchmarks

1. B. Douglas
2. Terence Tao

Citations in the corpus

• The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, background): “ent GI algorithms do exist for several restricted classes of graphs, such as trees [13], planar graphs [20] and graphs with certain bounded parameters, including valence [22], eigenvalue multiplicity [5] and genus [26]. The GI problem has several additional, relevant properties. It is generally easy”
• Random matrices: tail bounds for gaps between eigenvalues (2015, background): “Even proving that δmin > 0 (in other words the random matrix has simple spectrum) with high probability in the discrete case is already a highly non-trivial problem, first raised by Babai in the 1980s (motivated by his study of the isomorphism problem [5]).”
• Isomorphism of Coloured Graphs with Slowly Increasing Multiplicity of Jordan Blocks (1995, background): “There exist polynomial-time algorithms for graphs with bounded degree [10] and for graphs with bounded eigenvalue multiplicity [1].”
• Mechanism Design via Differential Privacy (2007, unknown): “In this case, Babai, Grigoriev and Mount [4] showed how to test isomorphism in polynomial time.”