New lower bounds for Ramsey numbers of graphs and hypergraphs (Q696820)

Slight modification of the authors' abstract: Let \(G\) be an \(r\)-uniform hypergraph. The multicolor Ramsey number \(r_k(G)\) is the minimum \(n\) such that every \(k\)-coloring of the edges of the complete \(r\)-uniform hypergraph \(K_n^{(r)}\) yields a monochromatic copy of \(G\). Improving slightly upon results from \textit{M. Axenovich, Z. Füredi}, and \textit{D. Mubayi} [J. Comb. Theory, Ser. B 79, 66-86 (2000)], it is proved that \(tk^2+1\leq r_k(K_{2,t+1})\leq tk^2+k+2\), where the lower bound holds when \(t\) and \(k\) are both powers of a prime \(p\). When \(t=1\), the lower bound is improved by 1, proving that \(r_k(C_4)\geq k^2+2\) for any prime power \(k\). This extends the result of \textit{F. Lazebnik} and \textit{A. J. Woldar} [J. Comb. Theory, Ser. B 79, 172-176 (2000)], which proves the same bound when \(k\) is an odd prime power. These results are generalized to hypergraphs in the following sense. Fix integers \(r,s,t\geq 2\). Let \({\mathcal H}^{(r)}(s,t)\) be the complete \(r\)-partite \(r\)-graph with \(r-2\) parts of size 1, one part of size \(s\), and one part of size \(t\) (note that \({\mathcal H}{(2)} (s,t)=K_{s,t})\). It is proved that \(tk^2-k+1\leq r_k({\mathcal H}^{(r)}(2,t+1))\leq tk^2+k+r,\) where the lower bound holds when \(t\) and \(k\) are both powers of a prime \(p\) and \((1-o(1))k^s\leq r_k({\mathcal H}^{(r)}(s,t))\leq O(k^s)\), for fixed \(t,s\geq 2, t>(s-1)!\), \(r_k({\mathcal H}^{(r)}(3,3))=(1+o(1))k^3\). Some of the lower bounds are special cases of a family of more general hypergraph constructions obtained by algebraic methods. This provides an extension of the results of \textit{F. Lazebnik} and \textit{A. J. Woldar} [J. Graph Theory 38, 65-86 (2001; Zbl 0990.05080)] about graphs.