[KAIST Discrete Math Seminar] 8/6 FRI 4PM (Choongbum Lee, Quasi-randomness of graph properties)

[Sang-il Oum]

***** KAIST Discrete Math Seminar *****

DATE: August 6, Friday

TIME: 4PM-5PM

PLACE: E6-1, ROOM 1409

SPEAKER: Choongbum Lee (이중범), UCLA

TITLE: Quasi-randomness of graph properties

http://mathsci.kaist.ac.kr/~sangil/seminar/entry/20100806/

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).