| Ramsey's Theorem |
Website Links For Theorem |
Information AboutRamsey's Theorem |
|
In Combinatorics , Ramsey's theorem states that in colouring a large Complete Graph (that is a Simple Graph , where an Edge connects every pair of Vertices ), one will find complete subgraphs all of the same colour. In a precise statement, for any pair of positive integers (''r'',''s''), there exists an integer ''R''(''r'',''s'') such that for any Complete Graph on ''R''(''r'',''s'') vertices, whose edges are coloured ''red'' or ''blue'', there exists either a complete subgraph on ''r'' vertices which is entirely blue, or a complete subgraph on ''s'' vertices which is entirely red. Here ''R(r,s)'' signifies an integer that depends on both ''r'' and ''s''. Ramsey's theorem is a foundational result in combinatorics. The first version of this result was proved by F. P. Ramsey . This initiated the combinatorial theory, now called ''Ramsey theory'', that seeks regularity amid disorder: general conditions for the existence of substructures with regular properties. In this application it is a question of the existence of ''homogeneous subsets'', that is, subsets of connected edges of just one colour. An extension of this theorem applies to any finite number of colours, rather than just two. More precisely, the theorem states that for any given number of colors ''c'', and any given integers ''n''1,...,''nc'', there is a number, ''R''(''n''1, ..., ''nc''; ''c''), such that if the edges of a complete graph of order ''R''(''n''1, ..., ''nc''; ''c'') are colored with ''c'' different colors, then for some ''i'' between 1 and ''c'', it must contain a complete subgraph of order ''ni'' whose edges are all color ''i''. The special case above has ''c'' = 2 (and ''n''1 = ''r'' and ''n''2 = ''s''). EXAMPLE: ''R''(3,3;2)=6 Suppose the edges of a complete graph on 6 vertices are coloured red and blue. Pick a vertex ''v''. There are 5 edges incident to ''v'' and so (by the Pigeonhole Principle ) at least 3 of them must be the same colour. Without Loss Of Generality we can assume at least 3 of these edges, connecting to vertices ''r'', ''s'' and ''t'', are blue. (If not, exchange red and blue in what follows.) If any of the edges (''r'', ''s''), (''r'', ''t''), (''s'', ''t'') are also blue then we have an entirely blue triangle. If not, then those three edges are all red and we have with an entirely red triangle. Since this argument works for any colouring ''any'' ''K''6 contains a monochromatic ''K''3 and therefore that ''R''(3,3;2) ≤ 6. The popular version of this is called the Theorem On Friends And Strangers . An alternate proof works by Double Counting . It goes as follows. Count the number of ordered triples of vertices ''x'', ''y'', ''z'' such that the edge (''xy'') is red and the edge (''yz'') is blue. Firstly, any given vertex will be the middle of either 0×5=0, 1×4=4 or 2 × 3 = 6 such triples. Therefore there are at most 6×6=36 such triples. Secondly, for any non-monochromatic triangle (xyz), there exist precisely two such triples. Therefore there are at most 18 non-monochromatic triangles. Therefore there are at least 2 monochromatic triangles. Conversely, it is possible to 2-colour a ''K''5 without creating any monochromatic ''K''3, showing that ''R''(3,3;2) > 5. The unique coloring is shown to the right. Thus ''R''(3,3;2) = 6. PROOF OF THE THEOREM We prove the theorem for the 2-colour case, by Induction on ''r'' + ''s''. It is clear from the definition that for all ''n'', ''R''(''n'', 1) = ''R''(1, ''n'') = ''1''. This starts the induction. We prove that ''R''(''r'', ''s'') exists by finding an explicit bound for it. By the inductive hypothesis ''R''(''r'' − 1, ''s'') and ''R''(''r'', ''s'' − 1) exist. Claim: ''R''(''r'', ''s'') ≤ ''R''(''r'' − 1, ''s'') + ''R''(''r'', ''s'' − 1): Consider a complete graph on ''R''(''r'' − 1, ''s'') + ''R''(''r'', ''s'' − 1) vertices. Pick a vertex ''v'' from the graph and consider two subgraphs ''M'' and ''N'' where a vertex ''w'' is in ''M'' If And Only If (''v'', ''w'') is blue and is in ''N'' otherwise. | ||
| { Border | "1" cellpadding="6" cellspacing="0" |
|
|