KAIST Discrete Math Seminar

An old problem raised independently by Jacobson and Schönheim asks to determine the maximum s for which every graph with m edges contains a pair of edge-disjoint isomorphic subgraphs with s edges. We determine this maximum up to a constant factor and show that every m-edge graph contains a pair of edge-disjoint isomorphic subgraphs with at least c (m log m)2/3 edges for some absolute constant c, and find graphs where this estimate is off only by a multiplicative constant. Our results improve bounds of Erdős, Pach, and Pyber from 1987.
Joint work with Po-Shen Loh and Benny Sudakov.

It is very well known that every graph on n vertices and m edges admits a bipartition of size at least m/2. This bound can be improved to m/2 + (n-1)/4 for connected graphs, and m/2 + n/6 for graphs without isolated vertices, as proved by Edwards, and Erdős, Gyárfás, and Kohayakawa, respectively. A bisection of a graph is a bipartition in which the size of the two parts differ by at most 1. We prove that graphs with maximum degree o(n) in fact contain a bisection which asymptotically achieves the above bounds. These results follow from a more general theorem, which can also be used to answer several questions and conjectures of Bollobás and Scott on judicious bisections of graphs.
Joint work with Po-Shen Loh (CMU) and Benny Sudakov (UCLA)

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