A note on constructive lower bounds for the Ramsey numbers \(R(3, t)\) (Q1204480): Difference between revisions
From MaRDI portal
Removed claims |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Fan R. K. Chung / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jiahai Kan / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1993.1013 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2032197527 / rank | |||
Normal rank |
Revision as of 20:56, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on constructive lower bounds for the Ramsey numbers \(R(3, t)\) |
scientific article |
Statements
A note on constructive lower bounds for the Ramsey numbers \(R(3, t)\) (English)
0 references
10 March 1993
0 references
The Ramsey number \(R(s,t)\) is the smallest integer \(n\) for which every graph on \(n\) vertices contains either a clique of size \(s\) or an independent set of size \(t\). In this paper, the authors present a simple constructive proof that \[ R(3,t)>{5\over 6}\left({t-1\over 2}\right)^{\log 6/\log 4}\in\Omega(t^{1.29}). \] This improves the best previous constructive lower bound of \[ R(3,t)>t^{(2\log 2)/3(\log 3-\log 2)}\in\Omega(t^{1.13}), \] due to \textit{P. Erdős} [J. Comb. Theory 1, 149-153 (1966; Zbl 0144.454)]. Moreover, the authors' result yields an explicit construction of a triangle-free \(k\)-chromatic graph of size \[ O(k^{\log 6/(\log 6-\log 4)}){\subset O(k^{4.42})}. \] {}.
0 references
Ramsey number
0 references
constructive lower bound
0 references