KAIST Discrete Math Seminar

Quasi-random graphs can be informally described as graphs whose edge distribution closely resembles that of a random graph. They have been a subject of intensive study during the last two decades and have seen numerous applications both in Combinatorics and Computer Science.

Starting with the work of Thomason and Chung, Graham, and Wilson, there have been many works which established the equivalence of various properties of graphs to quasi-randomness. In this talk, I will give a survey on this topic, and provide a new condition which guarantees quasi-randomness. This result answers an open question raised independently by Janson, and Shapira and Yuster.

Joint work with Hao Huang (UCLA).