Ramsey theory: Difference between revisions
Jump to navigation
Jump to search
imported>Christopher Smithers (New page: '''Ramsey Theory''' is is a branch of Graph theory which studies seemingly orderless systems and analyses the conditions under which order must be present. Typically it makes statement...) |
imported>Meg Taylor No edit summary |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
'''Ramsey Theory''' | {{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 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 9: | 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 04: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
