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.
sunflower conjecture
Is it true that \(f(n,k) < c_k^n\) for some constant \(c_k>0\) and for all \(n > 0\)?
Let \(f(n)\) be minimal such that there is an intersecting family \(\mathcal{F}\) of sets of size \(n\) (so \(A\cap B\neq\emptyset\) for all \(A,B\in \mathcal{F}\)) with \(\lvert \mathcal{F}\rvert=f(n)\) such that any set \(S\) with…
Suppose that we have a family \(\mathcal{F}\) of subsets of \([4n]\) such that \(\lvert A\rvert=2n\) for all \(A\in\mathcal{F}\) and for every \(A,B\in \mathcal{F}\) we have \(\lvert A\cap B\rvert \geq 2\). Then \[\lvert \mathcal{F}\rvert…
Erdős similarity problem
Let \(A \subseteq \mathbb{R}\) be an infinite set. Must there be a set \(E \subseteq \mathbb{R}\) of positive measure which does not contain any set of the shape \(a * A + b\) for some \(a,b \in \mathbb{R}\) and \(a \neq 0\)?
Let \(\alpha\in[0,1/2)\) and \(n,t\geq 1\). Let \(F^{(t)}(n,\alpha)\) be the smallest \(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…
Let \(\alpha > 0\) and \(n \geq 1\). Let \(F(n,\alpha)\) be the largest \(k\) such that there exists some 2-colouring of the edges of \(K_n\) in which any induced subgraph \(H\) on at least \(k\) vertices contains more than…
density Hales-Jewett
Is it true that for every \(\epsilon>0\) and integer \(t\geq 1\), if \(N\) is sufficiently large and \(A\) is a subset of \([t]^N\) of size at least \(\epsilon t^N\) then \(A\) must contain a combinatorial line \(P\) (a set…
Let \(C>0\) be arbitrary. Is it true that, if \(n\) is sufficiently large depending on \(C\), then in any \(2\)-colouring of \(\binom{\{2,\ldots,n\}}{2}\) there exists some \(X\subseteq \{2,\ldots,n\}\) such that \(\binom{X}{2}\) is…
Let \(A=\{a_1,a_2,\ldots\}\subset \mathbb{R}^d\) be an infinite sequence such that \(a_{i+1}-a_i\) is a positive unit vector (i.e. is of the form \((0,0,\ldots,1,0,\ldots,0)\)). For which \(d\) must \(A\) contain a three-term arithmetic…
For any \(g\geq 2\), if \(n\) is sufficiently large and \(\equiv 1,3\pmod{6}\) then there exists a 3-uniform hypergraph on \(n\) vertices such that - every pair of vertices is contained in exactly one edge (i.e. the graph is a Steiner…
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…
How large can a union-free collection \(\mathcal{F}\) of subsets of \([n]\) be? By union-free we mean there are no solutions to \(A\cup B=C\) with distinct \(A,B,C\in \mathcal{F}\). Must \(\lvert \mathcal{F}\rvert =o(2^n)\)? In [Er65b]…
Dedekind's problem
How many antichains in \([n]\) are there? That is, how many families of subsets of \([n]\) are there such that, if \(\mathcal{F}\) is such a family and \(A,B\in \mathcal{F}\), then \(A\not\subseteq B\)? Sperner's theorem states that…
strong Littlewood-Offord problem
Let \(z_1,\ldots,z_n\in\mathbb{C}\) with \(1\leq \lvert z_i\rvert\) for \(1\leq i\leq n\). Let \(D\) be an arbitrary disc of radius \(1\). Is it true that the number of sums of the shape \[\sum_{i=1}^n\epsilon_iz_i \textrm{ for…
Let \(M\) be a real \(n \times n\) doubly stochastic matrix. Does there exist some \(σ \in S_n\) such that \[ \prod_{1 \leq i \leq n} M_{i, σ(i)} \geq n^{-n}? \] This is true, and was proved by Marcus and Minc [MaMi62] [MaMi62] Marcus,…
For every \(x \in \mathbb{R}\) let \(A_x \subset \mathbb{R}\) be a bounded set with outer measure \(< 1\). Must there exist an infinite independent set, that is, some infinite \(X \subseteq \mathbb{R}\) such that \(x \notin A_y\) for all…
Property B
Does every almost-disjoint family of countably infinite sets whose pairwise intersections all have size ≠ 1 have Property B? Formally: let α be any type, let (A_i)_{i ∈ I} be a family of countably infinite subsets of α such that for all i…
Let \((A_i)\) be a family of countably infinite sets such that \(\lvert A_i\cap A_j\rvert \neq 2\) for all \(i\neq j\). Find the smallest cardinal \(C\) such that \(\cup A_i\) can always be coloured with at most \(C\) colours so that no…
Let \(X\) be a finite set of size \(n\) and \(H(n)\) be such that there is a function \(f:\{A : A\subseteq X\}\to X\) so that for every \(Y\subseteq X\) with \(\lvert Y\rvert \geq H(n)\) we have \(\left\{ f(A) : A\subseteq Y\right\}=X\).…
Let \(f(k,r)\) be minimal such that if \(A_1,A_2,\ldots\) is a family of sets, all of size \(k\), such that for every collection of \(r\) of the \(A_is\) there is some pair \(\{x,y\}\) which intersects all of the \(A_j\), then there is…
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…
A pairwise balanced design for \(\{1,\ldots,n\}\) is a collection of sets \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) such that \(2\leq \lvert A_i\rvert <n\) and every pair of distinct elements \(x,y\in \{1,\ldots,n\}\) is contained in…
Let \(\mathcal{F}\) be a family of sets closed under taking subsets (i.e. if \(B\subseteq A\in\mathcal{F}\) then \(B\in \mathcal{F}\)). There exists some element \(x\) such that whenever \(\mathcal{F}'\subseteq \mathcal{F}\) is an…
Let \(r\geq 1\) and define \(T(n,r)\) to be maximal such that there exists a family \(\mathcal{F}\) of subsets of \(\{1,\ldots,n\}\) of size \(T(n,r)\) such that \(\lvert A\cap B\rvert\neq r\) for all \(A,B\in \mathcal{F}\). Estimate…
Let \(k>r\) and \(n\) be sufficiently large in terms of \(k\) and \(r\). Does there always exist a block \(r-(n,k,1)\) design (or Steiner system with parameters \((n,k,r)\)), provided the trivial necessary divisibility conditions…
If there is a finite projective plane of order \(n\) then must \(n\) be a prime power?
Give an asymptotic formula for the number of \(k\times n\) Latin rectangles. The formula \(F(k,n)\) must satisfy \(L(k,n)\sim F(k,n)\) as \(n\to\infty\) for every choice of \(k=k(n)\leq n\), so it also covers Latin squares (\(k=n\)).
Call a sequence \(1< X_1\leq \cdots \leq X_m\leq n\) block-compatible if there is a pairwise balanced block design \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) such that \(\lvert A_i\rvert=X_i\) for \(1\leq i\leq m\). (A pairwise block…
Find, for all large \(n\), a non-trivial pairwise balanced block design \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) such that, for all \(t\), there are \(O(n^{1/2})\) many \(i\) such that \(\lvert A_i\rvert=t\).
How large should \(\ell(n)\) be such that, almost surely, a random \(3\)-uniform hypergraph on \(3n\) vertices with \(\ell(n)\) edges must contain \(n\) vertex-disjoint edges? The precise asymptotic was given by Kahn [Ka23], proving that…
Suppose \(n\geq kr+(t-1)(k-1)\) and the edges of the complete \(r\)-uniform hypergraph on \(n\) vertices are \(t\)-coloured. Prove that some colour class must contain \(k\) pairwise disjoint edges. In other words, this problem asks to…
weak sunflower problem
Estimate m(n,k), or better give an asymptotic formula.
Let \(m(n)\) be minimal such that there is an \(n\)-uniform hypergraph with \(m(n)\) edges which is \(3\)-chromatic. Estimate \(m(n)\).
Let \(n=p^2+p+1\) for some prime power \(p\), and let \(A_1,\ldots,A_t\subseteq \{1,\ldots,n\}\) be a block design (so that every pair \(x,y\in \{1,\ldots,n\}\) is contained in exactly one \(A_i\)). Is it true that if \(t>n\) then…
Is there a constant \(c_t\), where \(c_t\to \infty\) as \(t\to \infty\), such that if \(\mathcal{F}\) is a finite family of finite sets, all of size at least \(t\), and for every set \(X\) there are \(<c_t\lvert X\rvert\) many…
Let \(F(n)\) be the maximal size of a family of subsets of \(\{1,\ldots,n\}\) such that no set in this family is the union of other members of the family. Is it true that there is a constant \(c>0\) such that \[F(n)\sim c…
Let \(f\) be a function from all pairs of elements in \(\{1,\ldots,n\}\) to \(\{1,\ldots,n\}\) such that \(f(x,y)\neq x\) and \(\neq y\) for all \(x,y\). We call \(X\subseteq \{1,\ldots,n\}\) independent if whenever \(x,y\in X\) we have…
Let \(x_1,\ldots,x_n\) be a sequence of distinct real numbers. Determine \[ \max\left(\sum x_{i_r}\right), \] where the maximum is taken over all monotonic subsequences. This is as Erdős posed the problem in [Er71], which is rather…
Let \(c>0\), and let \(n\) be sufficiently large depending on \(c\). Suppose that \(\mathcal{F}\) is a family of at most \(c2^n\) many finite sets of size \(n\). Let \(X=\cup_{A\in \mathcal{F}}A\). Must there exist…
Determine whether there exists a constant \(C>1\) such that the following holds. Let \(P\) be a finite [projective plane](https://en.wikipedia.org/wiki/Projective_plane). Must there exist a set of points \(S\) such that…