Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T19:21:05.883Z Has data issue: false hasContentIssue false

Graph Theory and Probability. II

Published online by Cambridge University Press:  20 November 2018

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)

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1961