Constructive bounds for a Ramsey-type problem (Q1376057): Difference between revisions

Many important bounds for the Ramsey function \(R(s,t)\) are proved using probabilistic techniques. Some additional constructive ideas have been developed in recent years, but they usually give weaker bounds. The authors consider a more general Ramsey type function, and give constructive bounds for this function. In particular, given integers \(r\) and \(s\) with \(2 \leq r < s\), they construct a graph \(H = H_{r,s,n}\) of order \(n\) such that for some \(\varepsilon = \varepsilon(r,s)\), \(H\) contains no clique of order \(s\) and every subset with at least \(n^{1 - \varepsilon}\) vertices contains a clique of size \(r\). These constructions use properties of finite geometries and geometric expanders.