Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
If \(A\subseteq\{1, ..., 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. \] This conjecture is false. A machine-checked disproof constructs sum-distinct sets…
Can the smallest modulus of a covering system be arbitrarily large? This problem has a negative answer: there is a universal bound on the least modulus of any distinct covering system.
Is the set of odd integers not of the form \(2^k+p\) the union of an infinite arithmetic progression and a set of density \(0\)? Erdős called this conjecture "rather silly". Chen [Ch23] has proved the answer is no. This was formalized in…
Let \(A\subset\mathbb{N}\) be infinite such that \(\sum_{a \in A} \frac{1}{a} = \infty\). Must there exist some \(k\geq 1\) such that almost all integers have a divisor of the form \(a+k\) for some \(a\in A\)? This was formalized in Lean…
For any permutation \(\pi\in S_n\) of \(\{1,\ldots,n\}\) let \(S(\pi)\) count the number of distinct consecutive sums, that is, sums of the shape \(\sum_{u\leq i\leq v}\pi(i)\). Is it true that \[ S(\pi) = o(n^2) \] for all \(\pi\in S_n\)?…
If \(A\) and \(B\) are Sidon sets in \(\{1,\ldots,N\}\) with \((A-A)\cap(B-B)=\{0\}\), is it true that \[\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1)?\] The answer is no; the Erdős Problems page notes that…
Suppose \(A \subseteq \{1,\dots,N\}\) is such that there are no \(k+1\) elements of \(A\) which are relatively prime. An example is the set of all multiples of the first \(k\) primes. Is this the largest such set? To avoid trivial…
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? The answer is no. A machine-checked…
unit distance problem
Does every set of \(n\) distinct points in \(\mathbb{R}^2\) contain at most \(n^{1+O(\frac{1}{\log\log n})}\) many pairs which are distance \(1\) apart? This was…
Let \(A,B\subset \mathbb{R}^2\) be disjoint sets of size \(n\) and \(n-3\) respectively, with not all of \(A\) contained on a single line. Is there a line which contains at least two points from \(A\) and no points from \(B\)? This has…
If \(G\) is bipartite then \(\mathrm{ex}(n;G)\ll n^{3/2}\) if and only \(G\) is \(2\)-degenerate, that is, \(G\) contains no induced subgraph with minimal degree at least 3. Conjectured by Erdős and Simonovits [ErSi84]. Erdős first offered…
Let \(F_{k}(N)\) be the size of the largest \(A\subseteq \{1,\ldots,N\}\) such that the product of no \(k\) many distinct elements of \(A\) is a square. Is \(F_5(N)=(1-o(1))N\)? Conjectured by Erdős, Sós, and Sárközy [ESS95], who proved…
Let \(A\) be the set of integers which have only the digits \(0, 1\) when written base 3, -/ local notation "A" => { x : ℕ | (digits 3 x).toFinset ⊆ {0, 1} } /-- and \(B\) be the set of integers which have only the digits \(0, 1\) when…
Let \(f(n)\) be minimal such that every triangle-free graph \(G\) with \(n\) vertices and diameter \(2\) contains a vertex with degree \(\geq f(n)\). What is the order of growth of \(f(n)\)? Does \(f(n)/\sqrt{n}\to \infty\)? Asked by Erdős…
If \(H\) is bipartite and is \(r\)-degenerate, that is, every induced subgraph of \(H\) has minimum degree \(\leq r\), then \[\mathrm{ex}(n;H) \ll n^{2-1/r}.\] The answer is no. OpenAI [OpenAI26] give a connected bipartite 2-degenerate H…
If \(H\) is bipartite with minimum degree \(r\) then there exists \(\epsilon=\epsilon(H)>0\) such that \[\mathrm{ex}(n;H) \gg n^{2-\frac{1}{r-1}+\epsilon}.\] Conjectured by Erdős and Simonovits [ErSi84]. A probabilistic argument shows that…
If \(\mathcal{F}\) is a finite set of finite graphs then \(\mathrm{ex}(n;\mathcal{F})\) is the maximum number of edges a graph on \(n\) vertices can have without containing any subgraphs from \(\mathcal{F}\). Note that it is trivial that…
If \(\mathbb{R}^2\) is finitely coloured then must there exist some colour class which contains the vertices of a rectangle of every area? Graham, "On Partitions of 𝔼ⁿ", Journal of Combinatorial Theory, Series A 28, 89-91 (1980). (See…
Let \(S \subseteq \mathbb{Z}^3\) be a finite set and let \(A = \lbrace a_1, a_2, \ldots \rbrace\) be an infinite \(S\)-walk, so that \(a_{i+1} - a_i \in S\) for all \(i\). Must \(A\) contain three collinear points? Cambie and Kalviainen…
Let \(k\geq 3\). Must any ordering of \(\mathbb{R}\) contain a monotone \(k\)-term arithmetic progression, that is, some \(x_1 <\cdots < x_k\) which forms an increasing or decreasing \(k\)-term arithmetic progression? The answer is no,…
Let \(V\) be a vector space over the rationals and let \(k\) be a fixed positive integer. Then there is a set \(X_k \subseteq V\) such that \(X_k\) meets every infinite arithmetic progression in \(V\) but \(X_k\) intersects every…
If \(A\subset \mathbb{R}\) does not contain a 3-term arithmetic progression then must \(\mathbb{R}\backslash A\) contain an infinite arithmetic progression? Baumgartner [Ba75] answered this in the negative.
Are there \(n\) such that there is a covering system with moduli the divisors of \(n\) which is 'as disjoint as possible'? That is, for all \(d\mid n\) with \(d>1\) there is an associated \(a_d\) such that every integer is congruent to…
Is it true that all sufficiently large \(n\) can be written as \(2^k+m\) for some \(k\geq 0\), where \(\Omega(m)<\log\log m\)? (Here \(\Omega(m)\) is the number of prime divisors of \(m\) counted with multiplicity.) Barreto and Leeham,…
Let \(x>0\) be a real number. For any \(n\geq 1\) let \[R_n(x) = \sum_{i=1}^n\frac{1}{m_i}<x\] be the maximal sum of \(n\) distinct unit fractions which is \(<x\). Is it true that, for almost all \(x\), for sufficiently large \(n\), we…
Let \(A\) be a finite collection of \(d\geq 4\) non-parallel lines in \(\mathbb{R}^2\) such that there are no points where at least four lines from \(A\) meet. Must there exist a 'Gallai triangle' (or 'ordinary triangle'): three lines from…
Let \(P(z)=\sum_{1\leq k\leq n}a_kz^k\) for some \(a_k\in \mathbb{C}\) with \(\lvert a_k\rvert=1\) for \(1\leq k\leq n\). Does there exist a constant \(c>0\) such that, for \(n\geq 2\), we have \[\max_{\lvert z\rvert=1}\lvert P(z)\rvert…
Let \(S\) be a string of length \(2^k-1\) formed from an alphabet of \(k\) characters. Must \(S\) contain an abelian square: two consecutive blocks \(x\) and \(y\) such that \(y\) is a permutation of \(x\)? Erdős initially conjectured that…
Let \(a_1 < a_2 < \dotsc\) be an infinite sequence of positive integers such that \(\frac{a_{i+1}}{a_i} \to 1\). If every arithmetic progression contains infinitely many integers which are the sum of distinct \(a_i\) then every…
Let \(a_n\) be an infinite sequence of positive integers such that \(\sum \frac{1}{a_n}\) converges. There exists some integer \(t \ge 1\) such that \(\sum \frac{1}{a_n + t}\) is irrational. This was disproven by Kovač and Tao in [KoTa24].…
Let \(f(n)\to \infty\) as \(n\to \infty\). Is it true that \[\sum_{n\geq 1} \frac{1}{(n+1)\cdots (n+f(n))}\] is irrational? Erdős and Graham [ErGr80] write 'the answer is almost surely in the affirmative if \(f(n)\) is assumed to be…
Let \(n_1<n_2<\cdots \) be an infinite sequence of integers with associated \(a_k\pmod{n_k}\), such that for some \(\epsilon>0\) we have \(n_k>(1+\epsilon)k\log k\) for all \(k\). Then \[ \#\{ m<n_k : m\not\equiv a_i\pmod{n_i} \textrm{ for…
Is there an infinite sequence \(a_1 < a_2 < \dots\) such that \(a_{i+1} - a_i = O(1)\) and no finite sum of \(\frac{1}{a_i}\) is equal to 1? There does not exist such a sequence, which follows from the positive solution to…
Let \(N\geq 1\). How many integers can be written as the sum of distinct unit fractions with denominators from \(\{1,\ldots,N\}\)? Are there \(o(\log N)\) such integers? If the number of such integers is \(N(n)\) then it is trivial that…
Is it true that if \(A \subseteq \mathbb{N}\setminus\{1\}\) is a finite set with \(\sum_{n \in A} \frac{1}{n} < 2\) then there is a partition \(A=A_1 \sqcup A_2\) such that \(\sum_{n \in A_i} \frac{1}{n} < 1\) for \(i=1,2\)? This is not…
Suppose \(A\subseteq\mathbb{N}\) and \(C>0\) is such that \(1_A\ast 1_A(n)\leq C\) for all \(n\in\mathbb{N}\). Can \(A\) be partitioned into \(t\) many subsets \(A_1,\ldots,A_t\) (where \(t=t(C)\) depends only on \(C\)) such that…
Let \(A,B\subseteq \mathbb{N}\) such that for all large \(N\[\)\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}\]and\[\lvert B\cap \{1,\ldots,N\}\rvert \gg N^{1/2}.\] Is it true that there are infinitely many solutions to…
Let \(A\subseteq \mathbb{N}\) be a set of density zero. Does there exist a \(B\) such that \(A\subseteq B+B\) and \[\lvert B\cap \{1,\ldots,N\}\rvert =o(N^{1/2})\] for all large \(N\)? The answer is no. Erdős and Newman [ErNe77] have…
Let \(A\subseteq \mathbb{N}\) be an additive basis (of any finite order) such that \(\lvert A\cap \{1,\ldots,N\}\rvert=o(N)\). Is it true that \[ \lim_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert} {\lvert A\cap…
Is it true that, for each fixed \(n\) and fixed sizes \(k_1,\ldots,k_n \geq 4\), there are only finitely many collections of disjoint intervals \(I_1,\ldots,I_n\) of size \(\lvert I_i\rvert = k_i\) for \(1\leq i\leq n\) such…
Are there only finitely many solutions to \[ \prod_i \binom{2m_i}{m_i}=\prod_j \binom{2n_j}{n_j} \] with the \(m_i,n_j\) distinct? Somani, using ChatGPT, has given a negative answer. In fact, for any \(a\geq 2\), if \(c=8a^2+8a+1\),…
Is it true that there are no solutions to n! = x^k ± y^k with x,y,n ∈ ℕ, x*y > 1, and k > 2? The answer is no: Jonas Barfield found the counterexample 10! = 48^4 - 36^4 (equivalently, 10! + 36^4 = 48^4). This is discussed in problem D2 of…
We say \(H\) is a unique subgraph of \(G\) if there is exactly one way to find \(H\) as a subgraph (not necessarily induced) of \(G\). Is there a graph on \(n\) vertices with \[\gg \frac{2^{\binom{n}{2}}}{n!}\] many distinct unique…
Is it true that, if \(A\subseteq \mathbb{N}\) is sparse enough and does not cover all residue classes modulo \(p\) for any prime \(p\), then there exists some \(n\in \mathbb{Z}\) such that \(n+a\) is prime for all \(a\in A\)? Weisenberg…
Let \(N\geq 1\). What is the size of the largest \(A\subset \{1,\ldots,N\}\) such that \([a,b]\leq N\) for all \(a,b\in A\), where \([a,b]\) is the least common multiple of \(a\) and \(b\)? Is it attained by choosing all integers in…
Let \(\operatorname{Log} x := \max\{\log x, 1\}\), \(\operatorname{Log}_2x = \operatorname{Log} (\operatorname{Log} x)\), and \(\operatorname{Log}_3x = \operatorname{Log}(\operatorname{Log}(\operatorname{Log} x)).\) Is it true that if…
Let \(\tau(n)\) count the divisors of \(n\) and \(\tau^+(n)\) count the number of \(k\) such that \(n\) has a divisor in \([2^k, 2^{k+1})\). Is it true that, for all \(\epsilon > 0\), \[ \tau^+(n) < \epsilon \cdot \tau(n) \] for almost all…
Is it true that, for all sufficiently large \(n\), there exists some \(i<n\) such that \[ p_n^2 < p_{n+i}p_{n-i}, \] where \(p_k\) is the \(k\)th prime? Pomerance proved that the answer is no.
Borsuk's problem
**Erdős Problem 505** (disproved). Borsuk's conjecture is false for sufficiently large \(n\): there exists a dimension \(n\) and a bounded set \(S \subseteq \mathbb{R}^n\) with at least two points that cannot be covered by \(n + 1\)…
Let \(\delta > 0\). If \(n\) is sufficiently large and \(G\) is a graph on \(n\) vertices with no \(K_5\) and at least \(\delta n^2\) edges, must \(G\) contain a set of \(\gg_\delta n\) vertices spanning no triangle? Equivalently, writing…
Let \(\epsilon>0\) and \(N\) be sufficiently large. If \(A\subseteq \{1,\ldots,N\}\) has \(\lvert A\rvert \geq \epsilon N\) then must there exist \(a_1,a_2,a_3\in A\) and distinct primes \(p_1,p_2,p_3\) such that \[a_1p_1=a_2p_2=a_3p_3?\]…
If \(T\) is a tree which is a bipartite graph with \(k\) vertices in one class and \(2k\) vertices in the other class then \[R(T)=4k-1.\] This is false: Norin, Sun, and Zhao [NSZ16] have proved that if \(T\) is the union of two stars on…
Let \(\hat{R}(G)\) denote the size Ramsey number, the minimal number of edges \(m\) such that there is a graph \(H\) with \(m\) edges that is Ramsey for \(G\). If \(G\) has \(n\) vertices and maximum degree \(d\) then prove that…
Is there a covering system such that no two of the moduli divide each other? Asked by Schinzel, motivated by a question of Erdős and Selfridge (see [7](https://www.erdosproblems.com/7)). The answer is no, as proved by Balister, Bollobás,…
**Erdős Problem 613:** Let \(n \geq 3\) and \(G\) be a graph with \(\binom{2n+1}{2} - \binom{n}{2} - 1\) edges. Must \(G\) be the union of a bipartite graph and a graph with maximum degree less than \(n\)?
Does there exist some constant \(c > 0\) such that for all sufficiently large \(n\), if \(G\) is a graph with \(n\) vertices and at least \((1/8 - c)n^2\) edges then \(G\) must contain either a \(K_4\) or an independent set on at least…
Is there some function \(f\) such that for all \(k\geq 1\) if a finite graph \(G\) has chromatic number \(\geq f(k)\) then \(G\) has \(k\) edge disjoint cycles on the same set of vertices? A problem of Erdős and Hajnal. This was resolved…
Let \(P(m)\) denote the greatest prime factor of \(m\). Is it true that, for any two primes \(p,q\), there exists some integer \(n\) such that \(P(n)=p\) and \(P(n+1)=q\)? In fact, the answer to this question as written is easily seen to…
Let \(c<1\) be some constant and \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) be such that \(\lvert A_i\rvert >c\sqrt{n}\) for all \(i\) and \(\lvert A_i\cap A_j\rvert\leq 1\) for all \(i\neq j\). Must there exist some set \(B\) such that…
Let \(Q_n\) be the \(n\)-dimensional hypercube graph (so that \(Q_n\) has \(2^n\) vertices and \(n2^{n-1}\) edges). Is it true that, for every \(\epsilon>0\), if \(n\) is sufficiently large, every subgraph of \(Q_n\) with \[\geq \epsilon…
Let \(\delta_1(n,m)\) be the density of the set of integers with exactly one divisor in \((n,m)\). Is \(\delta_1(n,m)\) unimodular for \(m>n+1\) (i.e. increases until some \(m\) then decreases thereafter)? Cambie has calculated that…
Let \(G\) be a finite unit distance graph in \(\mamthbb{R}^2\). Is there some \(k\) such that if \(G\) has girth \(≥ k\), then \(\chi(G) ≤ 3\)? The general case was solved by O'Donnell [OD99], who constructed finite unit distance graphs…
**Erdős Problem 707**: It is false that any finite Sidon set can be embedded in a perfect different set modulo some \(n\). As described in [arxiv/2510.19804], a counterexample is provided in [Ha47], see below. The proof of this has been…
Let \(G\) be a graph with chromatic number \(\chi(G)=4\). If \(m_1<m_2<\cdots\) are the lengths of the cycles in \(G\) then can \(\min(m_{i+1}-m_i)\) be arbitrarily large? The answer is no: Bondy and Vince [BoVi98] proved that every graph…
The list chromatic number \(\chi_L(G)\) is defined to be the minimal \(k\) such that for any assignment of a list of \(k\) colours to each vertex of \(G\) (perhaps different lists for different vertices) a colouring of each vertex by a…
The cochromatic number of \(G\), denoted by \(\zeta(G)\), is the minimum number of colours needed to colour the vertices of \(G\) such that each colour class induces either a complete graph or empty graph. Is it true that if \(G\) has no…
Let \(A\subseteq \mathbb{N}\). Can there exist some constant \(c>0\) such that \[\sum_{n\leq N} 1_A\ast 1_A(n) = cN+O(1)?\] A conjecture of Erdős and Turán. Erdős and Fuchs [ErFu56] proved that the answer is no in a strong form: in fact…
Let \(A\subseteq \mathbb{N}\). Can there exist some constant \(c>0\) such that \[\sum_{n\leq N} 1_A\ast 1_A\ast 1_A(n) = cN+O(1)?\] The case of \(1_A\ast 1_A(n)\) is the subject of [763](https://www.erdosproblems.com/763). The answer is…
Is there a \(3\)-uniform hypergraph on \(n\) vertices which contains at least \(n-O(1)\) different sizes of cliques (maximal complete subgraphs)? The answer is no, as proved by Gao [Ga25]: more generally, for any \(k\geq 3\), every…
Let \(f(k)\) be the minimal \(n\) such that any \(2\)-colouring of \(\{1,\ldots,n\}\) contains a monochromatic \(k\)-term descending wave: a sequence \(x_1<\cdots <x_k\) such that, for \(1<j<k\), \[x_j \geq \frac{x_{j+1}+x_{j-1}}{2}.\]…
Is it true that every \(3\)-uniform hypergraph on \(3n\) vertices with at least \(n^3+1\) edges must contain either a subgraph on \(4\) vertices with \(3\) edges or a subgraph on \(5\) vertices with \(7\) edges? Harris has provided the…
We call a graph \(H\) \(D\)-balanced (or \(D\)-almost-regular) if the maximum degree of \(H\) is at most \(D\) times the minimum degree of \(H\). Is it true that for every \(m\geq 1\), if \(n\) is sufficiently large, any graph on \(n\)…
Let \(f(m,n)\) be maximal such that any graph on \(n\) vertices in which every induced subgraph on \(m\) vertices has an independent set of size at least \(\log n\) must contain an independent set of size at least \(f(n)\). Estimate…
Let \(r\geq 3\) and \(k\) be sufficiently large in terms of \(r\). Is it true that every \(r\)-uniform hypergraph with chromatic number \(k\) has at least \[\binom{(r-1)(k-1)+1}{r}\] edges, with equality only for the complete graph on…
Let \(C > 0\). Is it true that the set of integers of the form \(n = b_1 + \cdots + b_t\), with \(b_1 < \cdots < b_t\), where \(b_i = 2^{k_i}3^{l_i}\) for \(1 \leq i\leq t\) and \(b_t \leq Cb_1\) has density \(0\)? van Doorn and Everts…
**Erdős Problem 846** Let A ⊂ ℝ² be an infinite set for which there exists some ϵ>0 such that in any subset of A of size n there are always at least ϵn with no three on a line. Is it true that A is the union of a finite number of sets…
Let \(A \subset \mathbb{N}\) be an infinite set for which there exists some \(\epsilon > 0\) such that in any subset of \(A\) of size \(n\) there is a subset of size at least \(\epsilon n\) which contains no three-term arithmetic…
Is it true that if \(A=\{a_1<\cdots <a_t\}\subseteq \{1,\ldots,N\}\) has no solutions to \[a_i+a_{i+1}+\cdots+a_j\in A\] then \[\lvert A\rvert \leq \frac{N}{2}+O(1)?\] In fact this problem is false. Freud [Fr93] constructed a sequence with…
If \(A_1, A_2\) are disjoint additive bases of order \(2\) (i.e. \(A_i + A_i\) contains all large integers) then must \(A = A_1 \cup A_2\) contain a minimal additive basis of order \(2\) (one such that deleting any element creates…
Let \(A\) be an additive basis of order \(2\), and suppose \(1_A\ast 1_A(n)\to \infty\) as \(n\to \infty\). Can \(A\) be partitioned into two disjoint additive bases of order \(2\)? A question of Erdős and Nathanson [ErNa88], who proved…
For a natural number n, let \(1 = d_1 < \dotsc < d_{\tau(n)} = n\) denote the divisors of \(n\) in increasing order. Does it hold that…
Let \(f(n)\) be an additive function (so that \(f(ab)=f(a)+f(b)\) if \((a,b)=1\) such that \(\limsup_{p,k} f(p^k) / \log(p^k) = ∞\). Is it true that \(\limsup_n (f(n+1)−f(n))/ \log n = ∞\)? The answer is no; this follows from a…
Let \(g(n)\) be the maximum number of different sizes of cliques that can occur in a graph on \(n\) vertices. Estimate \(g(n)\) - in particular, is it true that \[g(n) = n - \log_2 n - \log_*(n) + O(1),\] where \(\log_*(n)\) is the number…
Let \(A\subset \mathbb{R}^2\) be a finite set of size \(n\), and let \(\{d_1,\ldots,d_k\}\) be the set of distances determined by \(A\). Let \(f(d)\) be the multiplicity of \(d\), that is, the number of unordered pairs from \(A\) of…
Erdős asks in [Er75b] if for every 2-coloring of ℝ, there is an uncountable set \(A ⊆ ℝ\) such that all sums \(a + b\) for \(a, b ∈ A, a ≠ b\) have the same colour. In [Ko16] Péter Komjáth constructed a counterexample. The same result was…
Let \(1<a_1<\cdots\) be a sequence of integers such that \(\sum\frac{1}{a_i}<\infty\). Is it true that, for every \(t\in \mathbb{R}\), \[1+\sum_{k}\frac{1}{a_k^{1+it}}\neq 0?\] Yip [Yi25] has proved that this is not always true - in fact,…
Let \(f=a_0+\cdots+a_dx^d\in \mathbb{C}[x]\) be a polynomial. Is it true that, if \(f\) has roots \(z_1,\ldots,z_d\) with corresponding arguments \(\theta_1,\ldots,\theta_d\in [0,2\pi]\), then for all intervals \(I\subseteq [0,2\pi]\) \[…
Let \(E\subseteq (0,1)\) be a meaurable subset with Lebesgue measure \(\lambda(E)\). Is it true that, for almost all \(\alpha\), \[\lim_{n\to \infty}\frac{1}{n}\sum_{1\leq k\leq n}1_{\{k\alpha \}\in E}=\lambda(E)\] for all \(E\)? This is a…
Let \(G\) be a graph on \(n\) vertices with \(>n^2/4\) many edges. Must there be a triangle \(T\) in \(G\) and vertices \(y_1,\ldots,y_t\), where \(t>(\frac{1}{2}-o(1))n\), such that every \(y_i\) is joined to at least two vertices of…
Let \(G\) be a graph on \(n\) vertices in which every degree occurs at most twice, and the number of distinct degrees is \(>(\frac{1}{2}+\epsilon)n\). Must \(G\) contain a trivial (empty or complete) subgraph of size 'much larger' than…
**Erdős Problem 1043**: Let \(f\in \mathbb{C}[x]\) be a monic polynomial. Must there exist a straight line \(\ell\) such that the projection of \[\{ z: \lvert f(z)\rvert\leq 1\}\] onto \(\ell\) has measure at most \(2\)? Pommerenke [Po61]…
Let \(f\in \mathbb{C}[x]\) be a monic polynomial and \[E=\{ z: \lvert f(z)\rvert <1\}.\] If \(E\) is connected then is \(E\) contained in a disc of radius \(2\)? A problem of Erdős, Herzog, and Piranian [EHP58], who also ask, if…
Let \(f\in \mathbb{C}[x]\) be a monic polynomial with \(m\) distinct roots, and let \(c>0\) be a constant small enough such that \(\{ z: \lvert f(z)\rvert\leq c\}\) has \(m\) distinct connected components. Must all these components be…
If \(f\in \mathbb{C}[x]\) is a monic polynomial with all roots satisfying \(\lvert z\rvert \leq r\) for some \(0 < r < 2\), then must \[\{ z: \lvert f(z)\rvert <1\}\] have a connected component with diameter \(>2-r\)? A problem of Erdős,…
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 Soukup [So15], who…
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 \(G\) is a graph on \(n\) vertices with at least…
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 \(G\) must contain a \(C_6\)? The answer is no, as…
Is it true that \(f_2(n) \gg n\)? Disproved by Rödl, who showed \(f_r(n) = o(n)\) for all fixed \(r \geq 2\). A conjecture of Erdős, Hajnal, and Szemerédi. This seems to be closely related to, but distinct from,…
**Prikry–Mills counterexample** (key lemma): There exists a 2-colouring \(f\) of a set of cardinality \(\aleph_1\) cubed such that no countable box \(A_1 \times B_1 \times C_1\) is monochromatic. This is the unpublished result of Prikry…
Let \(A\subseteq \mathbb{N}\) be the smallest set which contains \(1\) and is closed under the operations \[x\mapsto 2x+1,\quad x\mapsto 3x+1,\quad x\mapsto 6x+1.\] Does \(A\) have positive lower density? Lagarias [La16] reports that Erdős…
**Erdős Problem 1138.** Let \(x/2 < y < x\) and \(C > 1\). If \(d = \max_{p_n < x}(p_{n+1} - p_n)\), where \(p_n\) denotes the \(n\)-th prime, then is it true that \[\pi(y + Cd) - \pi(y) \sim \frac{Cd}{\log y}\]?
Are there infinitely many \(n\) such that \(n-k^2\) is prime for all \(k\) with \((n,k)=1\) and \(k^2 < n\)? In [Va99] it is asked whether \(968\) is the largest integer with this property, but this is an error, since for example…
Let \(\alpha>0\) be an irrational number. Is the set \[A=\left\{ n\geq 1: \| \alpha n^2\| < \frac{1}{\log n}\right\},\] where \(\|\cdot\|\) denotes the distance to the nearest integer, an additive basis of order \(2\)? This was disproved…
Let \(E\subset (0,\infty)\) be a set of positive measure. Is it true that, for almost all \(x>0\), for all sufficiently large (depending on \(x\)) integers \(n\) there exists an integer \(r\geq 1\) such that \(nx\in r\cdot E\)? A problem…
If \(\mathbb{N}\) is \(2\)-coloured, must there exist an infinite set \(A=\{a_1<a_2<\cdots\}\) such that all expressions of the shape \[\sum_{j=1}^{k}\prod_{i\in S_j}a_i,\] for \(k\geq 1\) and pairwise disjoint nonempty finite sets of…