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

About 7 years old · traced to

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,q∈Np,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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.