Editing Ramsey's theorem (section)

=== Known values ===
{{unsolved|mathematics|What is the value of {{math|''R''(5, 5)}}?}}
As described above, {{math|1=''R''(3, 3) = 6}}. It is easy to prove that {{math|1=''R''(4, 2) = 4}}, and, more generally, that {{math|1=''R''(''s'', 2) = ''s''}} for all {{mvar|s}}: a graph on {{math|''s'' − 1}} nodes with all edges coloured red serves as a counterexample and proves that {{math|''R''(''s'', 2) ≥ ''s''}}; among colourings of a graph on {{mvar|s}} nodes, the colouring with all edges coloured red contains a {{mvar|s}}-node red subgraph, and all other colourings contain a 2-node blue subgraph (that is, a pair of nodes connected with a blue edge.)

Using induction inequalities and the [[handshaking lemma]], it can be concluded that {{math|1=''R''(4, 3) ≤ ''R''(4, 2) + ''R''(3, 3) − 1 = 9}}, and therefore {{math|''R''(4, 4) ≤ ''R''(4, 3) + ''R''(3, 4) ≤ 18}}. There are only two {{math|(4, 4, 16)}} graphs (that is, 2-colourings of a complete graph on 16 nodes without 4-node red or blue complete subgraphs) among {{nowrap|6.4 × 10{{sup|22}}}} different 2-colourings of 16-node graphs, and only one {{math|(4, 4, 17)}} graph (the [[Paley graph]] of order 17) among {{nowrap|2.46 × 10{{sup|26}}}} colourings.<ref name=McKay /> It follows that {{math|1=''R''(4, 4) = 18}}.

The fact that {{math|1=''R''(4, 5) = 25}} was first established by [[Brendan McKay (mathematician)|Brendan McKay]] and [[Stanisław Radziszowski]] in 1995.<ref name=McKay1995>{{cite journal|title=''R''(4,5) = 25|last1=McKay | first1=Brendan D. | last2=Radziszowski | first2=Stanislaw P.|journal=[[Journal of Graph Theory]]|date=May 1995|doi=10.1002/jgt.3190190304|volume=19|issue=3|pages=309–322|url = http://users.cecs.anu.edu.au/~bdm/papers/r45.pdf}}</ref>

The exact value of {{math|''R''(5, 5)}} is unknown, although it is known to lie between 43 (Geoffrey Exoo (1989)<ref>{{cite journal |last1=Exoo |first1=Geoffrey |title=A lower bound for {{math| ''R''(5, 5)}} |journal=[[Journal of Graph Theory]] |date=March 1989 |volume=13 |issue=1 |pages=97–98 |doi=10.1002/jgt.3190130113}}</ref>) and 46 (Angeltveit and McKay (2024)<ref name=AngeltveitandMcKay2024>{{cite arXiv |eprint=2409.15709 |class=math.CO |author1=Vigleik Angeltveit |author2=Brendan McKay|title=<math>R(5,5) \leq 46</math> |date=September 2024}}</ref>), inclusive.

In 1997, McKay, Radziszowski and Exoo employed computer-assisted graph generation methods to conjecture that {{math|1=''R''(5, 5) = 43}}. They were able to construct exactly 656 {{math|(5, 5, 42)}} graphs, arriving at the same set of graphs through different routes. None of the 656 graphs can be extended to a {{math|(5, 5, 43)}} graph.<ref>{{cite journal |url=http://cs.anu.edu.au/~bdm/papers/r55.pdf| title=Subgraph Counting Identities and Ramsey Numbers |author=Brendan D. McKay, Stanisław P. Radziszowski |journal=[[Journal of Combinatorial Theory]] |series=Series B |doi=10.1006/jctb.1996.1741 |volume=69| issue=2|pages=193–209| year=1997|doi-access=free}}</ref>

For {{math|''R''(''r'', ''s'')}} with {{math|''r'', ''s'' > 5}}, only weak bounds are available. Lower bounds for {{math|''R''(6, 6)}} and {{math|''R''(8, 8)}} have not been improved since 1965 and 1972, respectively.<ref name="bananas" />

{{math|''R''(''r'', ''s'')}} with {{math|''r'', ''s'' ≤ 10}} are shown in the table below. Where the exact value is unknown, the table lists the best known bounds. {{math|''R''(''r'', ''s'')}} with {{math|''r'' < 3}} are given by {{math|1=''R''(1, ''s'') = 1}} and {{math|1=''R''(2, ''s'') = ''s''}} for all values of {{mvar|s}}.

The standard survey on the development of Ramsey number research is the ''Dynamic Survey 1'' of the ''[[Electronic Journal of Combinatorics]]'', by [[Stanisław Radziszowski]], which is periodically updated.<ref name="bananas">{{cite journal | url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1/pdf | title = Small Ramsey Numbers|doi=10.37236/21|doi-access=free|journal=Electronic Journal of Combinatorics|department=Dynamic Surveys|date=2011|last1=Radziszowski|first1=Stanisław| volume = 1000|author1-link=Stanisław Radziszowski}}</ref><ref name="sprSRS">{{cite web|url=https://www.cs.rit.edu/~spr/ElJC/eline.html|title=DS1|author=Stanisław Radziszowski|access-date=17 August 2023}}</ref>   Where not cited otherwise, entries in the table below are taken from the June 2024 edition.  (Note there is a trivial symmetry across the diagonal since {{math|1=''R''(''r'', ''s'') = ''R''(''s'', ''r'')}}.)

{| class="wikitable"
|+ Values / known bounding ranges for Ramsey numbers {{math|''R''(''r'', ''s'')}} {{OEIS|id=A212954}}
! {{diagonal split header|''r''|''s''}}
! width="27" | 1
! width="33" | 2
! width="39" | 3
! width="45" | 4
! 5
! 6
! 7
! 8
! 9
! 10
|-
! 1
| {{yes|'''1'''}}
| {{yes|1}}
| {{yes|1}}
| {{yes|1}}
| {{yes|1}}
| {{yes|1}}
| {{yes|1}}
| {{yes|1}}
| {{yes|1}}
| {{yes|1}}
|-
! 2
|
| {{yes|'''2'''}}
| {{yes|3}}
| {{yes|4}}
| {{yes|5}}
| {{yes|6}}
| {{yes|7}}
| {{yes|8}}
| {{yes|9}}
| {{yes|10}}
|-
! 3
|
|
| {{yes|'''6'''}}
| {{yes|9}}
| {{yes|14}}
| {{yes|18}}
| {{yes|23}}
| {{yes|28}}
| {{yes|36}}
| {{partial|40–41<ref name=Angeltveit2023>{{cite arXiv |eprint=2401.00392 |class=math.CO |first1=Vigleik |last1=Angeltveit|title=<math>R(3,10) \leq 41</math> |date=31 Dec 2023}}</ref>}}
|-
! 4
|
|
|
| {{yes|'''18'''}}
| {{yes|25<ref name=McKay1995 />}}
| {{partial|36–40}}
| {{partial|49–58}}
| {{partial|59<ref name="Exoo2015">{{cite journal | journal = [[Electronic Journal of Combinatorics]] | volume = 22 | issue = 3 | year = 2015 | title = New Lower Bounds for 28 Classical Ramsey Numbers | last1 = Exoo | first1 = Geoffrey | last2 = Tatarevic | first2 = Milos | page = 3 | url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p11| arxiv = 1504.02403 |doi=10.37236/5254 |doi-access=free}}</ref>–79}}
| {{partial|73–105}}
| {{partial|92–135}}
|-
! 5
|
|
|
|
| {{partial|'''43–46'''<ref name=AngeltveitandMcKay2024>{{cite arXiv |eprint=2409.15709 |class=math.CO |author1=Vigleik Angeltveit |author2=Brendan McKay|title=<math>R(5,5) \leq 46</math> |date=September 2024}}</ref>}}
| {{partial|59<ref name="Exoo2023">{{cite arXiv |eprint=2310.17099 |class=math.CO |first1=Geoffrey |last1=Exoo |title=A Lower Bound for R(5,6) |date=26 Oct 2023}}</ref>–85}}
| {{partial|80–133}}
| {{partial|101–193}}
| {{partial|133–282}}
| {{partial|149<ref name="Exoo2015" />–381}}
|-
! 6
|
|
|
|
|
| {{partial|'''102–160'''}}
| {{partial|115<ref name="Exoo2015" />–270}}
| {{partial|134<ref name="Exoo2015" />–423}}
| {{partial|183–651}}
| {{partial|204–944}}
|-
! 7
|
|
|
|
|
|
| {{partial|'''205–492'''}}
| {{partial|219–832}}
| {{partial|252–1368}}
| {{partial|292–2119}}
|-
! 8
|
|
|
|
|
|
|
| {{partial|'''282–1518'''}}
| {{partial|329–2662}}
| {{partial|343–4402}}
|-
! 9
|
|
|
|
|
|
|
|
| {{partial|'''565–4956'''}}
| {{partial|581–8675}}
|-
! 10
|
|
|
|
|
|
|
|
|
| {{partial|'''798–16064'''}}
|}

It is also interesting that Erdos showed  
R(''P''{{sub|n}}, ''K''{{sub|m}})  = (n − 1).(m − 1) + 1,
for a path and a complete graph with n and m vertices respectively. Also Chvatal showed 
R(''T''{{sub|n}}, ''K''{{sub|m}})  = (n − 1).(m − 1) + 1,
for a tree and a complete graph with n and m vertices respectively. These two theorems are the best examples of formulating Ramsey numbers for some special graphs.