Hostname: page-component-76fb5796d-zzh7m Total loading time: 0 Render date: 2024-04-25T23:30:16.888Z Has data issue: false hasContentIssue false
  • English
  • Français

Graph Theory and Probability. II

Published online by Cambridge University Press:  20 November 2018

P. Erdös
P. Erdös*
Affiliation:
Australian National University, Canberra
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.

Define f(k, l) as the least integer so t h a t every graph having f(k, l) vertices contains either a complete graph of order k or a set of l independent vertices (a complete graph of order k is a graph of k vertices every two of which are connected by an edge, a set of I vertices is called independent if no two are connected by an edge).

Throughout this paper c1, c2, … will denote positive absolute constants. It is known (1, 2) that

(1)

and in a previous paper (3) I stated that I can prove that for every ∈ > 0 and l > l(∈), f (3, l) > l2-∈. In the present paper I am going to prove that

(2)

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 13 , 1961 , pp. 346 - 352
Copyright
Copyright © Canadian Mathematical Society 1961

References

1. Erdös, P. and Szckeres, G., On a combinatorial problem in geometry, Compositio Math., 2 (1935), 463–470.Google Scholar
2. Erdös, P., Remarks on a theorem of Ramsey, Bull. Research Council of Israel, Section F, 7 (1957).Google Scholar
3. Erdös, P., Graph theory and probability, Can. J. Math., 11 (1959), 34–38.Google Scholar
4. Erdös, P. and Rényi, A., On the evolution of random graphs, Publ. Inst. Hung. Acad. Sci., 5 (1960), 17–61.Google Scholar