On a Ramsey type theorem (Q2553974): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q106084729, #quickstatements; #temporary_batch_1710199756243 |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: A partition calculus in set theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Partition relations for cardinal numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5759552 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some remarks on the theory of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3286850 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02018669 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2045774391 / rank | |||
Normal rank |
Latest revision as of 09:46, 30 July 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