Lower Ramsey numbers for graphs (Q1179278)

The lower Ramsey number \(s(\ell,m)\) is the largest integer \(n\) such that for any graph \(G\) of order \(n\) the smallest maximal clique of \(G\) has order at most \(\ell\) and the smallest maximal independent set has order at most \(m\). A construction is described that gives an upper bound for \(s(\ell,m)\) that improves previously known upper bounds. As a corollary of this the lower Ramsey number \(s(1,m)\) is determined precisely. In particular, it is shown that \(s(1,m)=m+2n+\lceil r/n\rceil\), where \(m=n^ 2+r\) and \(0\leq r\leq 2n\). Several interesting conjectures on lower Ramsey numbers are also given.