We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Hypergraph Ramsey numbers of cliques versus stars.
- Authors
Conlon, David; Fox, Jacob; He, Xiaoyu; Mubayi, Dhruv; Suk, Andrew; Verstraëte, Jacques
- Abstract
Let Km(3)$$ {K}_m^{(3)} $$ denote the complete 3‐uniform hypergraph on m$$ m $$ vertices and Sn(3)$$ {S}_n^{(3)} $$ the 3‐uniform hypergraph on n+1$$ n+1 $$ vertices consisting of all n2$$ \left(\genfrac{}{}{0ex}{}{n}{2}\right) $$ edges incident to a given vertex. Whereas many hypergraph Ramsey numbers grow either at most polynomially or at least exponentially, we show that the off‐diagonal Ramsey number r(K4(3),Sn(3))$$ r\left({K}_4^{(3)},{S}_n^{(3)}\right) $$ exhibits an unusual intermediate growth rate, namely, 2clog2n≤r(K4(3),Sn(3))≤2c′n2/3logn,$$ {2}^{c\log^2n}\le r\left({K}_4^{(3)},{S}_n^{(3)}\right)\le {2}^{c^{\prime }{n}^{2/3}\log n}, $$for some positive constants c$$ c $$ and c′$$ {c}^{\prime } $$. The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum N$$ N $$ such that any 2‐edge‐coloring of the Cartesian product KN□KN$$ {K}_N\square {K}_N $$ contains either a red rectangle or a blue Kn$$ {K}_n $$?
- Subjects
HYPERGRAPHS; RAMSEY numbers; RAMSEY theory; RECTANGLES
- Publication
Random Structures & Algorithms, 2023, Vol 63, Issue 3, p610
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.21155