Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
type: Item
instance of: scholarly article
title: Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
zbMATH Open document ID: 0822.05047
DOI: 10.1016/0012-365X(93)E0139-U
author: Dwight Duffus
author: Hanno Lefmann
author: Vojtěch Rödl
published in: Discrete Mathematics
publication date: 1995-09-28T00:00:00Z
review text: For positive integers \(\ell> k\geq 2\), the Ramsey number \(r_ k(\ell; r)\) is the smallest integer \(n\) such that for every coloring of the \(k\)- element subsets of an \(n\)-element set with \(r\) colors, their always exists an \(\ell\)-element set, all of whose \(k\)-element subsets have the same color. Let \(t_ 2(x)= 2^ x\), and inductively, \(t_ k(x)= 2^{t_{k-1}(x)}\). It is know that \(r_ k(\ell; r)\leq t_ k(c^ r_ k \ell)\), and there are corresponding lower bounds when \(\ell= \ell(k)\) is sufficiently large, so in this case the Ramsey number grows like a tower. Using shift graphs lower bounds are proved that verify that \(r_ k(\ell, r)\) grows like a tower even when there is no restriction on \(\ell\) as long as \(r\geq 3\).
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 719458
zbMATH Keywords: hypergraphs
zbMATH Keywords: Ramsey number
zbMATH Keywords: coloring
zbMATH Keywords: shift graphs
zbMATH Keywords: lower bounds
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: Q5548831
cites work: Partition relations for cardinal numbers
cites work: Q4074927
cites work: Combinatorial Theorems on Classifications of Subsets of a Given Set
cites work: Intersection theorems and mod \(p\) rank of inclusion matrices
cites work: Combinatorial Relations and Chromatic Graphs
cites work: Arc colorings of digraphs
cites work: A lower bound for Ramsey's theorem
cites work: Q3138966
cites work: A diagonal form for the incidence matrices of \(t\)-subsets vs. \(k\)- subsets
full work available at URL: 0012-365x(93)e0139-u
OpenAlex ID: W2015322433
description: scientific article; zbMATH DE number 719458