In reverse mathematics,there is a significant difference in proof strength between the version of Ramsey's theorem for infinite graphs(the case n=2)and for infinite multigraphs (the case n 23).The multigraph version of the theorem is equivalent in strength to the arithmetical comprehension axiom,making it part of the subsystem ACAo of second-order arithmetic,one of the big five subsystems in reverse mathematics.In contrast,by a theorem of David Seetapun,the graph version of the theorem is weaker than ACAo,and (combining Seetapun's result with others)it does not fall into one of the big five subsystems.6 Infinite version implies the finite It is possible to deduce the finite Ramsey theorem from the infinite version by a proof by contradiction. Suppose the finite Ramsey theorem is false.Then there exist integers c,n,T such that for every integer k,there exists a c-colouring of [(without a monochromatic set of size T.Let Cr denote the c-colourings of [( without a monochromatic set of size t. For any k,the restriction of a colouring in Ck+to[(by ignoring the colour of all sets containingk+1)is a colouring in Ci.Define C to be the colourings in Cr which are restrictions of colourings in C.Since Ck+is not empty,neither is C Similarly,the restriction of any colouring in is in allowing one to define as the set of all such restrictions,a non-empty set.Continuing so,define Cm for all integers m,k. Now,for any integer k,C..,and each set is non-empty.Furthermore,Ck is finite as follows that the intersection of all of these sets is non-empty.and let D=C.Then every colouring in Dk is the restriction of a colouring in D+.Therefore, by unrestricting a colouring in D to a colouring in D,and continuing doing so,one constructs a colouring of N)without any monochromatic set of size T.This contradicts the infinite Ramsey theorem. If a suitable topologica vie that the infin ewp int is taken,this ent bo Directed graph Ramsey numbers It is also possible to define Ramsey numbers for directed graphs;these were introduced by P.Erdos and L. Moser(1964).Let R(n)be the smallest number Q such that any complete graph with singly directed arcs (also called a "tournament)and with Q nodes contains an acyclic (also called "transitive")n-node subtoumament. graph analogue of what(above)has mber Z such that olete undirect node he a logue of the rs is the two directions of the arcs.the analogue of monochromatic"is"all arc-amows point the same wayi.e."acyclic. We have R(0)=0,R(1)=1,R(2)=2,R3)=4,R(4)=8,R5)=14,R(6)=28,and32≤R(7)≤54.18 Ramsey computation and quantum computers In reverse mathematics, there is a significant difference in proof strength between the version of Ramsey's theorem for infinite graphs (the case n = 2) and for infinite multigraphs (the case n ≥ 3). The multigraph version of the theorem is equivalent in strength to the arithmetical comprehension axiom, making it part of the subsystem ACA0 of second-order arithmetic, one of the big five subsystems in reverse mathematics. In contrast, by a theorem of David Seetapun, the graph version of the theorem is weaker than ACA0 , and (combining Seetapun's result with others) it does not fall into one of the big five subsystems. [16] It is possible to deduce the finite Ramsey theorem from the infinite version by a proof by contradiction. Suppose the finite Ramsey theorem is false. Then there exist integers c, n, T such that for every integer k, there exists a c-colouring of without a monochromatic set of size T. Let Ck denote the c-colourings of without a monochromatic set of size T. For any k, the restriction of a colouring in Ck+1 to (by ignoring the colour of all sets containing k + 1) is a colouring in Ck . Define to be the colourings in Ck which are restrictions of colourings in Ck+1 . Since Ck+1 is not empty, neither is . Similarly, the restriction of any colouring in is in , allowing one to define as the set of all such restrictions, a non-empty set. Continuing so, define for all integers m, k. Now, for any integer k, , and each set is non-empty. Furthermore, Ck is finite as . It follows that the intersection of all of these sets is non-empty, and let . Then every colouring in Dk is the restriction of a colouring in Dk+1 . Therefore, by unrestricting a colouring in Dk to a colouring in Dk+1 , and continuing doing so, one constructs a colouring of without any monochromatic set of size T. This contradicts the infinite Ramsey theorem. If a suitable topological viewpoint is taken, this argument becomes a standard compactness argument showing that the infinite version of the theorem implies the finite version.[17] It is also possible to define Ramsey numbers for directed graphs; these were introduced by P. Erdős and L. Moser (1964). Let R(n) be the smallest number Q such that any complete graph with singly directed arcs (also called a "tournament") and with ≥ Q nodes contains an acyclic (also called "transitive") n-node subtournament. This is the directed-graph analogue of what (above) has been called R(n, n; 2), the smallest number Z such that any 2-colouring of the edges of a complete undirected graph with ≥ Z nodes, contains a monochromatic complete graph on n nodes. (The directed analogue of the two possible arc colours is the two directions of the arcs, the analogue of "monochromatic" is "all arc-arrows point the same way"; i.e., "acyclic.") We have R(0) = 0, R(1) = 1, R(2) = 2, R(3) = 4, R(4) = 8, R(5) = 14, R(6) = 28, and 32 ≤ R(7) ≤ 54.[18] Ramsey numbers can be determined by some universal quantum computers. The decision question is solved by determining whether the probe qubit exhibits resonance dynamics. [19] Infinite version implies the finite Directed graph Ramsey numbers Ramsey computation and quantum computers