Erdős–Hajnal polynomial Ramsey-number conjecture for hereditary classes

From papers

Let XX be a proper hereditary class of graphs, meaning that XX is not the class of all graphs. For natural numbers pp and qq, let RX(p,q)R_X(p,q) be the least integer nn such that every graph in XX with at least nn vertices has either a clique of size pp or an independent set of size qq.

Erdős–Hajnal conjecture. There are constants AA and kk such that

RX(p,q)A(p+q)kR_X(p,q)\leq A(p+q)^k

for every p,qNp,q\in\mathbb{N}; equivalently, Ramsey numbers grow at most polynomially in XX.

This is the paper’s formulation of the Erdős–Hajnal conjecture. The supplied text gives no resolution status.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Bogdan Alecu, Aistis Atminas, Vadim Lozin and Viktor Zamaraev, “Graph classes with linear Ramsey numbers”, arXiv:1910.12109 (2020).

Solutions 0

No solutions have been posted yet.