Editing Ramsey's theorem (section)

=== Asymptotics ===
The inequality {{math|''R''(''r'', ''s'') ≤ ''R''(''r'' − 1, ''s'') + ''R''(''r'', ''s'' − 1)}} may be applied inductively to prove that
:<math>R(r, s) \leq \binom{r + s - 2}{r - 1}. </math>

In particular, this result, due to [[Paul Erdős|Erdős]] and [[George Szekeres|Szekeres]], implies that when {{math|1=''r'' = ''s''}},
:<math>R(s, s) \leq (1 + o(1))\frac{4^{s - 1}}{\sqrt{\pi s}}.</math>

An exponential lower bound,
:<math>R(s, s) \geq (1 + o(1)) \frac{s}{\sqrt{2} e} 2^{s/2},</math>

was given by Erdős in 1947 and was instrumental in his introduction of the probabilistic method. There is a huge gap between these two bounds: for example, for {{math|1=''s'' = 10}}, this gives {{math|101 ≤ ''R''(10, 10) ≤ 48,620}}. Nevertheless, the exponential growth factors of either bound were not improved for a long time, and for the lower bound it still stands at {{math|{{sqrt|2}}}}. There is no known explicit construction producing an exponential lower bound. The best known lower and upper bounds for diagonal Ramsey numbers are
:<math>[1 + o(1)] \frac{\sqrt{2} s}{e} 2^{\frac{s}{2}} \leq R(s, s) \leq s^{-(c \log s)/(\log \log s)} 4^s,</math>

due to [[Joel Spencer|Spencer]] and [[David Conlon|Conlon]], respectively; a 2023 preprint by Campos, Griffiths, [[Robert Morris (mathematician)|Morris]] and [[Julian Sahasrabudhe|Sahasrabudhe]] claims to have made exponential progress using an algorithmic construction relying on a graph structure called a "[[Book (graph theory)|book]]",<ref name="arxiv23">{{cite arXiv |eprint=2303.09521 |class=math.CO |first1=Marcelo |last1=Campos |first2=Simon |last2=Griffiths |title=An exponential improvement for diagonal Ramsey |last3=Morris |first3=Robert |last4=Sahasrabudhe |first4=Julian |year=2023}}</ref><ref>{{Cite web |last=Sloman |first=Leila |date=2 May 2023 |title=A Very Big Small Leap Forward in Graph Theory |url=https://www.quantamagazine.org/after-nearly-a-century-a-new-limit-for-patterns-in-graphs-20230502/ |website=[[Quanta Magazine]]}}</ref> improving the upper bound to
:<math>R(s,s) \leq (4-\varepsilon)^{s}\text{ and } R(s,t) \leq e^{-\delta t+o(s)}\binom{s+t}{t}.</math>
with <math>\varepsilon=2^{-7}</math> and <math>\delta=50^{-1}</math>.

A 2024 preprint<ref>{{cite arXiv |last1=Gupta |first1=Parth |title=Optimizing the CGMS upper bound on Ramsey numbers |date=2024-07-26 |eprint=2407.19026 |last2=Ndiaye |first2=Ndiame |last3=Norin |first3=Sergey |last4=Wei |first4=Louis|class=math.CO }}</ref> by Gupta, Ndiaye, Norin, and Wei claims an improvement of <math>\delta </math> to <math>-0.14e^{-1} \leq 20^{-1}</math>, and the diagonal Ramsey upper bound to

<math>R(s,s) \leq \left(4e^{-0.14e^{-1}}\right)^{s + o(s)} = 3.7792...^{s+o(s)}</math>

For the off-diagonal Ramsey numbers {{math|''R''(3, ''t'')}}, it is known that they are of order {{math|{{sfrac|''t''{{sup|2}}|log ''t''}}}}; this may be stated equivalently as saying that the smallest possible [[Independent set (graph theory)|independence number]] in an {{mvar|n}}-vertex [[triangle-free graph]] is
:<math>\Theta \left (\sqrt{n\log n} \right ).</math>

The upper bound for {{math|''R''(3, ''t'')}} is given by [[Miklós Ajtai|Ajtai]], [[János Komlós (mathematician)|Komlós]], and [[Endre Szemerédi|Szemerédi]],<ref>{{Cite journal |last1=Ajtai |first1=Miklós |last2=Komlós |first2=János |last3=Szemerédi |first3=Endre |date=1980-11-01 |title=A note on Ramsey numbers |journal=Journal of Combinatorial Theory, Series A |language=en |volume=29 |issue=3 |pages=354–360 |doi=10.1016/0097-3165(80)90030-8 |issn=0097-3165|doi-access=free }}</ref> the lower bound was obtained originally by [[Jeong Han Kim|Kim]],<ref>{{Citation |last1=Kim |first1=Jeong Han |title=The Ramsey Number ''R''(3,''t'') has order of magnitude ''t''<sup>2</sup>/log ''t'' |journal=Random Structures and Algorithms |volume=7 |issue=3 |pages=173–207 |year=1995 |citeseerx=10.1.1.46.5058 |doi=10.1002/rsa.3240070302 |author-link1=<!--Jeong Han Kim-->}}</ref> and the implicit constant was improved independently by Fiz Pontiveros, Griffiths and [[Robert Morris (mathematician)|Morris]],<ref>{{Cite web |title=The Triangle-Free Process and the Ramsey Number {{math|''R''(3,''k'')}} |url=https://bookstore.ams.org/memo-263-1274 |access-date=2023-06-27 |website=bookstore.ams.org}}</ref> and [[Tom Bohman|Bohman]] and [[Peter Keevash|Keevash]],<ref>{{Cite journal |last1=Bohman |first1=Tom |last2=Keevash |first2=Peter |date=2020-11-17 |title=Dynamic concentration of the triangle-free process |url=https://doi.org/10.1002/rsa.20973 |journal=Random Structures and Algorithms |language=en |volume=58 |issue=2 |pages=221–293 |doi=10.1002/rsa.20973 | arxiv=1302.5963 }}</ref> by analysing the triangle-free process. 

In general, studying the more general "{{math|''H''}}-free process" has set the best known asymptotic lower bounds for general off-diagonal Ramsey numbers,<ref>{{Cite journal |last1=Bohman |first1=Tom |last2=Keevash |first2=Peter |date=2010-08-01 |title=The early evolution of the H-free process |url=https://doi.org/10.1007/s00222-010-0247-x |journal=Inventiones Mathematicae |language=en |volume=181 |issue=2 |pages=291–336 |doi=10.1007/s00222-010-0247-x |issn=1432-1297| arxiv=0908.0429|bibcode=2010InMat.181..291B }}</ref> {{math|''R''(''s'', ''t'')}}
:<math>c'_s \frac{t^{\frac{s + 1}{2}}}{(\log t)^{\frac{s + 1}{2} - \frac{1}{s - 2}}} \leq R(s, t) \leq c_s \frac{t^{s - 1}}{(\log t)^{s - 2}}.</math>

In particular this gives an upper bound of <math>R(4, t) \leq c_s t^3(\log t)^{-2}</math>. Mattheus and Verstraete (2024)<ref>{{Cite journal | journal=Annals of Mathematics |last1=Mattheus |first1=Sam |last2=Verstraete |first2=Jacques |date=5 Mar 2024 |title=The asymptotics of r(4,t) |volume=199 |issue=2 |arxiv=2306.04007 |doi=10.4007/annals.2024.199.2.8}}</ref><ref>{{Cite web |last=Cepelewicz |first=Jordana |date=22 June 2023 |title=Mathematicians Discover Novel Way to Predict Structure in Graphs |url=https://www.quantamagazine.org/mathematicians-discover-new-way-to-predict-structure-in-graphs-20230622/ |website=[[Quanta Magazine]]}}</ref> gave a lower bound of  <math>R(4, t) \geq c'_s t^3(\log t)^{-4}</math>, determining the asymptotics of <math>R(4, t)</math> up to logarithmic factors, and settling a question of Erdős, who offered 250 dollars for a proof that the lower limit has form <math>c'_s t^{3}(\log t)^{-d}</math>.<ref>{{Citation |last=Erdös |first=Paul |title=Problems and Results on Graphs and Hypergraphs: Similarities and Differences |date=1990 |url=https://doi.org/10.1007/978-3-642-72905-8_2 |work=Mathematics of Ramsey Theory |pages=12–28 |editor-last=Nešetřil |editor-first=Jaroslav |access-date=2023-06-27 |series=Algorithms and Combinatorics |volume=5 |place=Berlin, Heidelberg |publisher=Springer |language=en |doi=10.1007/978-3-642-72905-8_2 |isbn=978-3-642-72905-8 |editor2-last=Rödl |editor2-first=Vojtěch}}</ref><ref>{{Cite web |title=Erdős Problems |url=https://www.erdosproblems.com/166 |access-date=2023-07-12 |website=www.erdosproblems.com}}</ref>