Ramsey numbers involving large dense graphs and bipartite Turán numbers (Q1405120): Difference between revisions
From MaRDI portal
Revision as of 10:20, 6 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ramsey numbers involving large dense graphs and bipartite Turán numbers |
scientific article |
Statements
Ramsey numbers involving large dense graphs and bipartite Turán numbers (English)
0 references
25 August 2003
0 references
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)\).
0 references
Ramsey numbers
0 references
Turan numbers
0 references
bounds
0 references
0 references