Erdős problem #901 — wave 7s

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

Claim labels

• (a) elementary-rigorous: a complete mathematical argument is given here.
• (b) rigorous-modulo-named-theorem: the claim is exactly a theorem in a

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

• (c) plausible/structural-unverified: a structural observation without a

proof; none is used as a conclusion below.

• (d) computational-only: certified by the standalone exhaustive program,

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:

• status: OPEN;
• claimed proofs: 0;
• “Currently working on this problem”: None;
• “Interested in collaborating”: None;
• all other displayed reaction/interest markers: None;
• page last edited: 28 December 2025.

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.

2. \(m(2)=3,\ m(3)=7,\ m(4)=23\).

3. Erdős proved

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

4. 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\).

5. Radhakrishnan–Srinivasan obtained

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

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

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

7. 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.

2. 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)

3. 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)

4. 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\).

5. 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.

6. 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.

7. 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

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

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

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:

• two blocks in the 6-side would meet in at least four points, impossible;
• one block in each side would be a disjoint pair, impossible.

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

edges. Together with the construction,

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:

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

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);

2. 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.

• If some pair is blue-blue, choose a blue point from every pair. If the

number of chosen \(b_i\)'s is odd, toggle the choice in that blue-blue pair.

An all-blue even-parity transversal results.

• If no pair is blue-blue, every pair is split. If the unique all-blue

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

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

• all \(2^{16}=65{,}536\) two-colorings modulo global color exchange were

checked;

• the minimum number of monochromatic edges is one;
• every one of the 51 edges is the unique monochromatic edge of some

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

• 35 edges have 325 such sole-edge witnesses each, and 16 edges have 448;
• every pair of the 17 vertices co-occurs in an edge, so the direct

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

This is (a).

4.2 Balanced-coloring bound

Double-counting balanced partitions and monochromatic edges gives

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 |

|---:|:---|

| 32 | 19–25 |

| 33 | 19–26 |

| 34–35 | 17–26 |

| 36–37 | 17–27 |

| 38 | 17–28 |

| 39–40 | 15–28 |

| 41–43 | 15–29 |

| 44–46 | 15–30 |

| 47 | 15–31 |

| 48–49 | 13–31 |

| 50 | 13–32 |

Consequently:

• to improve the named-theorem lower bound from 32 to 33, it is enough (and

necessary for this direct approach) to rule out 32-edge examples for

\(19\le v\le25\);

• any construction improving 51 to at most 50 has a pair-covered quotient

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

• closing \(m(5)=51\) by finite search requires excluding every relevant

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

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:

• \(v=25\): 53,130 candidate edges, 16,777,216 complement-fixed colorings,

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

• \(v=32\): 201,376 candidate edges, 2,147,483,648 colorings, and 54.056 TB

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;

2. a symmetry-aware exact-cover/SAT certificate for the finite windows;

3. 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:

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.