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

Self-dual codes have become one of the most active research areas in coding theory due to their rich mathematical theories. In this talk, we start with an introduction to coding theory. Then we describe some recent results on the constructions of self-dual codes over rings, and applications to lattices and network coding theory. We conclude the talk with some open problems.

The chromatic polynomial of a graph counts the number of proper colorings of the graph. We give an affirmative answer to the conjecture of Read (1968) and Welsh (1976) that the absolute values of the coefficients of the chromatic polynomial form a log-concave sequence. We define a sequence of numerical invariants of projective hypersurfaces analogous to the Milnor number of local analytic hypersurfaces. Then we show log-concavity of the sequence by answering a question of Trung and Verma on mixed multiplicities of ideals. The conjecture on the chromatic polynomial follows as a special case.