---

Claim. A. Dudek and D. Mubayi, On generalized Ramsey numbers for 3-uniform hypergraphs, J. Graph Theory 76 (2014), no. 3, 217--223, doi:10.1002/jgt.21760 (published online 21 August 2013, the date this page carries; arXiv:1309.4518, v1 of 18 September 2013). Their introduction (p. 2 of the arXiv text) proves, for every $s\ge3$, the lower bound $f_{s,s+1}(n)=\Omega((n\log n/\log\log n)^{1/2})$ for the Erdős–Rogers function of graphs: if a $K_{s+1}$-free graph on $n$ vertices has a vertex of degree at least $(n\log n/\log\log n)^{1/2}$, its neighborhood is $K_s$-free; otherwise Shearer's independence bound gives an independent set of that order. At $s=3$ this is $f(n)\ge c\sqrt{n\log n/\log\log n}$ for large $n$, for the function of Problem 620. The site's commentary attributes the lower bound to Shearer's results and prints the weaker form of equation (1) of Mubayi and Verstraete, who credit the observation to Dudek and Mubayi; Gishboliner, Janzer and Sudakov credit it to this paper as well. The deduction is written out on the library's result page for Shearer's corollary.

Covers. The lower bound $f(n)=\Omega(\sqrt{n\log n/\log\log n})$. Not covered: the upper bound and the order of $f(n)$.

Depends on. Shearer's Corollary 1, the independence bound the argument applies.

Acceptance. refereed: Journal of Graph Theory (published online 21 August 2013); Shearer's input appeared in Random Structures Algorithms 7 (1995). The site labels the problem OPEN, so its commentary is not acceptance.