TY - JOUR

T1 - Hypergraph Ramsey numbers

T2 - Triangles versus cliques

AU - Kostochka, Alexandr

AU - Mubayi, Dhruv

AU - Verstraete, Jacques

N1 - Funding Information:
E-mail addresses: kostochk@math.uiuc.edu (A. Kostochka), mubayi@math.uic.edu (D. Mubayi), jverstra@math.ucsd.edu (J. Verstraete). 1 Research of this author is supported in part by NSF grant DMS-0965587 and by grants 12-01-00448-a and 12-01-00631 of the Russian Foundation for Basic Research. 2 Research supported in part by NSF grants DMS 0653946 and DMS 0969092. 3 Research supported by NSF grant DMS 1101489.

PY - 2013/9

Y1 - 2013/9

N2 - 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, b r > 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(C k, K t) 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.

AB - 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, b r > 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(C k, K t) 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.

KW - Hypergraph

KW - Independent set

KW - Loose triangle

KW - Ramsey number

UR - http://www.scopus.com/inward/record.url?scp=84877669040&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84877669040&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2013.04.009

DO - 10.1016/j.jcta.2013.04.009

M3 - Article

AN - SCOPUS:84877669040

SN - 0097-3165

VL - 120

SP - 1491

EP - 1507

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

IS - 7

ER -