An explicit construction for a Ramsey problem (Q705745): Difference between revisions

Given graphs \(G\) and \(H\), an \((H, q)\)-coloring of \(G\) is a coloring of the edges of \(G\) such that every subgraph of \(G\) isomorphic to \(H\) receives at least \(q\) colors. The minimun munber of colors needed is \(r(G, H, q)\), for details see \textit{M. Axenovich, Z. Füredi} and \textit{D. Mubayi} [J. Comb. Theory, Ser. B 79, No. 1, 66--86 (2000; Zbl 1023.05101)]. For \(G=K_n\) and \(H=K_p\), \(f(n, p, q)\) is used instead of \(r(G, H, q)\). \textit{P. Erdős} and \textit{A. Gyárfás} [Combinatorica 17, No. 4, 459--467 (1997; Zbl 0910.05034)] investigated the growth rate of the function \(f\) when \(p\) is fixed. In particular, they showed that \(d \log n/\log \log n \leq f(n, 4, 2) \leq d' \log n\), and \(f(n, 4, 4) =O(n^{2/3})\) by a probabilistic argument. The main result of this paper gives an explicit (algebraic, with some modifications) coloring that proves \(f(n, 4, 4) < n^{1/2}e^{c \sqrt{\log n}}\). From Turán's celebrated theorem follows easily that \(\Omega(\sqrt{n})= f(n, 4, 4)\), and the author conjectures that indeed, \(f(n, 4, 4)= \Theta (\sqrt{n})\). The proof nicely blends some simple computation over finite fields with graph theoretic ideas.