Professor Ionin to Speak Friday Feb. 10

Title:

Binary Representations of Regular Graphs

Abstract:

A spherical representation of a graph Γ in a metric space M is an injective map from the vertex set of Γ to a sphere in M; it is assumed that there exist d₁ < d₂ such that the distance between the images of any two distinct vertices is equal to d1 if the vertices are adjacent and it is equal to or d₂ otherwise.


A particular case of M = H_n, the binary Hamming space of (0,1) strings of length n, sometimes yields a useful information about the graph Γ. The least n, for which such a representation is possible, is the binary spherical representation number of Γ, or bsr(Γ). I will show that if Γ is a connected regular graph, then bsr(Γ) ≥ |Γ| − m where m is the multiplicity of the least eigenvalue of Γ. The case of equality gives a characterization of an important class of strongly regular graphs that has been avoiding a good characterization for 60+ years.