An explicit construction of a 2^((log log n)^c)-Ramsey graph over n vertices

You need to know: Graph, clique, independent set, small o notation, polynomial time algorithm.

Background: A graph on n vertices is called a k-Ramsey graph if it contains no clique or independent set of size k. By an explicit construction of a k-Ramsey graph we mean a polynomial time algorithm that, given the labels of two vertices in the graph, determines whether there is an edge between them. For n-vertex graph, the input of such algorithm has $2\log n$ bits, hence the running time should be polynomial in $\log n$ .

The Theorem: On 14th June 2015, Gil Cohen submitted to arxiv a paper in which he proved the existence of an absolute constant $c$ such that there is an explicit construction of a $2^{(\log \log n)^c}$ -Ramsey graph over $n$ vertices.

Short context: In 1947 Erdős used the probabilistic method to show that most graphs on $n$ vertices are $(2+o(1))\log n$ -Ramsey. Interestingly, there is no known explicit example of such a graph for large n. Before 2015, the best explicit construction was achieved by Barak, Rao, Shaltiel, and Wigderson, who constructed k-Ramsey $n$ -vertex graphs for $k = 2^{2^{{(\log \log n)}^{1-\epsilon}}}$ , see here. The Theorem provides a significantly better construction. The same result was achieved independently by Chattopadhyay and Zuckerman, who posted their paper online on 23rd July 2015. In a later work (submitted in 2018), Li gave an even better explicit construction achieving $k=(\log n)^{o(\log \log \log n)}$ .