Some constructive bounds on Ramsey numbers (Q974470)

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.