Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 901

claims/: The 7 claim pages of Problem 901, one per claimant's result; the problem's standing derives from them.

Statement. Let $m(n)$ be minimal such that there is an $n$ -uniform hypergraph with $m(n)$ edges which is $3$ -chromatic. Estimate $m(n)$ .

Status. Open. The site labels the problem OPEN, with its note that no finite computation can settle it (page last edited 28 December 2025).

Source. erdosproblems.com/901, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #901, https://www.erdosproblems.com/901.

References.

[Be77] Beck, J., On a combinatorial problem of P. Erdős and L. Lovász. Discrete Math. (1977), 127-131.
[Be78] Beck, J., On $3$ -chromatic hypergraphs. Discrete Math. (1978), 127-137.
[Er63b] Erdős, P., On a combinatorial problem. Nordisk Mat. Tidskr. (1963), 5-10, 40.
[Er64e] Erdős, P., On a combinatorial problem. II. Acta Math. Acad. Sci. Hungar. (1964), 445-447.
[ErLo75] Erdős, P. and Lovász, L., Problems and results on $3$ -chromatic hypergraphs and some related questions. (1975), 609-627.
[Pl09] Pluhár, András, Greedy colorings of uniform hypergraphs. Random Structures Algorithms (2009), 216-221.
[RaSr00] Radhakrishnan, Jaikumar and Srinivasan, Aravind, Improved bounds and algorithms for hypergraph $2$ -coloring. Random Structures Algorithms (2000), 4-32.

Formalization. Statement in formal-conjectures.

Current assessment

The question (site formulation, page last edited 28 December 2025). The statement above; OPEN, with the site's note that no finite computation can settle it. $m(n)$ is the least number of edges of an $n$ -uniform hypergraph without property B, that is, with no set that meets every edge and contains none; the site's header sources are [ErLo75, p. 610] and Erdős's 1982 survey, and its commentary credits six papers, each recorded on an accepted partial claim page below. The problem asks for an estimate, so no claim page is a full claim and the derived standing is open.

Bounds. The best bounds on record are

0.7\sqrt{\frac n{\ln n}}\,2^n<m(n)\le n^22^{n+1}

for all large $n$ . The lower bound is Radhakrishnan and Srinivasan's theorem of 2000; the upper bound is Erdős's Theorem 1 of 1964, and no upper bound of smaller order than $n^22^n$ is known. Only the constant has improved: the same paper states without proof the refinement $m(n)<(1+\epsilon)e(\log2)\,n^22^{n-2}$ for large $n$ , and Radhakrishnan and Srinivasan cite Alon and Spencer's presentation of Erdős's random construction, with $(e(\ln2)/4+o(1))\,n^22^n$ edges. The lower bound grew in steps: Erdős's [[problems/set_systems/E0901/claims/1963_01_01_erdos| $2^{n-1}$ of 1963]], Beck's [[problems/set_systems/E0901/claims/1977_01_01_beck| $c(\log n)2^n$ of 1977]], which proved the Erdős–Lovász conjecture $m(n)/2^n\to\infty$ , and Beck's [[problems/set_systems/E0901/claims/1978_01_01_beck| $n^{1/3-o(1)}2^n$ of 1978]]; Pluhár's [[problems/set_systems/E0901/claims/2009_02_10_pluhar| $0.5268\,n^{1/4}2^n$ of 2009]] is weaker than the record but has a two-page proof. Erdős and Lovász [ErLo75] suggest that $n2^n$ is the true order of $m(n)$ , and Erdős's 1964 paper guesses the same; this is a conjecture in a colloquium volume, not a result, so it has no claim page.

Small values. $m(2)=3$ (a triangle) and $m(3)=7$ (the Fano plane) are recorded in Erdős's 1963 paper, and $m(4)=23$ is Östergård's computer-assisted determination of 2014, which the site lists without a source. No value with $n\ge5$ is known.

Search scope, 2026-10-06: the site's problem page (OPEN, last edited 28 December 2025, no proof claims) and its one-comment discussion thread (21 December 2025, pointing to [ErLo75]); the community database lists the problem as open and unformalized as of its last update; the formal-conjectures statement file is linked above.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (36)

Erdős's lower bound 2^(n-1) for m(n)Erdős's upper bound n^2 2^(n+1) for m(n)Beck's bound c (log n) 2^n and the Erdős–Lovász conjecture Beck's bound n^(1/3-o(1)) 2^n for m(n)Radhakrishnan and Srinivasan's bound 0.7 sqrt(n / ln n) 2^n Pluhár's short proof of m(n) > 0.5268 n^(1/4) 2^n Östergård's value m(4) = 23 problems/set_systems/E0901/claims Problem 1027 Koishi Chan's proof by adaptive partial coloring Set Systems, Designs and Hypergraphs graph_coloring/erdos_1975_problems_results_3_chromatic_hypergraphs_related graph_coloring/radhakrishnan_2000_improved_bounds_algorithms_hypergraph_coloring Corollary 5.1 (p. 24): m*(n) >= 4^n/n^{1+epsilon} for every fixed epsilon > 0 and all large n Definition 5.1 (p. 15): uniform epsilon-almost-disjoint families of hypergraphs Theorem 2.1 (p. 7): every n-uniform hypergraph with at most (1/10) sqrt(n/ln n) 2^n edges, or 0.7 sqrt(n/ln n) 2^n edges for large n, is 2-colorable Theorem 3.1 (p. 11): for large n a proper 2-coloring of an n-uniform hypergraph with at most 0.7 sqrt(n/ln n) 2^n edges is found in NC^1 Theorem 4.2 (p. 13): for large n an n-uniform hypergraph in which each edge meets at most 0.17 sqrt(n/ln n) 2^n other edges is 2-colorable Theorem 5.1 (p. 15): for each fixed epsilon > 0 some uniform epsilon-almost-disjoint family has at most n^2 2^n edges and is not 2-colorable for large n Theorem 5.2 (p. 15): uniform epsilon-almost-disjoint hypergraphs with at most n^{1-epsilon} 2^n edges are 2-colorable for large n Theorem 5.3 (p. 22): uniform hypergraphs with pairwise intersections at most a and overlap at most n^{1-epsilon} 2^n are 2-colorable for large n Set Systems, Designs and Hypergraphs set_systems/erdos_1963_combinatorial_problem Lemma (p. 7): at least 2^m times the product of (1-2^{-alpha_i}) subsets of T_1 contain no A_i, with equality exactly for disjoint A_i Theorem 1 (p. 6): a family of finite sets with sum of 2^{-alpha_i} at most 1/2, or product of (1-2^{-alpha_i}) at least 1/2, has property B Theorem 2 (p. 9): finite sets with product of (1-2^{-alpha_i}) at least 1/2, together with any infinite sets, have property B set_systems/erdos_1964_combinatorial_problem Theorem 1 (p. 445) and refinement (6): m(n) < n^2 2^(n+1)Theorem 2 (p. 447): random families of k n-sets of an N-set fail property B set_systems/pluhar_2009_greedy_colorings_uniform_hypergraphs Claim 1 (p. 2): the random greedy coloring leaves fewer than 2√π e^{1/(6n)} n^{-1/2} 2^{-2n}|E|(|E|-1) all-red edges in expectation Corollary 1 (p. 3): m(n) > (√2/2) π^{-1/4} e^{-1/(12n)} n^{1/4} 2^n, and m(n) > 0.5268 n^{1/4} 2^n for n ≥ 3 Corollary 3 (p. 4): |E| ≤ (2πe)^{-1/2} s^{(k-1)/(2k)} k^s with s = n-1 gives k-colorability, so m_k(n) > (√(4πe) k)^{-1} n^{1/2-1/(2k)} k^n Corollary 6 (p. 5): every n-uniform, n-regular hypergraph is 2-colorable for n ≥ 8 Lemma 2 (p. 3): a hypergraph is k-colorable if and only if some vertex order contains no ordered k-chain Theorem 4 (p. 4): an n-uniform hypergraph whose edges each meet at most D others is 2-colorable if 2e(2D²-D)((n-1)!)²/(2n-1)! ≤ 1

Graph