On a Ramsey type theorem (Q2553974): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 06:01, 3 February 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