Name
Abstract | ||
|---|---|---|
Extending the concept of Ramsey numbers, Erdős and Rogers introduced the following function. For given integers 2≤s<t letfs,t(n)=min{max{|W|:W⊆V(G) and fs,t(n)=G[W] contains no Ks}}, where the minimum is taken over all Kt-free graphs G of order n. In this paper, we show that for every s≥3 there exist constants c1=c1(s) and c2=c2(s) such that fs,s+1(n)≤c1(logn)c2n. This result is best possible up to a polylogarithmic factor. We also show that for all t−2≥s≥4, there exists a constant c3=c3(s) such that fs,t(n)≤c3n. In doing so, we partially answer a question of Erdős by showing that limn→∞fs+1,s+2(n)fs,s+2(n)=∞ for any s≥4. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.jctb.2014.06.006 | Journal of Combinatorial Theory, Series B |
Keywords | Field | DocType |
Generalized Ramsey numbers,Erdős and Rogers numbers | Integer,Graph,Combinatorics,Arithmetic,Ramsey's theorem,Mathematics | Journal |
Volume | Issue | ISSN |
109 | C | 0095-8956 |
Citations | PageRank | References |
3 | 0.40 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Dudek | 1 | 3 | 0.40 |
| Troy Retter | 2 | 5 | 2.20 |
| Vojtech Rödl | 3 | 3 | 0.40 |
| Vojta Rödl | 4 | 3 | 0.40 |