Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T05:14:03.306Z Has data issue: false hasContentIssue false

Graph Theory and Probability

Published online by Cambridge University Press:  20 November 2018

P. Erdös*
Affiliation:
University of Toronto and Technion, Haifa
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 well-known theorem of Ramsay (8; 9) states that to every n there exists a smallest integer g(n) so that every graph of g(n) vertices contains either a set of n independent points or a complete graph of order n, but there exists a graph of g(n) — 1 vertices which does not contain a complete subgraph of n vertices and also does not contain a set of n independent points. (A graph is called complete if every two of its vertices are connected by an edge; a set of points is called independent if no two of its points are connected by an edge.) The determination of g(n) seems a very difficult problem; the best inequalities for g(n) are (3)

It is not even known that g(n)1/n tends to a limit. The lower bound in (1) has been obtained by combinatorial and probabilistic arguments without an explicit construction.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1959