Erdos–Burr conjecture
Encyclopedia
In mathematics
, the Erdős–Burr conjecture is an unsolved 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.
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.
and Stefan Burr
made the following conjecture:
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.
s and graphs that do not contain a subdivision of Kp. It is also known for subdivided graphs, graphs in which no two adjacent vertices have degree greater than two.
For arbitrary graphs, the Ramsey number is known to be bounded by a function that grows only slightly superlinearly. Specifically, showed that there exists a constant cp such that, for any p-degenerate n-vertex graph G,
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Erdős–Burr conjecture is an unsolved problem concerning the Ramsey number of sparse graphs. The conjecture is named after Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Stefan Burr
Stefan Burr
Stefan Andrus Burr is a mathematician and computer scientist. He is currently a professor of computer science at The City College of New York.Burr received his Ph.D...
, and is one of many conjectures named after Erdős
Erdos conjecture
The prolific mathematician Paul Erdős and his various collaborators made many famous mathematical conjectures, over a wide field of subjects.Some of these are the following:* The Cameron–Erdős conjecture on sum-free sets of integers, proved by Ben Green....
; it states that the Ramsey number of graphs in any sparse family of graphs should grow linearly in the number of vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
of the graph.
Definitions
If G is an undirected graph, then the degeneracyDegeneracy (graph theory)
In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate...
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
Ramsey's theorem
In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph, one will find monochromatic complete subgraphs...
that for any graph G there exists a least integer
, the Ramsey number of G, such that any complete graphComplete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
on at least
verticesVertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
whose edges
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
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
In 1973, Paul ErdősPaul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Stefan Burr
Stefan Burr
Stefan Andrus Burr is a mathematician and computer scientist. He is currently a professor of computer science at The City College of New York.Burr received his Ph.D...
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
Although the full conjecture has not been proven, it has been settled in some special cases. It was proven for bounded-degree graphs by ; their proof led to a very high value of cp, and improvements to this constant were made by and . More generally, the conjecture is known to be true for p-arrangeable graphs, which includes graphs with bounded maximum degree, planar graphPlanar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s and graphs that do not contain a subdivision of Kp. It is also known for subdivided graphs, graphs in which no two adjacent vertices have degree greater than two.
For arbitrary graphs, the Ramsey number is known to be bounded by a function that grows only slightly superlinearly. Specifically, showed that there exists a constant cp such that, for any p-degenerate n-vertex graph G,