Ramsey numbers involving large dense graphs and bipartite Turán numbers (Q1405120): Difference between revisions

The authors develop lower and upper bounds for Ramsey numbers and extend their results to related Turán numbers. In particular, let \(\delta>0\), \(\alpha\geq 0\), let \(F\) be a graph with \(m\) vertices and \(e(F)\) edges, and let \(G\) be a large dense graph with \(n\) vertices and at least \(e(G)=\frac{(\delta-o(1))n^2}{(\log n)^{\alpha}}\) edges as \(n\rightarrow\infty\). Then, using probabilistic arguments, it is shown that the Ramsey number \[ r(F,G) \geq (c-o(1)) \left( \frac{n}{(\log n)^{\alpha+1}} \right)^{\frac{(e(F)-1)}{(m-2)}}. \] This result contains the lower bound for \(r(K_m,K_n)\) of \textit{J. Spencer} [Discrete Math. 20, 69-76 (1978; Zbl 0375.05033)] and the lower bound for \(r(F,K_n)\) of \textit{P. Erdős} et al. [Discrete Math. 67, 227-233 (1987; Zbl 0624.05047)] as special cases. Moreover, for a complete bipartite graph \(K_{m,k}\) and a complete graph \(K_m\), \(k\leq m\leq 2\), the following upper bound is derived: \[ r(K_{m.k},K_n) \leq (k-m+1+o(1)) \left(\frac{n}{\log n}\right)^m. \] Using connections between the extremal graphs for Ramsey numbers and those for Turán numbers, it is concluded that for an arbitrary \(m\times k\) bipartite graph \(F\) with minimum degree \(s\) and for any \(\varepsilon>0\), if \(k>\frac{m}{\varepsilon}\), then the Turán number \[ \text{ex}(F;N) \geq N^{2-\frac{1}{s}-\varepsilon} \] for all sufficiently large \(N\). This last result proves a conjecture of Erdős and Simonovits for the case that \(k>ms(s-1)\).