any , if there exists some of size and , such that there is a partition of into cliques of size , then we have . Indeed, supposing is a partition of into cliques of size , we can let be the bipartite graph with and , such that in if and only if . Since the form a clique partition, cannot contain a copy of . It remains to show that such a clique partition exists for any . To show this, let be the finite field of size and . For every polynomial of degree at most over , define . Let be the collection of all , so that and every has size . Clearly no two members of can share members. Since the only -sets in that do not belong to are those that have at least two points sharing the same first coordinate, we know that almost all -subsets of are contained in some . Randomized algebraic constructions Alternative proofs of for sufficiently larger than were also given by Blagojević, Bukh and Karasev and by Bukh using the method of random algebraic constructions. The basic idea is to take a random polynomial and consider the graph between two copies of whose edges are all those pairs such that . To start with, let be a prime power and . Let be a random polynomial with degree at most in , degree at most in , and furthermore satisfying for all . Let be the associated random graph on vertex set , such that two vertices and are adjacent if and only if . To prove the asymptotic lower bound, it suffices to show that the expected number of edges in is . For every -subset , we let denote the vertex subset of that "vanishes on ": . Using the Lang-Weil bound for polynomials in , we can deduce that one always has or for some large constant , which implies . Since is chosen randomly over , it is not hard to show that the right-hand side probability is small, so the expected number of -subsets with also turned out to be small. If we remove a vertex from every such , then the resulting graph is free, and the expected number of remaining edges is still large. This finishes the proof that for all sufficiently large with respect to . More recently, there