Erdős Problem #667

Let \(p, q \geq 1\) be fixed integers. Define \(H(n) = H(n; p, q)\) to be the largest \(m\) such that any graph on \(n\) vertices where every set of \(p\) vertices spans at least \(q\) edges must contain a complete graph on \(m\) vertices. Is \[ c(p, q) = \liminf_{n \to \infty} \frac{\log H(n)}{\log n} \] a strictly increasing function of \(q\) for \(1 \leq q \leq \binom{p-1}{2} + 1\)? A problem of Erdős, Faudree, Rousseau, and Schelp. When \(q = 1\) this corresponds exactly to the classical Ramsey problem, and hence \(\tfrac{1}{p-1} \leq c(p, 1) \leq \tfrac{2}{p+1}\) for \(p \geq 3\). It is easy to see that if \(q = \binom{p-1}{2} + 1\) then \(c(p, q) = 1\). erdosproblems.com/667 also states that Erdős, Faudree, Rousseau and Schelp showed \(c(p, \binom{p-1}{2}) \leq 1/2\). This cannot hold for all \(p\): for \(p = 6\), \(q = 10\), the complement of a \((6, 10)\)-locally dense graph is \(C_6\)-free, so Bondy–Simonovits together with \(\alpha(F) \geq n^2 / (2e(F) + n)\) gives \(c(6, 10) \geq 2/3\). That remark is therefore not formalised here.