Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\) (Q1343782): Difference between revisions

For positive integers \(\ell> k\geq 2\), the Ramsey number \(r_ k(\ell; r)\) is the smallest integer \(n\) such that for every coloring of the \(k\)- element subsets of an \(n\)-element set with \(r\) colors, their always exists an \(\ell\)-element set, all of whose \(k\)-element subsets have the same color. Let \(t_ 2(x)= 2^ x\), and inductively, \(t_ k(x)= 2^{t_{k-1}(x)}\). It is know that \(r_ k(\ell; r)\leq t_ k(c^ r_ k \ell)\), and there are corresponding lower bounds when \(\ell= \ell(k)\) is sufficiently large, so in this case the Ramsey number grows like a tower. Using shift graphs lower bounds are proved that verify that \(r_ k(\ell, r)\) grows like a tower even when there is no restriction on \(\ell\) as long as \(r\geq 3\).