Evasive Sets, Covering by Subspaces, and Point-Hyperplane Incidences.

Given positive integers and a finite field , a set is (, )- if every -dimensional affine subspace contains at most elements of . By a simple averaging argument, the maximum size of a (, )-subspace evasive set is at most . When and are fixed, and is sufficiently large, the matching lower bound is proved by Dvir and Lovett.

A Sharp Threshold Phenomenon in String Graphs.

A string graph is the intersection graph of curves in the plane. We prove that for every , if is a string graph with vertices such that the edge density of  is below , then () contains two linear sized subsets and  with no edges between them. The constant 1/4 is a sharp threshold for this phenomenon as there are string graphs with edge density less than such that there is an edge connecting any two logarithmic sized subsets of the vertices.