r/ErdosTasks

If $A\subseteq \{1,\ldots,N\}$ with $|A|=n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ then $N \gg 2^{n}$.

If $A\subseteq \mathbb{N}$ has $\sum_{n\in A}\frac{1}{n}=\infty$ then must $A$ contain arbitrarily long arithmetic progressions?

Let $C\geq 0$. Is there an infinite sequence of $n_i$ such that $\lim_{i\to \infty}\frac{p_{n_i+1}-p_{n_i}}{\log n_i}=C$?

Is there a distinct covering system all of whose moduli are odd?

Let $A$ be the set of all odd integers $\geq 1$ not of the form $p+2^{k}+2^l$ (where $k,l\geq 0$ and $p$ is prime). Is the upper density of $A$ positive?

Is there some $k$ such that every large integer is the sum of a prime and at most $k$ powers of 2?

Is every large odd integer $n$ the sum of a squarefree number and a power of 2?

Let $A$ be an infinite set with no distinct $a,b,c \in A$ where $a \mid (b+c)$ and $b,c>a$. Does such an $A$ exist with $\liminf |A \cap \{1,\ldots,N\}| / N^{1/2} > 0$? Must $\sum_{n \in A} 1/n < \inf...

Let $A \subset \mathbb{N}$ and $B$ be the set of integers representable in exactly one way as the sum of two elements from $A$. Is it true that $|\{1,\ldots,N\} \setminus B| \gg_\epsilon N^{1/2-\epsil...

Is it true that $\sum_{n=1}^{\infty}(-1)^n\frac{n}{p_n}$ converges, where $p_n$ is the sequence of primes?

Are there infinitely many primes $p$ such that every even number $n\leq p-3$ can be written as a difference of primes $n=q_1-q_2$ where $q_1,q_2\leq p$?

We call $m$ practical if every integer $1 \leq n < m$ is the sum of distinct divisors of $m$. If $m$ is practical let $h(m)$ be such that $h(m)$ many divisors always suffice. Is it true that $h(n!)<(\...

If $G$ is an edge-disjoint union of $n$ copies of $K_n$ then is $\chi(G)=n$?

Let $f(n,k)$ be minimal such that every family of $n$-uniform sets with $|\mathcal{F}|\geq f(n,k)$ contains a $k$-sunflower. Is it true that $f(n,k) < c_k^n$ for some constant $c_k > 0$?

Can every triangle-free graph on $5n$ vertices be made bipartite by deleting at most $n^2$ edges?

Let $1\leq n_1<n_2<\cdots$ be an arbitrary sequence of integers, each with an associated residue class $a_i\pmod{n_i}$. Let $A$ be the set of integers $n$ such that for every $i$ either $n<n_i$ or $n\...

If $A\subseteq \mathbb{N}$ is such that $A+A$ contains all but finitely many integers then $\limsup 1_A\ast 1_A(n)=\infty$.

Let $h(N)$ be the maximum size of a Sidon set in $\{1,\ldots,N\}$. Is it true that, for every $\epsilon>0$, $h(N) = N^{1/2}+O_\epsilon(N^\epsilon)$?

Is there a set $A\subset\mathbb{N}$ with $|A\cap\{1,\ldots,N\}| = O(\log N)$ such that every large integer can be written as $p+a$ for some prime $p$ and $a\in A$?

Let $A\subset\mathbb{N}$ be such that every large integer can be written as $n^2+a$ for some $a\in A$ and $n\geq 0$. What is the smallest possible value of $\limsup |A\cap\{1,\ldots,N\}|/N^{1/2}$?

For all sufficiently large $N$, if $A\sqcup B=\{1,\ldots,2N\}$ is a partition into two equal parts, then there is some $x$ such that the number of solutions to $a-b=x$ with $a\in A$ and $b\in B$ is at...

Does there exist $B\subset\mathbb{N}$ which is not an additive basis, but for every set $A$ of Schnirelmann density $\alpha$ and every $N$, there exists $b\in B$ such that $|(A\cup (A+b))\cap \{1,\ldo...

Is there an infinite Sidon set $A\subset \mathbb{N}$ such that $|A\cap \{1,\ldots,N\}| \gg_\epsilon N^{1/2-\epsilon}$ for all $\epsilon>0$?

For what functions $g(N)\to \infty$ is it true that $|A\cap \{1,\ldots,N\}| \gg N^{1/2}/g(N)$ implies $\limsup 1_A\ast 1_A(n)=\infty$?

Let $A\subset\mathbb{N}$ be an infinite set such that the triple sums $a+b+c$ are all distinct (aside from trivial coincidences). Is it true that $\liminf |A\cap \{1,\ldots,N\}|/N^{1/3}=0$?

Let $M\geq 1$ and $N$ be sufficiently large. Is it true that for every Sidon set $A\subset \{1,\ldots,N\}$ there is another Sidon set $B\subset \{1,\ldots,N\}$ of size $M$ such that $(A-A)\cap(B-B)=\{...

If $A,B \subset \{1,\ldots,N\}$ are two Sidon sets with $(A-A)\cap(B-B)=\{0\}$, is it true that $\binom{|A|}{2} + \binom{|B|}{2} \leq \binom{f(N)}{2} + O(1)$ where $f(N)$ is the maximum Sidon set size...

Let $A\subset \{1,\ldots,N\}$ be a Sidon set. For any $\epsilon>0$, do there exist $M$ and $B\subset \{N+1,\ldots,M\}$ such that $A\cup B$ is a Sidon set of size at least $(1-\epsilon)M^{1/2}$?

Schoenberg proved that for every $c\in [0,1]$ the density of $\{ n\in \mathbb{N} : \phi(n)<cn\}$ exists. Let this density be denoted by $f(c)$. Is it true that there are no $x$ such that $f'(x)$ exist...

Is there an infinite set $A\subset \mathbb{N}$ such that for every $a\in A$ there is an integer $n$ with $\phi(n)=a$, and yet if $n_a$ is the smallest such integer then $n_a/a\to \infty$?

Is it true that for every $\epsilon>0$: $\max(|A+A|,|AA|)\gg_\epsilon |A|^{2-\epsilon}$?

Does every graph on $n$ vertices with $>\mathrm{ex}(n;C_4)$ edges contain $\gg n^{1/2}$ many copies of $C_4$?

For any graph $H$ is there some $c=c(H)>0$ such that every graph $G$ on $n$ vertices not containing $H$ as an induced subgraph contains a complete graph or independent set on $\geq n^c$ vertices?

If $G_1,G_2$ are two graphs with chromatic number $\aleph_1$ then must there exist a graph $G$ with chromatic number $4$ (or even $\aleph_0$) which is a subgraph of both?

Does every finite graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k\geq 2$?

Let $G$ be a graph with $n$ vertices and $kn$ edges, and $a_1<a_2<\cdots$ the lengths of cycles in $G$. Is $\sum 1/a_i$ minimised when $G$ is a complete bipartite graph?

Is there $A\subseteq \mathbb{N}$ such that $\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}$ exists and is $\neq 0$?

Is $\sum_{n\geq 2}\frac{1}{n!-1}$ irrational?

Let $\mathfrak{c}$ be the cardinality of the reals, $\beta$ any countable ordinal, and $2\leq n<\omega$. Is it true that $\mathfrak{c}\to (\beta, n)_2^3$?

Let $f(n)\to \infty$ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?

Is there a graph of chromatic number $\aleph_1$ with $\aleph_1$ vertices such that for all $\epsilon>0$, if $n$ is sufficiently large, every subgraph on $n$ vertices contains an independent set of siz...

If $R(k)$ is the diagonal Ramsey number, find $\lim_{k\to \infty}R(k)^{1/k}$.

Give a constructive proof that $R(k)>C^k$ for some constant $C>1$. Equivalently, explicitly construct a graph on $n$ vertices with no clique or independent set of size $\geq c\log n$.

Let $c>0$ and $f_c(n)$ be the maximal $m$ such that every graph with $n$ vertices and $\geq cn^2$ edges, where each edge is in at least one triangle, contains a book of size $m$. Is $f_c(n)>n^{\epsilo...

Let $G$ be a chordal graph on $n$ vertices (no induced cycles of length > 3). Can the edges of $G$ be partitioned into $n^2/6+O(n)$ many cliques?

Let $F(n)$ be maximal such that every graph on $n$ vertices contains a regular induced subgraph on at least $F(n)$ vertices. Prove that $F(n)/\log n\to \infty$.

The cycle set of a graph $G$ on $n$ vertices is $A\subseteq \{3,\ldots,n\}$ such that $G$ has a cycle of length $\ell$ iff $\ell \in A$. Let $f(n)$ count possible cycle sets. Prove $f(n)=o(2^n)$ and $...

Let $f(n)$ be minimal such that every graph on $n$ vertices with minimum degree $\geq f(n)$ contains a $C_4$. Is it true that $f(n+1)\geq f(n)$ for all large $n$?

Is it true that every subgraph of $Q_n$ (the $n$-dimensional hypercube) with $\geq (\frac{1}{2}+o(1))n2^{n-1}$ many edges contains a $C_4$?

Let $\epsilon >0$. Is it true that if $k$ is sufficiently large, then $R(G)>(1-\epsilon)^kR(k)$ for every graph $G$ with $\chi(G)=k$?

Does every set of $n$ distinct points in $\mathbb{R}^2$ determine $\gg n/\sqrt{\log n}$ many distinct distances?

Does every set of $n$ distinct points in $\mathbb{R}^2$ contain at most $n^{1+O(1/\log\log n)}$ many pairs which are distance 1 apart?