Burr–Erdős conjecture

The Burr–Erdős conjecture states that for every fixed degeneracy bound, graphs with that degeneracy have Ramsey numbers bounded by a constant times their number of vertices.

Connect

Ramsey number: The least number of vertices such that every coloring of a complete graph’s edges contains a monochromatic copy of a specified graph. The conjecture asserts a linear upper bound on this quantity for graphs of bounded degeneracy.
Paul Erdős: A Hungarian mathematician whose work shaped modern combinatorics, number theory, and probabilistic methods. Erdős formulated the sparse-graph Ramsey problem with Burr.
Graph: A mathematical structure consisting of vertices joined in pairs by edges. The conjecture concerns Ramsey numbers of finite graphs.
Ramsey-minimal graph: A graph whose Ramsey number exceeds that of every proper subgraph. Understanding extremal examples tests how sharp sparse-graph Ramsey bounds can be.
Burr–Erdős conjecture for hypergraphs: A proposed extension of the sparse-graph Ramsey bound to uniform hypergraphs. Higher-order edges raise the question of whether analogous degeneracy conditions still yield linear growth.
Graph degeneracy: The smallest integer k such that every nonempty subgraph contains a vertex of degree at most k. This sparsity measure is the fixed structural parameter in the conjecture.
Stephan A. Burr: A mathematician known for foundational work on Ramsey numbers of graphs. Burr co-formulated the conjecture with Erdős.
Subgraph: A graph formed from a subset of another graph’s vertices and a subset of its edges. Degeneracy is defined by examining every nonempty subgraph.
Tree (graph theory): A connected graph with no cycles. Trees are 1-degenerate, providing a basic family covered by the conjecture.
Hypergraph Ramsey number: The least number of vertices forcing a monochromatic copy of a specified uniform hypergraph in every coloring. Hypergraph versions test how far the conjecture’s sparse-structure principle extends.