Problem 911

Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges that is Ramsey for $G$ .

Is there a function $f$ such that $f(x)/x\to \infty$ as $x\to \infty$ such that, for all large $C$ , if $G$ is a graph with $n$ vertices and $e\geq Cn$ edges then

\hat{R}(G) > f(C) e?

Source: erdosproblems.com/911

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. No source read states a bound of this kind for all graphs of given density, and no proof or disproof, preprint or proof claim was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

Er82e: Erdős, P., Some of my favourite problems which recently have been solved. Proceedings of the International Mathematical Conference (Singapore, 1981), North-Holland Math. Stud. 74, North-Holland, Amsterdam (1982), 59--79; the "last minute" additions, printed p. 78. Library home: Erdős 1982.
EFRS78b: Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., The size Ramsey number. Period. Math. Hungar. 9 (1978), 145--161. The definition, p. 146; Theorem 6 (Erdős et al. 1978), p. 154 (the $K_{m,n}$ bounds cited under What is known). Library home: Erdős et al. 1978. Context only: the definition and the $K_{m,n}$ example.

Problem 911

Status

Proof claims

Discussion