Lower bounds for small diagonal Ramsey numbers

DOI10.1016/0097-3165(86)90102-0MaRDI QIDQ1820171zbMATH OpenOpenAlexFDO

Authors James B. Shearer

Publication date 1986

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(86)90102-0

zbMATH Keywords

classical Ramsey numberscliquediagonal Ramsey numbersquadratic residues

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55)

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.

Recommendations

• Tidier examples for lower bounds on diagonal Ramsey numbers
• scientific article; zbMATH DE number 1293762
• scientific article; zbMATH DE number 1744091
• scientific article; zbMATH DE number 6130240
• scientific article; zbMATH DE number 4108824

Cites work

• A survey of bounds for classical Ramsey numbers
• Some lower bounds of the Ramsey number n(k,k).

Cited in

(12)

• Ramsey numbers based on \(C_ 5\)-decompositions
• Tidier examples for lower bounds on diagonal Ramsey numbers
• Randomly finding independent sets in locally sparse graphs
• The independence numbers of weighted graphs with forbidden cycles
• Lower bounds for small Ramsey numbers on hypergraphs
• scientific article; zbMATH DE number 1744091 (Why is no real title available?)
• scientific article; zbMATH DE number 6130240 (Why is no real title available?)
• Some further results in Ramsey graph construction
• Triangular Ramsey numbers
• Diagonal Ramsey via effective quasirandomness
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• A Mathon-type construction for digraphs and improved lower bounds for Ramsey numbers

This page was built for publication: Lower bounds for small diagonal Ramsey numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1820171)