Erdős Problem #545

declared status 'open'. Formalized: no. Let $G$ be a graph with $m$ edges and no isolated vertices. Is the Ramsey number $R(G)$ maximised when $G$ is 'as complete as possible'? That is, if $m=\binom{n}{2}+t$ edges with $0\leq t<n$ then is$$R(G)\leq R(H),$$where $H$ is the graph formed by connecting a new vertex to $t$ of the vertices of $K_n$? Current best: (This is true, and was proved by Sudakov [Su11].) LouisD in the comments has noted this fails for small $m$ (in particular for $2\leq m\leq 5$ and $7\leq m\leq 9$). Prize: no. OEIS: A059442. Tags: graph theory, ramsey theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.