An explicit construction for a Ramsey problem (Q705745): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:59, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An explicit construction for a Ramsey problem |
scientific article |
Statements
An explicit construction for a Ramsey problem (English)
0 references
14 February 2005
0 references
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.
0 references
Ramsey problems
0 references
explicit constructions
0 references
algebraic method
0 references
coloring
0 references