Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-27T01:44:29.788Z Has data issue: false hasContentIssue false
  • English
  • Français

Some Remarks on Ramsay's Theorem

Published online by Cambridge University Press:  20 November 2018

P. Erdös
P. Erdös*
Affiliation:
McGill University
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A special case of a well known theorem of Ramsay [3] states that an infinite graph either contains an infinite complete subgraph or it contains an infinite independent set; in other words there exists an infinite subset of its vertices so that either every two of them are joined by an edge or no two of them are joined by an edge. Thus if we have a graph whose vertices are the integers, and which has no infinite complete sub-graph, it certainly has an infinite independent set. The question can now be asked if there exists an independent set whose vertices n1 < n2 < … do not tend to infinity too fast.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 7 , Issue 4 , December 1964 , pp. 619 - 622
Copyright
Copyright © Canadian Mathematical Society 1964

References

1. Erdös, P. and Szekeres., G., A combinatorial problem in geometry, Compositio Math. 2(1935), 463–470.Google Scholar
2. Erdős, P., Graph theory and probability II, Can. J. Math. 13 (1961), 346–352.CrossRefGoogle Scholar
3. Ramsay, F. P., On a problem of formal logic, Proc. London Math. Soc., 30(1929), 264–286.Google Scholar