An explicit construction for a Ramsey problem
type: Item
instance of: scholarly article
title: An explicit construction for a Ramsey problem
zbMATH Open document ID: 1058.05025
author: Dhruv Mubayi
published in: Combinatorica
publication date: 2005-02-14T00:00:00Z
review text: 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.
reviewed by: András Pluhár
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05D10
zbMATH DE Number: 2133936
zbMATH Keywords: Ramsey problems
zbMATH Keywords: explicit constructions
zbMATH Keywords: algebraic method
zbMATH Keywords: coloring
MaRDI profile type: Publication
full work available at URL: s00493-004-0019-6
OpenAlex ID: W2072455759
DOI: 10.1007/S00493-004-0019-6
description: scientific article; zbMATH DE number 2133936