Ramsey theory: Difference between revisions
Jump to navigation
Jump to search
imported>Boris Tsirelson (subpages) |
imported>Meg Taylor No edit summary |
||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
'''Ramsey Theory''' is a branch of [[Graph theory]] which studies seemingly orderless systems and analyses the conditions under which order must be present. Typically it makes statements about the existence of specific sub-graphs in arbitrary graphs. | |||
'''Ramsey Theory''' | |||
==Ramsey Numbers== | ==Ramsey Numbers== | ||
The Ramsey Number <math> R(s,t): s,t\in \mathbb N</math> | The Ramsey Number <math> R(s,t): s,t\in \mathbb N</math> | ||
is defined as the least integer ''n'' such that whenever the [[complete graph]] <math> K_n</math> is coloured, such that each edge is one of two colours, it contains either a <math> K_s</math> with all edges the first colour, or a <math> K_t</math> with all edges the second colour, if such an ''n'' exists. | is defined as the least integer ''n'' such that whenever the [[complete graph]] <math> K_n</math> is coloured, such that each edge is one of two colours, it contains either a <math> K_s</math> with all edges the first colour, or a <math> K_t</math> with all edges the second colour, if such an ''n'' exists. | ||
| Line 11: | Line 9: | ||
===Ramsey's Theorem=== | ===Ramsey's Theorem=== | ||
Ramsey's Theorem states that <math> R(s,t)</math> exists <math> \forall s,t\in \mathbb N</math> | Ramsey's Theorem states that <math> R(s,t)</math> exists <math> \forall s,t\in \mathbb N</math> | ||
Latest revision as of 05:01, 1 November 2013
Ramsey Theory is a branch of Graph theory which studies seemingly orderless systems and analyses the conditions under which order must be present. Typically it makes statements about the existence of specific sub-graphs in arbitrary graphs.
Ramsey Numbers
The Ramsey Number is defined as the least integer n such that whenever the complete graph is coloured, such that each edge is one of two colours, it contains either a with all edges the first colour, or a with all edges the second colour, if such an n exists.
Ramsey Numbers are rarely calculated, largely due to the rate at which the complexity of verifying the results grows.
Ramsey's Theorem
Ramsey's Theorem states that exists
