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.
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…
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…
What is \(\mathrm{ex}_3(n,K_4^3)\)? That is, the largest number of \(3\)-edges which can placed on \(n\) vertices so that there exists no \(K_4^3\), a set of 4 vertices which is covered by all 4 possible \(3\)-edges. See also…
Let \(R_r(n)\) denote the \(r\)-uniform hypergraph Ramsey number: the minimal \(m\) such that if we \(2\)-colour all edges of the complete \(r\)-uniform hypergraph on \(m\) vertices then there must be some monochromatic copy of the…
Let \(F(n,\alpha)\) denote the smallest \(m\) such that there exists a \(2\)-colouring of the edges of \(K_n\) so that every \(X\subseteq [n]\) with \(\lvert X\rvert\geq m\) contains more than \(\alpha \binom{\lvert X\rvert}{2}\) many…
Let \(R_3(n)\) be the minimal \(m\) such that if the edges of the \(3\)-uniform hypergraph on \(m\) vertices are \(2\)-coloured then there is a monochromatic copy of the complete \(3\)-uniform hypergraph on \(n\) vertices. Is there some…
**Erdős Problem 593 (\\(500)**: Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number \)> \aleph_0…
Let \(f(n;t)\) be minimal such that if a \(t\)-uniform hypergraph on \(n\) vertices contains at least \(f(n;t)\) edges then there must be four edges \(A,B,C,D\) such that \[A\cup B= C\cup D\] and \[A\cap B=C\cap D=\emptyset.\] Estimate…
Determine, for any \(k>r>2\), the limiting value as \(n\to\infty\) of \[\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},\] where \(\mathrm{ex}_r(n,K_k^r)\) is the largest number of \(r\)-edges which can placed on \(n\) vertices so that there…
Ruzsa-Szemerédi problem
Let \(\mathcal{F}\) be the family of all \(3\)-uniform hypergraphs with \(6\) vertices and \(3\) \(3\)-edges. Is it true that \[\mathrm{ex}_3(n,\mathcal{F})=o(n^2)?\] The answer is yes, proved by Ruzsa and Szemerédi [RuSz78] (this is known…
Let \(r\geq 2\), and let \(\mathrm{ex}_r(n;K_{r+1}^r)\) be the maximum number of \(r\)-edges that can be placed on \(n\) vertices without forming a \(K_{r+1}^r\) (the \(r\)-uniform complete graph on \(r+1\) vertices). Is every…
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…
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…
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…
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…
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…
Does there exist an absolute constant \(c>0\) such that, for all \(r\geq 2\), in any \(r\)-uniform hypergraph with chromatic number \(3\) there is a vertex contained in at least \((1+c)^r\) many edges? This was solved by Erdős and Lovász…
Does there exist a \(3\)-critical \(3\)-uniform hypergraph in which every vertex has degree \(\geq 7\), where criticality means that the transversal number is \(3\) and deleting any edge reduces it to \(2\)? In the first formulation, the…
Does there exist a \(k>2\) such that the \(k\)-sized subsets of {1,...,2k} can be coloured with \(k+1\) colours such that for every \(A\subset \{1,\ldots,2k\}\) with \(\lvert A\rvert=k+1\) all \(k+1\) colours appear among the \(k\)-sized…
Let \(r\geq 2\) and let \(G\) be an intersecting \(r\)-uniform hypergraph with chromatic number \(3\). Must \(G\) contain \(O(r^2)\) many vertices? Vertices are counted in the union of the edges, so isolated vertices are excluded. Alon has…
Let \(k\geq 2\) and \(A_k\subseteq [0,1]\) be the set of \(\alpha\) such that there exists some \(\beta(\alpha)>\alpha\) with the property that, if \(G_1,G_2,\ldots\) is a sequence of \(k\)-uniform hypergraphs with \[\liminf…
Let \(m(n)\) be minimal such that there is an \(n\)-uniform hypergraph with \(m(n)\) edges which is \(3\)-chromatic. Estimate \(m(n)\).
Erdős matching conjecture
Let \(f(n;r,k)\) be the maximal number of edges in an \(r\)-uniform hypergraph which contains no set of \(k\) many independent edges. For all \(r\geq 3\), \[f(n;r,k)=\max\left(\binom{rk-1}{r}, \binom{n}{r}-\binom{n-k+1}{r}\right).\] Note:…
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 such that every \(3\)-uniform linear hypergraph on \(n\) vertices contains an independent set on \(f(n)\) vertices. Estimate \(f(n)\). Phelps and Rödl [PhRo86] proved \(f(n) \asymp (n\log n)^{1/2}\).
Let \(r\geq 3\). There exists \(c_r>r^{-r}\) such that, for any \(\epsilon>0\), if \(n\) is sufficiently large, the following holds. Any \(r\)-uniform hypergraph on \(n\) vertices with at least \((1+\epsilon)(n/r)^r\) many edges contains a…
**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 \(s,k,r\geq 2\). Let \(\mathcal{F}\) be the family of all \(r\)-uniform hypergraphs with \(k\) vertices and \(s\) edges. Determine \[\mathrm{ex}_r(n,\mathcal{F}).\]
Let \(K_{t}(r)\) be the complete \(t\)-partite \(t\)-uniform hypergraph with \(r\) vertices in each class. Is it true that \[\mathrm{ex}_t(n,K_t(r)) \geq n^{t-r^{1-t}-o(1)}\] for all \(t,r\geq 2\)? The restriction \(r\geq 2\) excludes…
Let \(G\) be a finite \(3\)-uniform hypergraph, and let \(F_G(\kappa)\) denote the collection of \(3\)-uniform hypergraphs with chromatic number \(\kappa\) not containing \(G\). If \(F_G(\aleph_1)\) is not empty then there exists…
For \(r\geq 3\) let \(d_r(e)\) be the minimal \(d\) such that \[\mathrm{ex}_r(n,\mathcal{F})=o(n^2),\] where \(\mathcal{F}\) is the family of \(r\)-uniform hypergraphs on \(d\) vertices with \(e\) edges. Prove that \[d_r(e)=(r-2)e+3\] for…