On a Ramsey type theorem (Q2553974): Difference between revisions
From MaRDI portal
Set profile property. |
Created claim: Wikidata QID (P12): Q106084729, #quickstatements; #temporary_batch_1710199756243 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q106084729 / rank | |||
Normal rank |
Revision as of 00:43, 12 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a Ramsey type theorem |
scientific article |
Statements
On a Ramsey type theorem (English)
0 references
1972
0 references
Let \(\bar G\) denote the complement of the graph \(G\), and let \(K_n\) denote the complete graph on \(n\) vertices. The main result of this paper is the following: Theorem 2. Let \(G(n,r)\) be a graph of \(n\) vertices with \(r<{n^2 \over k}\) edges. Then there is a positive constant \(c\) such that for \(s<c{k \over \log k} \log n\), either \(\overline{G(n,r)}\) or \(G(n,r)\) contains \(K_s\) as a subgraph. This result is shown to be best possible as far as the order of magnitude is concerned.
0 references