Algebraic Graph Theory Seminar - Ferdinand Ihringer

Title: Pseuodrandom Cliquefree Graphs, Finite Geometry, and Spectra

Abstract:

A regular graph is called optimally pseudorandom if its second largest eigenvalue in absolute value is, up to a constant factor, as small as possible. Determining the largest degree of an optimally pseudorandom graph without a clique of size s is a well-known open problem in extremal graph theory. There many applications related to this question. In particular, if one improves existing construction for pseudorandom cliquefree graphs, then one also improves the best known lower bounds on off-diagonal Ramsey numbers. In this talk, we will discuss the best known constructions for optimally pseudorandom clique-free graphs as well as the spectra of better constructions (if they exist).