Some Remarks on Ramsay's Theorem
Canadian mathematical bulletin, Tome 7 (1964) no. 4, pp. 619-622
Voir la notice de l'article provenant de la source Cambridge University Press
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.
Erdös, P. Some Remarks on Ramsay's Theorem. Canadian mathematical bulletin, Tome 7 (1964) no. 4, pp. 619-622. doi: 10.4153/CMB-1964-059-6
@article{10_4153_CMB_1964_059_6,
author = {Erd\"os, P.},
title = {Some {Remarks} on {Ramsay's} {Theorem}},
journal = {Canadian mathematical bulletin},
pages = {619--622},
year = {1964},
volume = {7},
number = {4},
doi = {10.4153/CMB-1964-059-6},
url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1964-059-6/}
}
[1] 1. Erdös, P. and Szekeres., G., A combinatorial problem in geometry, Compositio Math. 2(1935), 463–470. Google Scholar
[2] 2. Erdős, P., Graph theory and probability II, Can. J. Math. 13 (1961), 346–352. Google Scholar | DOI
[3] 3. Ramsay, F. P., On a problem of formal logic, Proc. London Math. Soc., 30(1929), 264–286. Google Scholar
Cité par Sources :