For positive integersn, r, swithr>s, the setcoloring Ramsey numberR(n; r, s) is the minimumNsuch that if every edge of the complete graphKNreceives a set ofscolors from a palette ofrcolors, then there is a subset ofnvertices where all of the edges between them receive a common color. Ifnis fixed ands/ris less than and bounded away from 1 - 1/n-1, thenR(n; r, s) is known to grow exponentially in r, while ifs/ris greater than and bounded away from 1 - 1/n-1, thenR(n; r, s) is bounded. Here we prove bounds forR(n; r, s) in the intermediate range wheres/ris close to 1 - 1/n-1 by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.

For a fixed graph $H$, what is the smallest number of colors $C$ such that there is a proper edge-coloring of the complete graph $K_n$ with $C$ colors containing no two vertex-disjoint color-isomorphic copies, or repeats, of $H$? We study this function and its generalization to more than two copies using a variety of combinatorial, probabilistic, and algebraic techniques. For example, we show that for any tree $T$ there exists a constant $c$ such that any proper edge-coloring of $K_n$ with at most $c n^2$ colors contains two repeats of $T$, while there are colorings with at most $c' n^{3/2}$ colors for some absolute constant $c'$ containing no three repeats of any tree with at least two edges. We also show that for any graph $H$ containing a cycle there exist $k$ and $c$ such that there is a proper edge-coloring of $K_n$ with at most $c n$ colors containing no $k$ repeats of $H$, while for a tree $T$ with $m$ edges, a coloring with $o(n^{(m+1)/m})$ colors contains $\omega(1)$ repeats of $T$.

A celebrated result of Mantel shows that every graph on n vertices with $\lfloor n^2/4 \rfloor + 1$ edges must contain a triangle. A robust version of this result, due to Rademacher, says that there must, in fact, be at least $\lfloor n/2 \rfloor$ triangles in any such graph. Another strengthening, due to the combined efforts of many authors starting with Erdös, says that any such graph must have an edge which is contained in at least $n/6$ triangles. Following Mubayi, we study the interplay between these two results, that is, between the number of triangles in such graphs and their book number, the largest number of triangles sharing an edge. Among other results, Mubayi showed that for any $1/6 \leq \beta < 1/4$ there is $\gamma > 0$ such that any graph on $n$ vertices with at least $\lfloor n^2/4\rfloor + 1$ edges and book number at most $\beta n$ contains at least $(\gamma -o(1))n^3$ triangles. He also asked for a more precise estimate for $\gamma$ in terms of $\beta$. We make a conjecture about this dependency and prove this conjecture for $\beta = 1/6$ and for $0.2495 \leq \beta < 1/4$, thereby answering Mubayi's question in these ranges.

Let $$\ell _m$$ be a sequence of m points on a line with consecutive points of distance one. For every natural number n, we prove the existence of a red/blue-coloring of $${\mathbb {E}}^n$$ containing no red copy of $$\ell _2$$ and no blue copy of $$\ell _m$$ for any $$m \ge 2^{cn}$$ . This is best possible up to the constant c in the exponent. It also answers a question of Erdős et al. (J Comb Theory Ser A 14:341–363, 1973). They asked if, for every natural number n, there is a set $$K \subset {\mathbb {E}}^1$$ and a red/blue-coloring of $${\mathbb {E}}^n$$ containing no red copy of $$\ell _2$$ and no blue copy of K.

Suppose that $a$ and $d$ are positive integers with $a \geq 2$. Let $h_{a,d}(n)$ be the largest integer $t$ such that any set of $n$ points in $\mathbb{R}^d$ contains a subset of $t$ points for which all the nonzero volumes of the ${t \choose a}$ subsets of order $a$ are distinct. Beginning with Erdös in 1957, the function $h_{2,d}(n)$ has been closely studied and is known to be at least a power of $n$. We improve the best known bound for $h_{2,d}(n)$ and show that $h_{a,d}(n)$ is at least a power of $n$ for all $a$ and $d$.

For natural numbers d and t there exists a positive C such that if F is a family of nC semi-algebraic sets in Rd of description complexity at most t, then there is a subset F' of F of size $n$ such that either every pair of elements in F' intersect or the elements of F' are pairwise disjoint. This result, which also holds if the intersection relation is replaced by any semi-algebraic relation of bounded description complexity, was proved by Alon, Pach, Pinchasi, Radoicic, and Sharir and improves on a bound of 4n for the family F which follows from a straightforward application of Ramsey's theorem. We extend this semi-algebraic version of Ramsey's theorem to k-ary relations and give matching upper and lower bounds for the corresponding Ramsey function, showing that it grows as a tower of height k-1. This improves on a direct application of Ramsey's theorem by one exponential. We apply this result to obtain new estimates for some geometric Ramsey-type problems relating to order types and one-sided sets of hyperplanes. We also study the off-diagonal case, achieving some partial results.

Consider the following game between two players, Builder and Painter. Builder draws edges one at a time and Painter colors them in either red or blue, as each appears. Builder's aim is to force Painter to draw a monochromatic copy of a fixed graph G. The minimum number of edges which Builder must draw, regardless of Painter's strategy, in order to guarantee that this happens is known as the on-line Ramsey number $\tilde{r}(G)$ of G. Our main result, relating to the conjecture that $\tilde{r}(K_t)=o(({r(t)\atop2}))$, is that there exists a constant $c>1$ such that $\tilde{r}(K_t)\leq c^{-t}({r(t)\atop2})$ for infinitely many values of t. We also prove a more specific upper bound for this number, showing that there exists a positive constant c such that $\tilde{r}(K_t)\leq t^{-c\frac{\log t}{\log \log t}}4^t$. Finally, we prove a new upper bound for the on-line Ramsey number of the complete bipartite graph $K_{t,t}$.