Some constructive bounds on Ramsey numbers
type: Item
instance of: scholarly article
title: Some constructive bounds on Ramsey numbers
zbMATH Open document ID: 1200.05137
author: Vojtěch Rödl
author: Alexandr Kostochka
author: Pavel Pudlák
published in: Journal of Combinatorial Theory. Series B
publication date: 2010-06-03T00:00:00Z
review text: Graphs are constructed that provide lower bounds for the classical Ramsey number \(R(k,m)\) for \(k = 4, 5, 6\). More specifically, the bounds are \(R(4,m)\geq \Omega(m^{8/5})\), \(R(5,m)\geq \Omega(m^{5/3})\), and \(R(6,m)\geq \Omega(m^{2})\). The techniques involve a variety of constructions and structures, including the ``superline'' graphs and similar constructions using bipartite graphs, and classical projective planes. These bounds do not have the same order of magnitude of the best lower bounds for the classical Ramsey number proved using probabilistic methods, but they are the best know constructive lower bounds.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5716649
zbMATH Keywords: classical Ramsey numbers
zbMATH Keywords: constructive bounds
zbMATH Keywords: superline graphs
reviewed by: Ralph Faudree
MaRDI profile type: Publication
full work available at URL: j.jctb.2010.01.003
OpenAlex ID: W2149727310
cites work: Explicit Ramsey graphs and orthonormal labelings
cites work: Constructive lower bounds for off-diagonal Ramsey numbers
cites work: Norm-graphs: Variations and applications
cites work: On Graphs that do not Contain a Thomsen Graph
cites work: Some structural properties of low-rank matrices related to computational complexity
cites work: The Ramsey number R(3, t) has order of magnitude t2/log t
cites work: Polarities and \(2k\)-cycle-free graphs
cites work: On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
cites work: Asymptotic lower bounds for Ramsey functions
cites work: Explicit Concentrators from Generalized N-Gons
DOI: 10.1016/J.JCTB.2010.01.003
Recommended article: Constructive bounds for a Ramsey-type problem
Recommended article: Q4597160
Recommended article: Q3089193
Recommended article: An upper bound for some ramsey numbers
Recommended article: More Constructive Lower Bounds on Classical Ramsey Numbers
Recommended article: Q5711189
Recommended article: Lower bounds for some Ramsey numbers
Recommended article: An Upper Bound for Constrained Ramsey Numbers
Recommended article: A constructive approach for the lower bounds on the Ramsey numbersR (s, t)
Recommended article: Q3831046
description: scientific article; zbMATH DE number 5716649