کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655419 | 1343384 | 2013 | 17 صفحه PDF | دانلود رایگان |
A celebrated result in Ramsey Theory states that the order of magnitude of the triangle-complete graph Ramsey numbers R(3,t)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,ge,f,g such that |e∩f|=|f∩g|=|g∩e|=1|e∩f|=|f∩g|=|g∩e|=1 and e∩f∩g=∅e∩f∩g=∅. For all r⩾2r⩾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>0a,br>0 such that for all t⩾3t⩾3,at32(logt)34⩽R(C3,Kt3)⩽b3t32 and for r⩾4r⩾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⩾3r⩾3. We also study a generalization to hypergraphs of cycle-complete graph Ramsey numbers R(Ck,Kt)R(Ck,Kt) and a connection to r3(N)r3(N), the maximum size of a set of integers in {1,2,…,N}{1,2,…,N} not containing a three-term arithmetic progression.
Journal: Journal of Combinatorial Theory, Series A - Volume 120, Issue 7, September 2013, Pages 1491–1507