Hypergraph Ramsey numbers: Triangles versus cliques

Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraete

Research output: Contribution to journalArticlepeer-review

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, 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.

Original languageEnglish (US)
Pages (from-to)1491-1507
Number of pages17
JournalJournal of Combinatorial Theory. Series A
Volume120
Issue number7
DOIs
StatePublished - Sep 2013

Keywords

  • Hypergraph
  • Independent set
  • Loose triangle
  • Ramsey number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Hypergraph Ramsey numbers: Triangles versus cliques'. Together they form a unique fingerprint.

Cite this