## Choongbum Lee proved the Burr-Erdős conjecture

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

Ramsey’s famous theorem asserts that if $H$ is a complete graph on $m$ vertices then $R(H)$ is finite.   Ir follows that $R(H)$ is finite for every graph $H$ and understanding the dependence of $R(H)$ on $H$ 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 $d$-degenerate if it can be reduced to the empty graph by successively deleting vertices of degree at most $d$. 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 $d$, there exists a constant $c = c(d)$ such that every $d$-degenerate graph $H$ on $n$ vertices satisfies $r(H)\le cn.$  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!

This entry was posted in Combinatorics, Updates and tagged , . Bookmark the permalink.

### 2 Responses to Choongbum Lee proved the Burr-Erdős conjecture

1. Frank Vega says:

Dear Professor,

I have found a new complexity class that I called “equivalent-P” and I have showed it has a close relation with the P versus NP Problem. I have been making a paper that explain my ideas, and in the meantime, I decided to share them as a preprint in the web.

Here, I show you the abstract of the paper (so you can capture the idea):

“The P versus NP problem is one of the most important and unsolved problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by Kurt Gödel to John von Neumann in 1956. However, the precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in a seminal paper. We consider a new complexity class, called equivalent-P, which has a close relation with this problem. The class equivalent-P has those languages that contain ordered pairs of instances, where each one belongs to a specific problem in P, such that the two instances share a same solution, that is, the same certificate. We demonstrate that equivalent-P = NP and equivalent-P = P. In this way, we find the solution of P versus NP problem, that is, P = NP.”

In this preprint, I shall show that there is an NP-complete problem in equivalent-P and a P-complete problem in equivalent-P. Moreover, I shall show the complexity class equivalent-P is closed under reductions. Since P and NP are also closed under reductions, then we can conclude that P = NP.

https://hal.archives-ouvertes.fr/hal-01161668/document

Kind regards,
Frank.

2. Manuel says:

“In this preprint, I shall show that there is an NP-complete problem in equivalent-P and a P-complete problem in equivalent-P. Moreover, I shall show the complexity class equivalent-P is closed under reductions. Since P and NP are also closed under reductions, then we can conclude that P = NP.”

This does not make much sense: To summarize your text, you argue that there is some complexity class X (that you call equivalent-P) with the following three properties:
* X is closed under polynomial time reductions
* X contains an NP-complete problem
* X contains a P-complete problem

But also simply setting X=NP would yield such a class. I do not see how these three properties lead you to the conclusion P=NP.