has1)edges,so there would bea total ofgrapststhrough (for ccoou)f brte As described above,R(3,3)=6.It is easy to prove that R(4,2)=4,and,more generally,that R(s,2)=s for all s:a graph on s-1 nodes with all edges coloured red serves as a counterexample and proves that R(s,2)2S;among colourings of a graph on s nodes,the colouring with all edges coloured red contains a 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,it can be concluded that R(4,3)R(4,2)+R(3,3)-1=9,and therefore R(4,4)R(4,3)+R(3,4)<18.There are only two (4,4,16)graphs (that is,2-colourings of a complete graph on 16 nodes without 4-node red or blue complete subgraphs)among 6.4x 1022 different ouring of 16-node graphs,and only one (,4,17)graph (the Paley graph of order 17)am 2.46×1026 R(4,4)= (This was proven by Evans,Pulham and Sheehan in 1979.)It follows that 18 The fact that R(4,5)=25 was first established by Brendan McKay and Stanislaw The exact value of R(5.5)is unkno n,although it is known to lie between 43(Geoffrey Exoo (1989)8)) and 48(Angeltveit and McKay (2017)(inclusive). Erdos asks us to imagine ce,vastly more poweranding on Earth e ale. -Joel Spencer(10] In 1997,McKa m警场 Radzisski and Exoo employed computer-as conjecture that R(5,5)= R(r,s)with r,ss 10 are shown in the table below.Where the exact value is unknown,the table lists the best known bounds.R(r,s)with r,s<3 are given by R(1,s)=1 and R(2,s)=s for all values of s.The standard survey on the dev elopment of Ramsey number research is the Dynamic Survey 1 of the Electronic Journal of Combinatorics.121 It was written and is updated by Stanislaw Radziszowski.Its latest update was in March 2017.In general,there are a few y ears be een the updates.Wher not cited otherwise,entries in the table below are taken from this dynamic suvey.Note diagonal sice R(r,s)=R(s,r). has 1 2 n(n − 1) edges, so there would be a total of c n(n − 1) 2 graphs to search through (for c colours) if brute force is used.[6] Therefore, the complexity for searching all possible graphs (via brute force) is O(c n 2 ) for c colourings and an upper bound of n nodes. As described above, R(3, 3) = 6. It is easy to prove that R(4, 2) = 4, and, more generally, that R(s, 2) = s for all s: a graph on s − 1 nodes with all edges coloured red serves as a counterexample and proves that R(s, 2) ≥ s; among colourings of a graph on s nodes, the colouring with all edges coloured red contains a 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, it can be concluded that R(4, 3) ≤ R(4, 2) + R(3, 3) − 1 = 9, and therefore R(4, 4) ≤ R(4, 3) + R(3, 4) ≤ 18. There are only two (4, 4, 16) graphs (that is, 2-colourings of a complete graph on 16 nodes without 4-node red or blue complete subgraphs) among 6.4 × 10 22 different 2-colourings of 16-node graphs, and only one (4, 4, 17) graph (the Paley graph of order 17) among 2.46 × 10 26 colourings. [5] (This was proven by Evans, Pulham and Sheehan in 1979.) It follows that R(4, 4) = 18. The fact that R(4, 5) = 25 was first established by Brendan McKay and Stanisław Radziszowski in 1995.[7] The exact value of R(5, 5) is unknown, although it is known to lie between 43 (Geoffrey Exoo (1989)[8] ) and 48 (Angeltveit and McKay (2017)[9] ) (inclusive). Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. — Joel Spencer [10] In 1997, McKay, Radziszowski and Exoo employed computer-assisted graph generation methods to conjecture that R(5, 5) = 43. They were able to construct exactly 656 (5, 5, 42) graphs, arriving at the same set of graphs through different routes. None of the 656 graphs can be extended to a (5, 5, 43) graph.[11] For R(r, s) with r, s > 5, only weak bounds are available. Lower bounds for R(6, 6) and R(8, 8) have not been improved since 1965 and 1972, respectively. [12] R(r, s) with r, s ≤ 10 are shown in the table below. Where the exact value is unknown, the table lists the best known bounds. R(r, s) with r, s < 3 are given by R(1, s) = 1 and R(2, s) = s for all values of s. The standard survey on the development of Ramsey number research is the Dynamic Survey 1 of the Electronic Journal of Combinatorics. [12] It was written and is updated by Stanisław Radziszowski. Its latest update was in March 2017. In general, there are a few years between the updates. Where not cited otherwise, entries in the table below are taken from this dynamic survey. Note there is a trivial symmetry across the diagonal since R(r, s) = R(s, r)