Problem 925

Is there a constant $\delta>0$ such that, for all large $n$ , if $G$ is a graph on $n$ vertices which is not Ramsey for $K_3$ (i.e. there exists a 2-colouring of the edges of $G$ with no monochromatic triangle) then $G$ contains an independent set of size $\gg n^{1/3+\delta}$ ?

Source: erdosproblems.com/925

Graph theory
Ramsey theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The status-defining source is Theorem 3.2 of Alon and Rödl, Combinatorica 25 (2005), 125--141 (refereed; the page numbers used here are the authors' final manuscript's), in the form of the explicit lower-bound construction inside its proof (p. 7): for infinitely many $N$ , a $3$ -coloring of $K_N$ with no monochromatic triangle in the first two colors and a third color whose clique number is below $c\,N^{1/3}(\log N)^2$ , so the graph of the first two colors is $2$ -colorable without a monochromatic triangle and has independence number below $c\,N^{1/3}(\log N)^2$ , which is $o(N^{1/3+\delta})$ for every $\delta>0$ ; the answer is no. The conversion is written in the Current assessment and named there as authored; the paper never states the problem. The site's commentary credits Alon and Rödl [AlRo05] with the disproof, with the bounds $m^3/(\log m)^{4+o(1)}\ll R(3,3,m)\ll m^3\log\log m/(\log m)^2$ and Sudakov's removal of the $\log\log m$ , and so records the same resolution through the reformulation. The claim page Alon and Rödl 2005 records the theorem, its construction, the conversion and its acceptance evidence, and the frontmatter standing derives from it.

AlRo05: Alon, N. and Rödl, V., Sharp bounds for some multicolor Ramsey numbers. Combinatorica 25 (2005), no. 2, 125--141, doi:10.1007/s00493-005-0011-9 (Crossref record accessed: issue dated March 2005). The pages and statement numbers used here are those of the authors' "Final Version" manuscript (15 pages) from Alon's publication list; Theorem 3.2, p. 6; its proof with the construction, pp. 6--7; the Remark, p. 7. Library home: Alon and Rödl 2005.
Er69b: Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press (1969), 27--35. The question, p. 33. Library home: Erdős 1969 (a Rényi archive scan).
AKS80: Ajtai, M., Komlós, J. and Szemerédi, E., A note on Ramsey numbers. J. Combin. Theory Ser. A 29 (1980), no. 3, 354--360, DOI 10.1016/0097-3165(80)90030-8; Theorem 3, printed p. 358 (PDF p. 5 of the publisher's open-archive file): $R(3,x)<100x^2/\ln x$ . Library home: Ajtai and Szemerédi 1980; paged at Ajtai and Szemerédi 1980, Theorem 3. The upper half of the $k=1$ case $r(K_3,K_m)=\Theta(m^2/\log m)$ that [AlRo05]'s induction starts from, cited in the paper and taken at statement depth.
Ki95: Kim, J. H., The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$ . Random Structures Algorithms 7 (1995), 173--207. The lower half of the same $k=1$ case, cited in the paper; in the library on Problem 553's account and not read.

Problem 925

Status

Proof claims

Discussion