Name
Abstract | ||
|---|---|---|
A celebrated result in Ramsey Theory states that the order of magnitude of the triangle-complete graph Ramsey numbers R(3,t) is t2/logt. In this paper, we consider an analogue of this problem for uniform hypergraphs. A triangle is a hypergraph consisting of edges e,f,g such that |e∩f|=|f∩g|=|g∩e|=1 and e∩f∩g=∅. For all r⩾2, let R(C3,Ktr) be the smallest positive integer n such that in every red–blue coloring of the edges of the complete r-uniform hypergraph Knr, there exists a red triangle or a blue Ktr. We show that there exist constants a,br>0 such that for all t⩾3,at32(logt)34⩽R(C3,Kt3)⩽b3t32 and for r⩾4t32(logt)34+o(1)⩽R(C3,Ktr)⩽brt32. This determines up to a logarithmic factor the order of magnitude of R(C3,Ktr). We conjecture that R(C3,Ktr)=o(t3/2) for all r⩾3. We also study a generalization to hypergraphs of cycle-complete graph Ramsey numbers R(Ck,Kt) and a connection to r3(N), the maximum size of a set of integers in {1,2,…,N} not containing a three-term arithmetic progression. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.jcta.2013.04.009 | Journal of Combinatorial Theory, Series A |
Keywords | Field | DocType |
Ramsey number,Hypergraph,Loose triangle,Independent set | Ramsey theory,Integer,Discrete mathematics,Combinatorics,Constraint graph,Hypergraph,Ramsey's theorem,Independent set,Conjecture,Mathematics,Arithmetic progression | Journal |
Volume | Issue | ISSN |
120 | 7 | 0097-3165 |
Citations | PageRank | References |
4 | 0.44 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandr V. Kostochka | 1 | 682 | 89.87 |
| Dhruv Mubayi | 2 | 579 | 73.95 |
| Jacques Verstraëte | 3 | 192 | 26.99 |