A note on constructive lower bounds for the Ramsey numbers \(R(3, t)\) (Q1204480): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claims
Property / author
 
Property / author: Fan R. K. Chung / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Jiahai Kan / rank
Normal rank
 

Revision as of 16:20, 20 February 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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references