Choongbum Lee proved the Burr-Erdős conjecture

Let be a graph. The Ramsey number is the smallest such that whenever you color the edges of the complete graph with vertices with two colors blue and red, you can either find a blue copy or a red copy of .

Ramsey’s famous theorem asserts that if is a complete graph on vertices then is finite.   Ir follows that is finite for every graph and understanding the dependence of on is a very important question. Of course there are very basic extensions: to many colors, to different requirements for different colors, and to hypergraphs.

A graph is -degenerate if it can be reduced to the empty graph by successively deleting vertices of degree at most . Thus, trees are 1-degenerate (and 1-degenerate graphs are forests), and planar graphs are 5-degenerate. For graphs to be degenerate is equivalent to the condition that the number of edges is at most linear times the number of vertices uniformly for all subgraphs.

In 1973, Burr and Erdős  conjectured that that for every natural number , there exists a constant such that every -degenerate graph on vertices satisfies  This is a very different behavior than that of complete graphs where the dependence on the number of vertices is exponential. In 1983 Chvátal, Rödl, Szemerédi, and Trotter proved the conjecture when the maximum degree is bounded. Over the years further restricted cases of the conjectures were proved some weaker estimates were demonstrated. These developments were instrumental in the developments of some very basic tools in extremal and probabilistic combinatorics. Lee’s paper Ramsey numbers of degenerate graphs proved the conjecture!