This is the authors' abstract. We don't add key points for this paper.
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.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Paul Erdős (1959) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: