ERDŐS/DAILY ▸

← back to the ledger

ERDőS #901 · PARTIAL

Erdős problem #901 — wave 7s

Date of live check and computation: 2026-07-28 UTC

Claim labels

verified primary source, but I did not re-prove the whole theorem.

proof; none is used as a conclusion below.

but not promoted to a uniform theorem.

0. Mandatory live-page check

I fetched both the problem page and its discussion thread through the Bright Data browser path, not datacenter curl.

Authoritative page: <https://www.erdosproblems.com/901>

Discussion: <https://www.erdosproblems.com/forum/discuss/901>

The exact displayed statement is:

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

Live status and collision markers:

Thus neither mandatory stop condition applies.

The sole comment, by Alfaiz at 11:35 on 21 December 2025, says:

This problem is also reported to be in [ErLo75].

It then gives the full Erdős–Lovász bibliographic entry and says that the site was updated to address the comment. It is not a proof claim.

The page's listed ground-truth context is:

  1. Not having Property B is the equivalent formulation used by the page. Property

B means that some set \(S\) intersects every edge and contains no edge.

  1. \(m(2)=3,\ m(3)=7,\ m(4)=23\).
  2. Erdős proved

\[ 2^n\ll m(n)\ll n^2 2^n. \]

  1. Beck first proved \(m(n)/2^n\to\infty\), quantitatively

\(m(n)\gg(\log n)2^n\), and later obtained \(m(n)\gg n^{1/3-o(1)}2^n\).

  1. Radhakrishnan–Srinivasan obtained

\[ m(n)\gg 2^n\sqrt{\frac n{\log n}}. \]

  1. Pluhár gave a short proof of the weaker

\(m(n)\gg n^{1/4}2^n\).

  1. Erdős–Lovász speculated that \(n2^n\) is the correct order.

1. Primary-source literature audit

I verified the following sources rather than relying on search-result summaries.

  1. Erdős–Lovász (1975). The scan

Problems and results on 3-chromatic hypergraphs and some related questions exists and pp. 609–610 define the chromatic-number convention, define the minimum-edge parameter, record the then-known bounds, and say that \(r2^r\) may be the correct order. This confirms the page's attribution.

  1. Radhakrishnan–Srinivasan (2000).

Improved bounds and algorithms for hypergraph 2-coloring1098-2418(200001)16:1%3C4::AID-RSA2%3E3.0.CO;2-2) is Random Structures & Algorithms 16(1), 4–32. Its abstract explicitly says it improves Beck's \(n^{1/3-o(1)}2^n\) bound; the 2024 source below states its lower bound as \(\Omega(2^n\sqrt{n/\log n})\). (b)

  1. Pluhár (2009). The author's

paper PDF explicitly states the \(cn^{1/4}2^n\) lower bound and identifies it as weaker than Beck's later result. (b)

  1. Aglave–Amarnath–Shannigrahi–Singh (2020).

Improved bounds for uniform hypergraphs without property B is the primary journal PDF. Section 1.1 gives the Abbott–Hanson–Toft construction, and its table records \(m(5)\leq 51\); its Theorem 1.3 was the then-improved \(m(5)\geq29\).

  1. Grill–Linzmayer (2024).

Improved Lower Bounds for Property B, arXiv:2403.05674v3 exists. Theorem 1 states \[ m(5)\ge32,\quad m(6)\ge64,\quad m(7)\ge128,\quad m(8)\ge263,\quad m(9)\ge538. \] The paper still calls \(\Omega(2^n\sqrt{n/\log n})\) and \(O(n^2 2^n)\) the best asymptotic bounds. I therefore use \[ \boxed{32\le m(5)\le51} \] as the current finite bracket, with the lower bound explicitly classified (b) because the long fixed-vertex probability calculation was not independently reconstructed here. The upper bound is re-proved and checked below.

  1. A 2026 subscription chapter,

An Overview of Property B, exists and cites an item called Some upper bounds for property B for small values of \(n\) by heuristic search (2024). The accessible first-page preview and conference abstract contain no numerical result, and I found no independently accessible paper or construction file. I therefore make no mathematical claim from that citation. This is a literature miss, not evidence that no such result exists.

  1. Linzmayer (2018). The TU Wien repository copy of the diploma thesis

Die probabilistische Methode in der Kombinatorik exists. Section 10.2.1 and Appendices A.1–A.2 report \(m_{11}(5)=m_{12}(5)=66\) and give 66-block examples. I independently reconstruct and verify a compact cyclic example below.

No primary source found in this search claimed to close the asymptotic gap.

2. Exact constrained cases: \(m_{11}(5)=m_{12}(5)=66\)

Write \(m_v(5)\) for the minimum number of edges in a non-2-colorable 5-uniform hypergraph on exactly \(v\) vertices (isolated vertices are allowed).

2.1 Compact explicit construction

On \(\mathbb Z/11\mathbb Z\), take all 11 cyclic translates of each of

\[ \begin{split} &\{0,1,2,3,5\},\quad \{0,1,2,6,9\},\quad \{0,1,2,7,8\},\\ &\{0,1,3,4,7\},\quad \{0,1,3,6,8\},\quad \{0,1,5,7,9\}. \end{split} \]

This gives 66 distinct 5-sets. The from-scratch checker verifies all 330 4-subsets and finds that each lies in exactly one block, so this is an \(S(4,5,11)\) Witt design. (d), exact finite certificate

For completeness, its standard intersection arithmetic is elementary. The design parameters through level three are

\[ \lambda_1=30,\qquad \lambda_2=12,\qquad \lambda_3=4,\qquad\lambda_4=1. \]

Fix a block and let \(n_i\) count other blocks meeting it in \(i\) points. Distinct blocks cannot meet in four points. Counting contained triples, pairs, and points gives

\[ n_3=10(4-1)=30, \]
\[ n_2+3n_3=10(12-1)=110, \]
\[ n_1+2n_2+3n_3=5(30-1)=145. \]

Hence \((n_1,n_2,n_3)=(15,20,30)\), whose sum is 65, so \(n_0=0\): no two blocks are disjoint. (a)

Consider an unordered \(5|6\) partition. It has at most one monochromatic block:

There are \(\binom{11}{5}=462\) such partitions. Each block is monochromatic in exactly seven of them: once as the 5-side and six times as a subset of the 6-side. Thus the 66 blocks give \(66\cdot7=462\) incidences. Every \(5|6\) partition consequently has exactly one monochromatic block.

This also covers unbalanced colorings. If the smaller color class has at most four points, extend it to a non-block 5-set (a fixed 4-set has seven 5-set extensions but lies in only one block). The complementary 6-set lies inside the original larger class and, by the preceding paragraph, contains a block. Thus the construction has no Property B. (a), modulo the explicitly checked design incidence

2.2 Matching lower bounds

Any single 5-edge is monochromatic in only seven of the 462 unordered \(5|6\) partitions. Covering them all therefore needs at least

\[ \left\lceil\frac{462}{7}\right\rceil=66 \]

edges. Together with the construction,

\[ \boxed{m_{11}(5)=66}. \]

For 12 vertices, restrict to balanced \(6|6\) partitions. There are \(\binom{12}{6}/2=462\), and a fixed 5-edge is monochromatic in exactly seven, so again at least 66 edges are necessary. Add one isolated vertex to the 11-vertex construction for the matching upper bound:

\[ \boxed{m_{12}(5)=66}. \]

The counting lower bounds are (a); the explicit construction is independently exhausted by the checker (d). These exact values were already reported in Daniel Linzmayer's 2018 diploma thesis, so I do not claim novelty. The compact cyclic block certificate and independent checker are the useful output here.

3. Explicit 51-edge construction proving \(m(5)\le51\)

Let \(\mathcal F\) be the cyclic Fano plane on \(\mathbb Z/7\mathbb Z\), with lines the seven translates of \(\{0,1,3\}\). Let

\[ A=\{a_0,\ldots,a_4\},\qquad B=\{b_0,\ldots,b_4\} \]

be disjoint from the seven Fano vertices. Take:

  1. \(F\cup\{a_i,b_i\}\) for every \(F\in\mathcal F\) and \(0\le i<5\)

(35 edges);

  1. every transversal \(\{x_0,\ldots,x_4\}\), where

\(x_i\in\{a_i,b_i\}\), having an even number of \(b_i\)'s (16 edges).

There are 51 distinct 5-edges on 17 vertices.

Elementary proof of non-2-colorability

In any two-coloring, the Fano core has a monochromatic line; call its color red. To prevent each of the five edges \(F\cup\{a_i,b_i\}\) from being red, every pair \(\{a_i,b_i\}\) must contain a blue point.

number of chosen \(b_i\)'s is odd, toggle the choice in that blue-blue pair. An all-blue even-parity transversal results.

transversal has even parity it is an edge. If it has odd parity, its complementary all-red transversal has \(5-\text{odd}\), hence an even number of \(b_i\)'s, and is an edge.

Either way a gadget edge is monochromatic, a contradiction. Thus the hypergraph is not 2-colorable. (a)

The explicit coloring \(c(v)=v\bmod3\), under the numeric labeling used by the checker, is proper on all 51 edges. Hence the chromatic number is exactly three, not merely at least three. (a), finite direct check

Therefore

\[ \boxed{m(5)\le51}. \]

The exhaustive computation adds the following structural certificate (d):

checked;

coloring, so deleting any edge makes this hypergraph 2-colorable;

vertex-identification reduction cannot shrink this example.

The edge-list SHA-256 is

949270f00e86645dcc08ffe366711542b1bde743968433e73e2cf4c81285e4f4.

4. Exact finite reduction for the unresolved \(m(5)\) range

4.1 Pair-identification lemma

Suppose vertices \(x,y\) occur together in no edge. Identify them. No 5-edge loses a vertex, and any proper coloring of the quotient lifts to a proper coloring of the original by giving \(x,y\) the quotient color. Therefore non-2-colorability is preserved, while duplicate edges can only reduce the edge count.

Repeated identification shows that any example with \(M\) edges has a minimum-vertex quotient in which every vertex pair occurs in an edge. Hence

\[ \binom v2\le M\binom52=10M. \tag{1} \]

This is (a).

4.2 Balanced-coloring bound

Double-counting balanced partitions and monochromatic edges gives

\[ M\ge \left\lceil \frac{\binom v5} {\binom{\lfloor v/2\rfloor}{5}+ \binom{\lceil v/2\rceil}{5}} \right\rceil. \tag{2} \]

This is (a). It is the elementary fixed-\(v\) coloring bound also used in the modern literature.

Combining (1) and (2) gives these exact surviving vertex windows:

edge count \(M\)possible \(v\) after the two tests
3219–25
3319–26
34–3517–26
36–3717–27
3817–28
39–4015–28
41–4315–29
44–4615–30
4715–31
48–4913–31
5013–32

Consequently:

necessary for this direct approach) to rule out 32-edge examples for \(19\le v\le25\);

with \(13\le v\le32\);

edge count 32 through 50 in the displayed windows.

No unproved finiteness assumption is hidden here.

4.3 Exact set-cover formulation

For fixed \(v\), introduce a binary variable \(x_E\) for every \(E\in\binom{[v]}5\). Represent colorings up to complement by the \(2^{v-1}\) subsets \(S\) with \(0\notin S\). The exact constraints are

\[ \sum_{\substack{E\subseteq S\\\text{or }E\subseteq [v]\setminus S}}x_E\ge1 \qquad\text{for every such }S, \]

and the objective is \(\min\sum_E x_E\).

Thus there is no modeling gap: a feasible integer solution is exactly a non-2-colorable 5-uniform hypergraph. (a)

The direct instances rapidly exceed this VM's intended few-minute budget:

and 111.422 decimal GB even as a dense bit incidence matrix;

as a dense bit matrix.

Naively enumerating 32-edge subsets at \(v=25\) means \(\binom{53130}{32}\approx10^{115.787}\) candidates. Even at an unrealistically optimistic \(10^8\) candidates per core-second this is about \(10^{104.230}\) core-hours. For \(v=32,M=50\), the analogous figure is \(10^{189.158}\) core-hours. These are not estimates for a sophisticated symmetry-aware SAT solver; they precisely show why naive enumeration is not the missing computation.

The exact missing ingredient is therefore one of:

  1. a structural lemma much stronger than pair covering that sharply restricts

degree/codegree patterns or the vertex count;

  1. a symmetry-aware exact-cover/SAT certificate for the finite windows;
  2. a new probabilistic-coloring inequality strong enough to push the lower

bound past 32 (and ultimately toward \(n2^n\)).

For the asymptotic Erdős–Lovász conjecture, finite \(n=5\) computation alone cannot supply the required uniform-in-\(n\) step.

5. Standalone verifier

Complete source: runs/erdos901_wave7s_verify.py

Script SHA-256:

f072cb33fbed7c34dbbe177be5c92c20045ef543693ed3132d52be7f1dcd4f9e

It uses only the Python standard library. Run:

python runs/erdos901_wave7s_verify.py

The core independent checks are implemented directly as follows (the standalone file contains the full source and all assertions):

BASES = (
    (0, 1, 2, 3, 5), (0, 1, 2, 6, 9), (0, 1, 2, 7, 8),
    (0, 1, 3, 4, 7), (0, 1, 3, 6, 8), (0, 1, 5, 7, 9),
)
blocks = {
    frozenset((x + shift) % 11 for x in base)
    for base in BASES for shift in range(11)
}
assert len(blocks) == 66
four_counts = Counter(
    q for block in blocks for q in combinations(sorted(block), 4)
)
assert len(four_counts) == comb(11, 4)
assert set(four_counts.values()) == {1}

for coloring in range(0, 1 << vertex_count, 2):  # fix vertex 0's color
    mono = [
        edge for edge, mask in edge_masks.items()
        if coloring & mask in (0, mask)
    ]
    histogram[len(mono)] += 1

Observed deterministic output:

=== Erdős #901 independent verifier ===
Witt S(4,5,11): 66 distinct blocks; every 4-set occurs once
Witt edge-list SHA-256: 822f0ea2401737466ecb9e5508d38595c3c98bb243b8de1bc318c0328a8d5341
11-vertex two-coloring histogram: [(1, 462), (3, 330), (8, 165), (18, 55), (36, 11), (66, 1)]
12-vertex minimum monochromatic-edge count: 1
EXACT: m_11(5) = m_12(5) = 66

Abbott-Hanson n=5 construction: 17 vertices, 51 distinct 5-edges
51-edge construction SHA-256: 949270f00e86645dcc08ffe366711542b1bde743968433e73e2cf4c81285e4f4
Two-coloring histogram: [(1, 18543), (2, 21395), (3, 3430), (4, 11800), (5, 560), (6, 2730), (7, 1725), (8, 2155), (10, 1400), (12, 700), (14, 190), (16, 669), (21, 85), (24, 70), (25, 40), (26, 21), (28, 5), (36, 17), (51, 1)]
All 51 edges have sole-monochromatic-edge witnesses (edge-critical)
Sole-witness counts per edge: 35 edges x 325, 16 edges x 448
The explicit coloring c(v)=v mod 3 is proper
CERTIFIED: chromatic number is exactly 3, hence m(5) <= 51

Finite search windows after pair-cover + balanced-coloring bounds:
  32 edges: v=19..25 (7 integer values)
  33 edges: v=19..26 (8 integer values)
  34 edges: v=17..26 (10 integer values)
  35 edges: v=17..26 (10 integer values)
  36 edges: v=17..27 (11 integer values)
  37 edges: v=17..27 (11 integer values)
  38 edges: v=17..28 (12 integer values)
  39 edges: v=15..28 (14 integer values)
  40 edges: v=15..28 (14 integer values)
  41 edges: v=15..29 (15 integer values)
  42 edges: v=15..29 (15 integer values)
  43 edges: v=15..29 (15 integer values)
  44 edges: v=15..30 (16 integer values)
  45 edges: v=15..30 (16 integer values)
  46 edges: v=15..30 (16 integer values)
  47 edges: v=15..31 (17 integer values)
  48 edges: v=13..31 (19 integer values)
  49 edges: v=13..31 (19 integer values)
  50 edges: v=13..32 (20 integer values)
  v=25: 53130 candidate edges, 16777216 complement-fixed colorings, 111.422 decimal GB as a dense bit matrix
    naive C(53130,32) search has 10^115.787 candidates
  v=32: 201376 candidate edges, 2147483648 complement-fixed colorings, 54056.458 decimal GB as a dense bit matrix
    naive C(201376,50) search has 10^200.715 candidates

ALL ASSERTIONS PASSED

6. Verified state

This does not solve the requested asymptotic estimate. It does give two exact vertex-restricted values with a compact construction and checker, an independently proved and exhaustively certified 51-edge upper construction, the externally verified post-page lower bound \(m(5)\ge32\), and a finite no-hidden-uniformity reduction specifying exactly what a small-\(n\) exact attack must decide.

PARTIAL: Verified \(m_{11}(5)=m_{12}(5)=66\), certified an edge-critical 51-edge 3-chromatic construction, and reduced the current \(32\le m(5)\le51\) gap to explicit finite set-cover windows; the asymptotic problem remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger