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: [email protected] (A. Kostochka), [email protected] (D. Mubayi), [email protected] (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 -