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 Erdos's probabilistic argument shows the existence of graphs on 2^n vertices with no clique or independent set of size 2n, the best known explicit constructions are far from this bound Constructing Ramsey graphs is closely related to polynomial representations of Boolean functions; Grolmusz has shown that a low degree representation for the OR function can be used to explicitly construct Ramsey graphs.

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 on if the union of their zero sets contains all points in the hypercube except the origin.We give a simple construction of a Ramsey graph using such polynomials.Furthermore, we show that all the best known constructions, ones to due to Frankl-Wilson, Grolmusz and Alon 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 current techniques appears to be the construction of lower degree representations. Using new algebraic techniques, we show that the above Ramsey constructions cannot be improved using symmetric polynomials.