Graph Theory and Probability
P. Erdös
Source record
Source: Crossref
Published: Jan 1, 1959
DOI: 10.4153/cjm-1959-003-9
Open original source ↗Source abstract
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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.