Summary: Explicit construction of Ramsey graphs or graphs with no large clique or independent set, has remained a challenging open problem for a long time. While Erdős’ probabilistic argument shows the existence of graphs on \(2^n\) vertices with no clique or independent set of size \(2n\), the best explicit constructions achieve a far weaker bound. There is a connection between Ramsey graph constructions and polynomial representations of Boolean functions due to Grolmusz; a low degree representation for the OR function can be used to explicitly construct Ramsey graphs (see [V. Grolmusz, Lect. Notes Comput. Sci. 1276, 82–90 (1997; Zbl 0888.05053); Combinatorica 20, No. 1, 71–86 (2000; Zbl 0949.05083)]).
We generalize the above relation by proposing a new framework. We propose a new definition of OR representations: a pair of polynomials represent the OR function if the union of their zero sets contains all points in \(\{0, 1\}^n\) except the origin. We give a simple construction of a Ramsey graph using such polynomials. Furthermore, we show that all the known algebraic constructions, ones to due to P. Frankl and R. M. Wilson [Combinatorica 1, 357–368 (1981; Zbl 0498.05048)], Grolmusz [Zbl 0949.05083, loc. cit.] and N. Alon [ibid. 18, No. 3, 301–310 (1998; Zbl 0921.05039)] are captured by this framework; they can all be derived from various OR representations of degree \(O(\sqrt{n})\) based on symmetric polynomials.

Thus the barrier to better Ramsey constructions through such algebraic methods appears to be the construction of lower degree representations. Using new algebraic techniques, we show that better bounds cannot be obtained using symmetric polynomials.