이중범

[Colloquium] Choongbum Lee (이중범), Ramsey numbers of graphs

Ramsey numbers of graphs

Choongbum Lee
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.

Tags:

Choongbum Lee (이중범), Ramsey numbers of cubes versus cliques

Ramsey numbers of cubes versus cliques

Choongbum Lee (이중범)
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ⁿ 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ⁿ -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

Tags:

이중범

Choongbum Lee (이중범), Self-similarity of graphs

Self-similarity of graphs

Choongbum Lee (이중범)
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.

Tags:

이중범

Choongbum Lee (이중범), Large and judicious bisections of graphs

Large and judicious bisections of graphs

Choongbum Lee (이중범)
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)

Tags:

이중범

Choongbum Lee (이중범), Quasi-randomness of graph properties

Quasi-randomness of graph properties

Choongbum Lee (이중범)
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).

Tags:

이중범

Choongbum Lee (이중범), Resilient pancyclicity of random graphs

Resilient pancyclicity of random graphs

Choongbum Lee (이중범)
Department of Mathematics, UCLA, Los Angeles, USA

2009/7/31 Thursday 4PM-5PM

A graph G on n vertices is pancyclic if it contains cycles of length t for all $3 \leq t \leq n$ . We prove that for any fixed $\epsilon>0$ , the random graph G(n,p) with $p(n)\gg n^{-1/2}$ asymptotically almost surely has the following resilience property. If H is a subgraph of G with maximum degree at most $(1/2 - \epsilon)np$ then G-H is pancyclic. In fact, we prove a more general result which says that if $p \gg n^{-1+1/(l-1)}$ for some integer $l \geq 3$ then for any $\epsilon>0$ , asymptotically almost surely every subgraph of G(n,p) with minimum degree greater than $(1/2+\epsilon)np$ contains cycles of length t for all $l \leq t \leq n$ . These results are tight in two ways. First, the condition on p essentially cannot be relaxed. Second, it is impossible to improve the constant 1/2 in the assumption for the minimum degree.