Erdős–Burr conjecture

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, the Erdős–Burr conjecture is a problem concerning the Ramsey number of sparse graphs. The conjecture is named after Paul Erdős and Stefan Burr, and is one of many conjectures named after Erdős; it states that the Ramsey number of graphs in any sparse family of graphs should grow linearly in the number of vertices of the graph.

In 2015, a proof of the conjecture was announced by Choongbum Lee.[1]


If G is an undirected graph, then the degeneracy of G is the minimum number p such that every subgraph of G contains a vertex of degree p or smaller. A graph with degeneracy p is called p-degenerate. Equivalently, a p-degenerate graph is a graph that can be reduced to the empty graph by repeatedly removing a vertex of degree p or smaller.

It follows from Ramsey's theorem that for any graph G there exists a least integer , the Ramsey number of G, such that any complete graph on at least vertices whose edges are coloured red or blue contains a monochromatic copy of G. For instance, the Ramsey number of a triangle is 6: no matter how the edges of a complete graph on six vertices are colored red or blue, there is always either a red triangle or a blue triangle.

The conjecture[edit]

In 1973, Paul Erdős and Stefan Burr made the following conjecture:

For every integer p there exists a constant cp so that any p-degenerate graph G on n vertices has Ramsey number at most cp n.

That is, if an n-vertex graph G is p-degenerate, then a monochromatic copy of G should exist in every two-edge-colored complete graph on cp n vertices.

Known results[edit]

Although a proof of full conjecture has not been published, it has been settled in some special cases. It was proven for bounded-degree graphs by Chvátal et al. (1983); their proof led to a very high value of cp, and improvements to this constant were made by Eaton (1998) and Graham, Rödl & Ruciński (2000). More generally, the conjecture is known to be true for p-arrangeable graphs, which includes graphs with bounded maximum degree, planar graphs and graphs that do not contain a subdivision of Kp.[2] It is also known for subdivided graphs, graphs in which no two adjacent vertices have degree greater than two.[3]

For arbitrary graphs, the Ramsey number is known to be bounded by a function that grows only slightly superlinearly. Specifically, Fox & Sudakov (2009) showed that there exists a constant cp such that, for any p-degenerate n-vertex graph G,