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!

### Like this:

Like Loading...

*Related*

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.

You can read more on:

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

Kind regards,

Frank.

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

Pingback: Greatest Hits 2015-2022, Part I | Combinatorics and more