Lower bounds for small diagonal Ramsey numbers
type: Item
instance of: scholarly article
title: Lower bounds for small diagonal Ramsey numbers
zbMATH Open document ID: 0614.05037
DOI: 10.1016/0097-3165(86)90102-0
author: James B. Shearer
published in: Journal of Combinatorial Theory. Series A
publication date: 1986-01-01T00:00:00Z
review text: For p a prime that is congruent to 1 modulo 4, let \(G_ p\) be the self complementary graph with vertices \(\{\) 0,1,...,p-1\(\}\) and edges the pairs whose difference is a quadratic residue modulo p. If \(k=k(p)\) is the order of the largest clique in \(G_ p\), then clearly the diagonal Ramsey number \(r(K_{k+1},K_{k+1})=r(k+1)\) exceeds p. Using the graph \(G_ p\) a graph \(H_ p\) on \(2p+2\) vertices with clique number \(k+1\) is constructed, and this graph implies that \(r(k+2)>2p+2\). Also, for each of the primes \(p\leq 3000\) a computer search to determine the value of k associated with p was made, and these findings are summarized in a table. These results generate some improved lower bounds for diagonal Ramsey numbers.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3993623
zbMATH Keywords: classical Ramsey numbers
zbMATH Keywords: quadratic residues
zbMATH Keywords: clique
zbMATH Keywords: diagonal Ramsey numbers
MaRDI profile type: Publication
full work available at URL: 0097-3165(86)90102-0
OpenAlex ID: W2027234979
cites work: Some lower bounds of the Ramsey number \(n(k,k)\).
cites work: A survey of bounds for classical Ramsey numbers
description: scientific article; zbMATH DE number 3993623