Rutgers Discrete Mathematics Seminar

Title: The Smallest Eigenvalues of some Hamming and Johnson Graphs

Speaker: Sebastian Cioaba, U. Delaware

Date: Monday, April 30, 2018 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


The smallest eigenvalue of a graph is closely related to other graph parameters such as the independence number, the chromatic number or the max-cut. In this talk, I will describe some of the connections between the smallest eigenvalue and the max-cut of a graph that have motivated various researchers such as Karloff, Alon, Sudakov, Van Dam, Sotirov to investigate the smallest eigenvalue of Hamming and Johnson graphs. I will outline our proofs of a 2016 conjecture by Van Dam and Sotirov on the smallest eigenvalue of (distance-j) Hamming graphs and a 1999 conjecture by Karloff on the smallest eigenvalue of (distance-j) Johnson graphs and mention some open problems. This is joint work with Andries Brouwer, Ferdinand Ihringer and Matt McGinnis.