3 solved out of 7 shown (show only solved or open)
SOLVED - $500 If$f:\mathbb{N}\to \{-1,+1\}$then is it true that for every$C>0$there exist$d,m\geq 1$such that $\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert > C?$ The Erdős discrepancy problem. This is true, and was proved by Tao [Ta16], who also proved the more general case when$f$takes values on the unit sphere. In [Er81] it is further conjectured that $\max_{md\leq x}\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert \gg \log x.$ In [Er85c] Erdős also asks about the special case when$f$is multiplicative. OPEN -$500
Let $\alpha\in[0,1/2)$ and $n,t\geq 1$. Let $F^{(t)}(n,\alpha)$ be the largest $m$ such that we can $2$-colour the edges of the complete $t$-uniform hypergraph on $n$ vertices such that if $X\subseteq [n]$ with $\lvert X\rvert \geq m$ then there are at least $\alpha \binom{\lvert X\rvert}{t}$ many $t$-subsets of $X$ of each colour.

For fixed $n,t$ as we change $\alpha$ from $0$ to $1/2$ does $F^{(t)}(n,\alpha)$ increase continuously or are there jumps? Only one jump?

For $\alpha=0$ this is the usual Ramsey function. A conjecture of Erdős, Hajnal, and Rado (see [562]) implies that $F^{(t)}(n,0)\asymp \log_{t-1} n$ and results of Erdős and Spencer imply that $F^{(t)}(n,\alpha) \gg_\alpha (\log n)^{\frac{1}{t-1}}$ for all $\alpha>0$, and a similar upper bound holds for $\alpha$ close to $1/2$.

Erdős believed there might be just one jump, occcurring at $\alpha=0$.

Conlon, Fox, and Sudakov [CFS11] have proved that, for any fixed $\alpha>0$, $F^{(3)}(n,\alpha) \ll_\alpha \sqrt{\log n}.$ Coupled with the lower bound above, this implies that there is only one jump for fixed $\alpha$ when $t=3$, at $\alpha=0$.

For all $\alpha>0$ it is known that $F^{(t)}(n,\alpha)\gg_t (\log n)^{c_\alpha}.$ See also [563].

OPEN
Let $\alpha>0$ and $n\geq 1$. Let $F(n,\alpha)$ be the largest $k$ such that in any 2-colouring of the edges of $K_n$ any subgraph $H$ on at least $k$ vertices contains more than $\alpha\binom{\lvert H\rvert}{2}$ many edges of each colour.

Prove that for every fixed $0\leq \alpha \leq 1/2$, as $n\to\infty$, $F(n,\alpha)\sim c_\alpha \log n$ for some constant $c_\alpha$.

It is easy to show with the probabilistic method that there exist $c_1(\alpha),c_2(\alpha)$ such that $c_1(\alpha)\log n < F(n,\alpha) < c_2(\alpha)\log n.$
OPEN
Let $N(k,\ell)$ be the minimal $N$ such that for any $f:\{1,\ldots,N\}\to\{-1,1\}$ there must exist a $k$-term arithmetic progression $P$ such that $\left\lvert \sum_{n\in P}f(n)\right\rvert\geq \ell.$ Find good upper bounds for $N(k,\ell)$. Is it true that for any $c>0$ there exists some $C>1$ such that $N(k,ck)\leq C^k?$ What about $N(k,2)\leq C^k$ or $N(k,\sqrt{k})\leq C^k?$
Spencer [Sp73] has proved that if $k=2^tm$ with $m$ odd then $N(k,1)=2^t(k-1)+1.$ Erdős and Graham write that 'no decent bound' is known even for $N(k,2)$. Probabilistic methods imply that, for every fixed constant $c>0$, we have $N(k,ck)>C_c^k$ for some $C_c>1$.
OPEN
Find the smallest $h(d)$ such that the following holds. There exists a function $f:\mathbb{N}\to\{-1,1\}$ such that, for every $d\geq 1$, $\max_{P_d}\left\lvert \sum_{n\in P_d}f(n)\right\rvert\leq h(d),$ where $P_d$ ranges over all finite arithmetic progressions with common difference $d$.
Cantor, Erdős, Schreiber, and Straus [Er66] proved that $h(d)\ll d!$ is possible. Van der Waerden's theorem implies that $h(d)\to \infty$. Beck [Be17] has shown that $h(d) \leq d^{8+\epsilon}$ is possible for every $\epsilon>0$. Roth's famous discrepancy lower bound [Ro64] implies that $h(d)\gg d^{1/2}$.
Let $A_1,A_2,\ldots$ be an infinite collection of infinite sets of integers, say $A_i=\{a_{i1}<a_{i2}<\cdots\}$. Does there exist some $f:\mathbb{N}\to\{-1,1\}$ such that $\max_{m, 1\leq i\leq d} \left\lvert \sum_{1\leq j\leq m} f(a_{ij})\right\rvert \ll_d 1$ for all $d\geq 1$?
Erdős remarks 'it seems certain that the answer is affirmative'. This was solved by Beck [Be81]. Recently Beck [Be17] proved that one can replace $\ll_d 1$ with $\ll d^{4+\epsilon}$ for any $\epsilon>0$.
Let $z_1,z_2,\ldots \in [0,1]$ be an infinite sequence, and define the discrepancy $D_N(I) = \#\{ n\leq N : z_n\in I\} - N\lvert I\rvert.$ Must there exist some interval $I\subseteq [0,1]$ such that $\limsup_{N\to \infty}\lvert D_N(I)\rvert =\infty?$
The answer is yes, as proved by Schmidt [Sc68], who later showed [Sc72] that in fact this is true for all but countably many intervals of the shape $[0,x]$.
Essentially the best possible result was proved by Tijdeman and Wagner [TiWa80], who proved that, for almost all intervals of the shape $[0,x)$, we have $\limsup_{N\to \infty}\frac{\lvert D_N([0,x))\rvert}{\log N}\gg 1.$