Premium
New lower bounds for hypergraph Ramsey numbers
Author(s) -
Mubayi Dhruv,
Suk Andrew
Publication year - 2018
Publication title -
bulletin of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.396
H-Index - 48
eISSN - 1469-2120
pISSN - 0024-6093
DOI - 10.1112/blms.12133
Subject(s) - ramsey's theorem , mathematics , combinatorics , hypergraph , exponent , constant (computer programming) , diagonal , upper and lower bounds , exponential function , function (biology) , tower , binary logarithm , discrete mathematics , mathematical analysis , graph , philosophy , linguistics , civil engineering , geometry , evolutionary biology , computer science , engineering , biology , programming language
The Ramsey numberr k ( s , n )is the minimum N such that for every red–blue coloring of the k ‐tuples of { 1 , … , N } , there are s integers such that every k ‐tuple among them is red, or n integers such that every k ‐tuple among them is blue. We prove the following new lower bounds for 4‐uniform hypergraph Ramsey numbers:r 4 ( 5 , n ) > 2 n c log nandr 4 ( 6 , n ) > 2 2 c n 1 / 5, where c is an absolute positive constant. This substantially improves the previous best bounds of 2 n c log log nand 2 n c log n, respectively. Using previously known upper bounds, our result implies that the growth rate ofr 4 ( 6 , n )is double exponential in a power of n . As a consequence, we obtain similar bounds for the k ‐uniform Ramsey numbersr k ( k + 1 , n )andr k ( k + 2 , n ) , where the exponent is replaced by an appropriate tower function. This almost solves the question of determining the tower growth rate for all classical off‐diagonal hypergraph Ramsey numbers, a question first posed by Erdős and Hajnal in 1972. The only problem that remains is to prove thatr 4 ( 5 , n )is double exponential in a power of n .