Browse Problems

The least common multiple bound implies $n_k \le \exp((1 + o(1))k)$.

Monier observed that $n_k \le k!$ for $k \ge 3$ ([Mo85]). TODO: Find reference

The initial values satisfy $n_2 = 4$, $n_3 = 6$, $n_4 = 9$, and $n_5 = 12$ ([Gu04], Problem B31).

Let $ϕ(n)$ be the Euler's totient function, then the $n$ satisfies $ϕ(n)>ϕ(n - ϕ(n))$ have asymptotic density 1. Reference: [LuPo02] Luca, Florian and Pomerance, Carl, On some problems of {M}\polhk akowski-{S}chinzel and …

For any function $f(n)=o(n)$, we have $\phi(n)>\phi(n-\phi(n))+f(n)$ for almost all $n$. Reference: [LuPo02] Luca, Florian and Pomerance, Carl, On some problems of {M}\polhk akowski-{S}chinzel and {E}rd\H os concerning the arithmetical functions {$\phi$} …

Let $ϕ(n)$ be the Euler's totient function, there exist infinitely many $n$ such that $ϕ(n)< ϕ(n - ϕ(n))$ Reference: [GLW01] Grytczuk, A. and Luca, F. and W\'ojtowicz, M., A conjecture of {E}rdős …

Are there infinitely many primes $p$ such that $p = 2^k * q + 1$ for some prime $q$ and $k ≥ 0$? This is mentioned as B46 in [Unsolved Problems in …

Are there infinitely many primes $p$ such that $p = 2^k 3^l q + 1$ for some prime $q$ and $k ≥ 0$, $l ≥ 0$?

Does every graph with chromatic number $\aleph_1$ contain an infinitely connected subgraph with chromatic number $\aleph_1$? Komjáth [Ko13] proved that it is consistent that the answer is no. This was improved by …

Thomassen [Th17] constructed a counterexample to the version which asks for infinite edge-connectivity (that is, to disconnect the graph requires deleting infinitely many edges).

Does every graph with chromatic number $\aleph_1$ contain a countable subgraph which is infinitely connected?

Let $f(n)$ be minimal such that any $f(n)$ points in $ℝ^2$, no three on a line, contain $n$ points which form the vertices of a convex $n$-gon. Prove that $f(n) = 2^{n-2} …

Can a finite set of disjoint unit segments in a unit square be maximal? Solved affirmatively by [Da85], who gave an explicit construction.

Is there a region $R$ with a maximal set of disjoint unit line segments that is countably infinite?

Is it true that there are infinitely many $p$ for which $f(p) = p − 1$?

Erdős, Hardy, and Subbarao [HaSu02], believed that the number of $p \le x$ for which $f(p)=p−1$ is $o(x/\log x)$. [HaSu02] Hardy, G. E. and Subbarao, M. V., _A modified problem of Pillai …

Is it true that $f(p)/p \to 0$ for $p \to \infty$ in a density 1 subset of the primes?

Is it true that $A(x) \le x^{o(1)}$?

Let $S$ be the set of all $m\geq 1$ such that there exists a prime $p\not\equiv 1\pmod{m}$ such that $m! + 1 \equiv 0\pmod{p}$. Does $$ \lim\frac{|S\cap[1, x]|}{x} $$ exist?

Let $S$ be the set of all $m\geq 1$ such that there exists a prime $p\not\equiv 1\pmod{m}$ such that $m! + 1 \equiv 0\pmod{p}$. What is $$ \lim\frac{|S\cap[1, x]|}{x}? $$

Similarly, if $P$ is the set of all primes $p$ such that there exists an $m$ with $p\not\equiv 1\pmod{m}$ such that $m! + 1 \equiv 0\pmod{p}$, then does $$ \lim\frac{|P\cap[1, x]|}{\pi(x)} $$ …

Similarly, if $P$ is the set of all primes $p$ such that there exists an $m$ with $p\not\equiv 1\pmod{m}$ such that $m! + 1 \equiv 0\pmod{p}$, then what is $$ \lim\frac{|P\cap[1, x]|}{\pi(x)}? …

Erdős, Hardy, and Subbarao proved that $S$ is infinite.

Regarding the first question, Hardy and Subbarao computed all EHS numbers up to $2^{10}$, and write "...if this trend conditions we expect [the limit] to be around 0.5, if it exists."

Erdős, Hardy, and Subbarao proved that $P$ is infinite.

We call a graph $D$-balanced (or $D$-almost-regular) if the maximum degree is at most $D$ times the minimum degree. Let $ε, α > 0$ and $D$ and $n$ be sufficiently large. If …

For every r ≥ 4 and k ≥ 2 is there some finite f(k,r) such that every graph of chromatic number ≥ f(k,r) contains a subgraph of girth ≥ r and chromatic …

Let $G$ be a bipartite graph on $n$ vertices such that one part has $\lfloor n^{2/3}\rfloor$ vertices. Is there a constant $c>0$ such that if $G$ has at least $cn$ edges then …

It is easy to check that $f_2(n) < 3n$.

Erdős conjectured that the triangular lattice is best possible in 2D, in particular that $f_2(3n^2 + 3n + 1) < 9n^2 + 3n$. Note: in [Er75f] is read $9n^2 + 6n$, but …

It is easy to check that $f_1(n) = n - 1$.

Erdős showed that there is some constant $c > 0$ such that $f_2(n) < 3n - c n^{1/2}$.

Erdős claims the existence of two constants $c_1, c_2 > 0$ such that $6n - c_1 n^{2/3} ≤ f_3(n) \le 6n - c_2 n^{2/3}$.

It is easy to check that $f_2(n) < 3n$.

Erdős conjectured that the triangular lattice is best possible in 2D, in particular that $f_2(3n^2 + 3n + 1) < 9n^2 + 3n$. Note: in [Er75f] is read $9n^2 + 6n$, but …

It is easy to check that $f_1(n) = n - 1$.

Erdős showed that there is some constant $c > 0$ such that $f_2(n) < 3n - c n^{1/2}$.

Erdős claims the existence of two constants $c_1, c_2 > 0$ such that $6n - c_1 n^{2/3} ≤ f_3(n) \le 6n - c_2 n^{2/3}$.

Erdős showed $f_2(n) > n^{1+c/\log\log n}$ for some $c > 0$.

Erdős showed $f_3(n) = Ω(n^{4/3}\log\log n)$.

Lenz showed that, for $d \ge 4$, $f_d(n) \ge \frac{p - 1}{2p} n^2 - O(1)$ where $p = \lfloor\frac d2\rfloor$.

Spencer, Szemerédi, and Trotter showed $f_2(n) = O(n^{4/3})$.

Is the $n^{4/3}\log\log n$ lower bound in 3D also an upper bound?.

Erdős showed that, for $d \ge 4$, $f_d(n) \le \left(\frac{p - 1}{2p} + o(1)\right) n^2$ where $p = \lfloor\frac d2\rfloor$.

Erdős and Pach showed that, for $d \ge 5$ odd, there exist constants $c_1(d), c_2(d) > 0$ such that $\frac{p - 1}{2p} n^2 - c_1 n^{4/3} ≤ f_d(n) \le \frac{p - 1}{2p} …

Erdős showed $f_2(n) > n^{1+c/\log\log n}$ for some $c > 0$.

Erdős showed $f_3(n) = Ω(n^{4/3}\log\log n)$.

Lenz showed that, for $d \ge 4$, $f_d(n) \ge \frac{p - 1}{2p} n^2 - O(1)$ where $p = \lfloor\frac d2\rfloor$.

Spencer, Szemerédi, and Trotter showed $f_2(n) = O(n^{4/3})$.

Is the $n^{4/3}\log\log n$ lower bound in 3D also an upper bound?.