A variant of the classical Ramsey problem
type: Item
instance of: scholarly article
title: A variant of the classical Ramsey problem
zbMATH Open document ID: 0910.05034
DOI: 10.1007/BF01195000
author: András Gyárfás
author: P. Erdős
published in: Combinatorica
publication date: 1999-03-14T00:00:00Z
review text: The following quantity is estimated. Let \(f(n,p,q)\) be the minimum number of colors needed to color all edges of \(K_n\) such that every \(K_p\) gets at least \(q\) colors. A general upper bound is given using the Lovász local lemma. If \(q={p\choose 2}-p+3\) then \(f(n,p,q)\) is linear while \(f(n,p,q-1)\) is sublinear. If \(q={p\choose 2}-\lfloor{p\over 2}\rfloor+2\) then \(f(n,p,q)=\Omega(n^2)\) while \(f(n,p,q-1)=O(n^{2-{4\over p}})\) but is \(\Omega(n^{{4\over 3}})\) for \(p\geq 7\). \(f(n,p,p)=\Omega(n^{{1\over{p-2}}})\). Also, \({5\over 6}(n-1)\leq f(n,4,5)\) and \(f(n,9,34)={n\choose 2}-o(n^2)\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 1261162
zbMATH Keywords: extremal graph theory
zbMATH Keywords: probabilistic methods
reviewed by: Péter Komjáth
MaRDI profile type: Publication
cites work: On the existence of triangulated spheres in 3-graphs, and related problems
cites work: On coloring graphs to maximize the proportion of multicolored k-edges
cites work: Linear sets with five distinct differences among any four elements
full work available at URL: https://doi.org/10.1007/bf01195000
OpenAlex ID: W1994434808
description: scientific article; zbMATH DE number 1261162