Department of Mathematics, UCSD, San Diego, CA, USA

In this talk, I will review the history of Ramsey numbers of graphs and discuss recent developments.

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

Ramsey numbers of graphs

Choongbum Lee

Department of Mathematics, UCSD, San Diego, CA, USA

Department of Mathematics, UCSD, San Diego, CA, USA

2015/09/10 Thu 4:15PM-5:15PM

The Ramsey number of a graph G is the minimum integer n for which every edge coloring of the complete graph on n vertices with two colors admits a monochromatic copy of G. It was first introduced in 1930 by Ramsey, who proved that the Ramsey number of complete graphs are finite, and applied it to a problem of formal logic. This fundamental result gave birth to the subfield of Combinatorics referred to as Ramsey theory which informally can be described as the study of problems that can be grouped under the common theme that “Every large system contains a large well-organized subsystem.”

In this talk, I will review the history of Ramsey numbers of graphs and discuss recent developments.

In this talk, I will review the history of Ramsey numbers of graphs and discuss recent developments.

Ramsey numbers of cubes versus cliques

Choongbum Lee (이중범)

Department of Mathematics, MIT, Cambridge, MA, USA

Department of Mathematics, MIT, Cambridge, MA, USA

2013/01/04 Fri 4PM-5PM

The cube graph Q_{n} is the skeleton of the n-dimensional cube. It is an n-regular graph on 2^{n} vertices. The Ramsey number r(Q_{n}, K_{s}) is the minimum N such that every graph of order N contains the cube graph Q_{n} or an independent set of order s. Burr and Erdős in 1983 asked whether the simple lower bound r(Q_{n}, K_{s}) ≥ (s-1)(2^{n} -1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.

Joint work w/ David Conlon, Jacob Fox, and Benny Sudakov

Joint work w/ David Conlon, Jacob Fox, and Benny Sudakov

Self-similarity of graphs

Choongbum Lee (이중범)

Department of Mathematics, UCLA, Los Angeles, USA

Department of Mathematics, UCLA, Los Angeles, USA

2012/7/4 Wed 4PM-5PM (Bldg. E6-1, Room 3433)

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.

Large and judicious bisections of graphs

Choongbum Lee (이중범)

Department of Mathematics, UCLA, Los Angeles, USA

Department of Mathematics, UCLA, Los Angeles, USA

2011/7/7 Thu 4PM-5PM

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-randomness of graph properties

Choongbum Lee (이중범)

Department of Mathematics, UCLA, Los Angeles, USA

Department of Mathematics, UCLA, Los Angeles, USA

2010/8/6 Fri 4PM-5PM

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