Abstract. We call an edge-colored graph rainbow if all of its edges receive distinct colors. An edge-colored graph [Formula: see text] is called [Formula: see text]- rainbow saturated if [Formula: see text] does not contain a rainbow copy of [Formula: see text] and adding an edge of any color to [Formula: see text] creates a rainbow copy of [Formula: see text]. The rainbow saturation number [Formula: see text] is the minimum number of edges in an [Formula: see text]-vertex [Formula: see text]-rainbow saturated graph. Girão, Lewis, and Popielarz conjectured that [Formula: see text] for fixed [Formula: see text]. Disproving this conjecture, we establish that for every [Formula: see text], there exists a constant [Formula: see text] such that [Formula: see text] and [Formula: see text]. Recently, Behague, Johnston, Letzter, Morrison, and Ogden independently gave a slightly weaker upper bound which was sufficient to disprove the conjecture. They also introduced the weak rainbow saturation number and asked whether this is equal to the rainbow saturation number of [Formula: see text], since the standard weak saturation number of complete graphs equals the standard saturation number. Surprisingly, our lower bound separates the rainbow saturation number from the weak rainbow saturation number, answering this question in the negative. The existence of the constant [Formula: see text] resolves another of their questions in the affirmative for complete graphs. Furthermore, we show that the conjecture of Girão, Lewis, and Popielarz is true if we have an additional assumption that the edge-colored [Formula: see text]-rainbow saturated graph must be rainbow. As an ingredient of the proof, we study graphs which are [Formula: see text]-saturated with respect to the operation of deleting one edge and adding two edges.

We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound. In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound. It was previously known that there are Reed-Solomon codes that do not have this property. As an immediate corollary to our main theorem, we obtain better degree bounds on unbalanced expanders that come from Reed-Solomon codes.

We show that there exists an absolute constant $c > 0$, such that, for any finite set $A$ of quaternions, $\max\{|A+A|, |AA| \} \gtrsim |A|^{4/3 + c}.$ This generalizes a sum-product bound for real numbers proved by Konyagin and Shkredov.

We give improved lower bounds on the size of Kakeya and Nikodym sets over $\Bbb{F}_q^3$. We also propose a natural conjecture on the minimum number of points in the union of a not-too-flat set of lines in $\Bbb{F}_q^3$ and show that this conjecture implies an optimal bound on the size of a Nikodym set.

We prove three theorems giving extremal bounds on the incidence structures determined by subsets of the points and blocks of a balanced incomplete block design (BIBD). These results generalize and strengthen known bounds on the number of incidences between points and $m$-flats in affine geometries over finite fields. First, we show an upper bound on the number of incidences between sufficiently large subsets of the points and blocks of a BIBD. Second, we show that a sufficiently large subset of the points of a BIBD determines many $t$-rich blocks. Third, we show that a sufficiently large subset of the blocks of a BIBD determines many $t$-rich points. These last two results are new even in the special case of incidences between points and $m$-flats in an affine geometry over a finite field. As a corollary we obtain a tight bound on the number of $t$-rich points determined by a set of points in a plane over a finite field, and use it to sharpen a result of [A. Iosevich, M. Rudnev, and Y. Zhai Combinatorica, 35 (2012), pp. 295--308] on the number of triangles with distinct areas determined by a set of points in a plane over a finite field.

We introduce the bisector energy of an n-point set P in the real plane, defined as the number of quadruples (a,b,c,d) from P such that a and b determine the same perpendicular bisector as c and d. If no line or circle contains M(n) points of P, then we prove that the bisector energy is O(M(n)^{2/5}n^{12/5} + M(n)n^2). We also prove the lower bound M(n)n^2, which matches our upper bound when M(n) is large. We use our upper bound on the bisector energy to obtain two rather different results: (i) If P determines O(n / sqrt(log n)) distinct distances, then for any 0 < a < 1/4, either there exists a line or circle that contains n^a points of P, or there exist n^{8/5 - 12a/5} distinct lines that contain sqrt(log n) points of P. This result provides new information on a conjecture of Erdös regarding the structure of point sets with few distinct distances. (ii) If no line or circle contains M(n) points of P, then the number of distinct perpendicular bisectors determined by P is min{M(n)^{-2/5}n^{8/5}, M(n)^{-1}n^2}). This appears to be the first higher-dimensional example in a framework for studying the expansion properties of polynomials and rational functions over the real numbers, initiated by Elekes and Ronyai.