Erdős problem #1178 — wave 8i

Date: 2026-07-28 (UTC)

Claim labels used below:

• (a) elementary-rigorous: proved here from definitions and elementary facts.
• (b) rigorous-modulo-named-theorem: the deduction is rigorous assuming the explicitly named published/preprint theorem.
• (c) plausible/structural-unverified: no claims of this type are used in a conclusion.
• (d) computational-only: certified by the standalone standard-library checker, not promoted to an asymptotic theorem.

0. Mandatory live-page audit

I fetched the live page, its LaTeX-source page, and its discussion thread through the Bright Data browser on 2026-07-28.

Live status: OPEN. The page was last edited 26 January 2026.

Verbatim live statement (from the page's “View the LaTeX source”):

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 all $r,e\geq 3$.

The page lists the following ground truth.

• Brown, Erdős, and Sós [BES73] proved \(d_r(e)\ge (r-2)e+3\).
• Ruzsa and Szemerédi [RuSz78] proved \(d_3(3)=6\).
• Erdős, Frankl, and Rödl [EFR86] proved \(d_r(3)=3(r-2)+3\) for every \(r\ge3\).
• Sárközy and Selkow [SaSe05] proved

\[ d_r(e)\le (r-2)e+2+\lfloor\log_2e\rfloor. \]

• Solymosi and Solymosi [SoSo17] proved \(d_3(10)\le14\).
• Conlon, Gishboliner, Levanzov, and Shapira [CGLS23] proved

\[ d_3(e)\le e+O\!\left(\frac{\log e}{\log\log e}\right). \]

• The page also records Erdős's stronger-order-of-magnitude question involving \(r_{k-3}(n)\), and points to problem #1157 for the general case.

The sole comment says, verbatim, “[SaSe04] is unable to load a reference. (The site has been updated to address this comment.)” It was posted by JakeMallen at 09:53 on 25 January 2026. It is not a proof claim.

The collision checks were all negative:

• claimed proofs: 0;
• “Currently working on this problem”: None;
• “Interested in collaborating”: None;
• “I am working on formalising the results”: None.

Therefore the requested stop condition was not triggered.

1. Notation and the exact core

Write \(f_r(n,v,e)\) for the maximum number of edges in an \(n\)-vertex \(r\)-graph with no \(e\) edges whose union has at most \(v\) vertices. For \(n\ge v\), this is the page's extremal function for the family of all \(r\)-graphs on \(v\) vertices with \(e\) edges: a union of fewer than \(v\) vertices can be padded by isolated vertices.

Proposition 1: the whole conjecture reduces to \(r=3\) (a)

For every \(r,e\ge3\),

This is the \(k=2,d=1\) specialization of Proposition 1.2 in CGLS23, but here is a self-contained proof.

Let \(H\) be an \(r\)-graph with more than the right side of (1) edges. If some triple \(T\) lies in \(e\) edges of \(H\), those edges have union at most

and we are done.

Otherwise each triple lies in at most \(e-1\) edges. Form a conflict graph whose vertices are the edges of \(H\), joining two when their intersection has at least three vertices. For a fixed \(r\)-edge \(Y\), charge every conflict to a triple in \(Y\). Its conflict degree is at most \(\binom r3(e-1)\). Greedy independent-set selection therefore gives a subfamily \(\mathcal E_1\) of more than \(f_3(n,e+3,e)\) \(r\)-edges with pairwise intersections of size at most two.

Choose an arbitrary triple \(T_Y\subset Y\) for every \(Y\in\mathcal E_1\). These triples are distinct, since equality \(T_Y=T_{Y'}\) would give \(|Y\cap Y'|\ge3\). By the definition of \(f_3\), some \(e\) selected triples span at most \(e+3\) vertices. Their corresponding \(r\)-edges add at most \(r-3\) vertices apiece, so they span at most

This proves (1).

Consequently, proving \(f_3(n,e+3,e)=o(n^2)\) for every fixed \(e\) proves the requested upper bound for every \(r\); the live-page lower bound then gives equality. Conversely, \(r=3\) is a special case. Thus the unresolved content of #1178 is exactly the \(3\)-uniform conjecture. Its first unknown value is \(e=4\), the \((7,4)\)-problem.

2. Primary-literature audit through July 2026

All paper identifiers below were opened on their primary arXiv or publisher pages and checked against the claimed theorem/abstract.

• CGLS, arXiv:1912.08834, JCTB 158 (2023) explicitly states that only \(e=3\) is settled, gives the \(e+O(\log e/\log\log e)\) result, and proves the general reduction used above. It also notes that \(f_3(n,7,4)=o(n^2)\) implies Szemerédi's four-term progression theorem. (b)
• Shapira–Tyomkyn, arXiv:2301.07758, Israel J. Math. 267 (2025) reduces an approximate form to a graph conjecture; its abstract promises an absolute additive error, not the exact \(+3\). It does not solve #1178. (b)
• Janzer–Methuku–Milojević–Sudakov, arXiv:2311.12765, Discrete Analysis 2025:5 proves a power saving for \(e+\lfloor\log_2e\rfloor+38\) vertices. This is valuable but does not reach \(e+3\). (b)
• Santos–Tyomkyn, arXiv:2508.09841 proves the conjectured configuration in linear triple systems at normalized density \(>4/5\), not at every fixed positive density. (b)
• Gishboliner–Solymosi, arXiv:2606.25931, submitted 24 June 2026, proves that a linear \(r\)-graph with

\[ |E(H)|\ge \frac{k-2}{r^2((r-2)(k-2)+1)}n^2+\frac nr \]

contains \(k\) edges on at most \((r-2)k+3\) vertices. Its introduction still calls the conjecture widely open and says only \(k=3\) is known. (b)

• Keevash–Long, arXiv:2007.14824 proves a “large uniformity” density theorem where the required \(r\) depends on the positive density. That quantifier does not imply \(o(n^2)\) for any fixed \(r\), because #1178 needs the conclusion for every density \(\delta>0\) with \(r\) fixed. (b)
• The search also found Shangguan, arXiv:2210.11338, whose title says “a solution to the Brown–Erdős–Sós problem for every uniformity.” It concerns existence of the limit for

\[ f_r(n,er-2(e-1),e)=f_r(n,(r-2)e+2,e), \]

one vertex below #1178's target, and is a different BES problem. It does not solve this page. (b)

• Gyárfás–Sárközy, DOI 10.1556/012.2023.01539 gives an equivalent balanced-bipartite edge-coloring form of the \((7,4)\)-conjecture, but no resolution. (b)

Targeted searches for exact values such as \(f_3(10,7,4)\) did not locate a primary-source finite table. That is a search miss, not a novelty claim: the table in Section 4 may well be known or folklore.

3. A finite-density corollary for the first open case

Proposition 2 (b: Gishboliner–Solymosi 2026 + Brooks's theorem)

Every \(n\)-vertex \((7,4)\)-free triple system \(H\) satisfies

This improves the immediate pair-codegree ceiling

\(|E(H)|\le\binom n2=(\tfrac12+o(1))n^2\), but it is still a positive-density bound and therefore does not prove the conjecture.

Proof. Four triples through one fixed pair span only six vertices, so every pair has codegree at most three. Make a conflict graph \(G\) on \(E(H)\), with two triples adjacent when they share a pair. Each triple has three pairs and at most two other triples through each pair, hence \(\Delta(G)\le6\).

Also \(G\) has no \(K_7\); in fact every clique has size at most four. To see this, take two clique members

If every clique member contains \(\{1,2\}\), the pair-codegree bound gives size at most three. Otherwise a clique member missing that pair must be \(\{1,3,4\}\) or \(\{2,3,4\}\), and checking intersection with it restricts the whole clique to the four triples on \(\{1,2,3,4\}\).

By Brooks's theorem, every component of maximum degree six is six-colorable unless it is \(K_7\); lower-degree, complete, and odd-cycle components also need at most six colors here. Thus \(\chi(G)\le6\). The six color classes partition \(H\) into linear triple systems.

The \(r=3,k=4\) case of the Gishboliner–Solymosi theorem says that a linear triple system with at least

edges contains four edges on at most seven vertices. Since every color class is \((7,4)\)-free, each is smaller than this threshold. Summing six classes gives (2). \(\square\)

I do not claim (2) is new in the literature; it is a verified corollary of a June 2026 preprint.

4. Exact finite \((7,4)\)-free table

Set

A triple system is \((7,4)\)-free exactly when every four of its edges have union of size at least eight.

The exact values (d, with elementary upper proofs (a))

The construction checks are finite/computational and reproduced by the standalone script. The upper bounds are elementary.

4.1 Deletion averaging (a)

If \(H\) is an \(n\)-vertex \((7,4)\)-free triple system, every \(H-v\) has at most \(M(n-1)\) edges. Every triple survives exactly \(n-3\) vertex deletions, so

Therefore

Starting with \(M(7)=3\), (4) gives \(M(8)\le4\) and \(M(9)\le6\). Once the special \(M(10)\le7\) lemma below is known, it gives

4.2 The exceptional \(n=10\) upper bound (a)

Assume for contradiction that \(H\) has eight edges on ten vertices. Since \(M(9)=6\),

for every vertex \(v\), so every degree is at least two. The degree sum is \(24\); hence at least six vertices have degree exactly two.

Construct a multigraph \(J\) whose eight vertices are the eight hyperedges of \(H\). Every degree-two vertex \(x\in V(H)\) supplies one edge of \(J\), joining the two hyperedges containing \(x\). Thus \(J\) has at least six edges.

Any three edges of \(J\) must have at least five endpoints. Otherwise, three degree-two vertices \(x,y,z\) have all their incident hyperedges among at most four hyperedges of \(H\). Extend these to four hyperedges if necessary. The complementary four hyperedges avoid \(x,y,z\), so they span at most the other seven vertices—a forbidden \((7,4)\)-configuration.

This condition forces \(J\) to be simple: two parallel edges together with any third edge have at most four endpoints. It also forces maximum degree at most two, forbids triangles, forbids every cycle, and forbids a three-edge path. Consequently every nontrivial component is \(K_2\) or \(P_3\). On eight vertices such components contain at most

edges, contradicting the at least six edges already obtained. Hence \(M(10)\le7\).

The checker independently exhausts all

simple six-edge graphs on eight vertices and confirms that every one has three edges on at most four endpoints. This is an audit of the structural lemma, not a substitute for the preceding proof.

4.3 Explicit lower certificates (d)

For \(n=7\), use

For \(n=8\), add \(137\). The union of all four triples is all eight vertices.

For \(n=9\), use the three rows and three columns of a \(3\times3\) grid:

For \(n=10,11,12\), start with the following 12-edge triple system \(Q\) on \(\{0,\ldots,11\}\):

Here, for example, \(08\,11\) means \(\{0,8,11\}\). The \(n=11\) certificate is \(Q-\{0\}\), and the \(n=10\) certificate is \(Q-\{0,4\}\). They have 9 and 7 edges respectively. The system \(Q\) is linear and 3-regular.

The complete edge-quadruple union histograms are:

No histogram contains a union size below eight, proving that all six displayed systems are \((7,4)\)-free. Their edge counts meet the upper bounds, establishing (3).

The immediate next finite frontier is only

The lower bound adds an isolated vertex to \(Q\). A completely naive target-15 search would inspect

labeled candidates, about \(1.17\times10^9\) core-years even at an unrealistic \(10^8\) candidates per second. Any useful \(n=13\) computation therefore needs isomorph-free generation or a symmetry-aware SAT/ILP proof; I did not run a heavy search and make no claim for \(M(13)\).

5. Exact wall

The reduction (1) shows that no separate higher-uniformity lemma is missing. The first unresolved statement is already

After constant-factor linearization, the missing lemma can be stated exactly:

> For every \(\varepsilon>0\), every sufficiently large linear triple system with at least \(\varepsilon n^2\) edges contains four edges spanning at most seven vertices.

The June 2026 theorem supplies this only above the fixed threshold

Proposition 2 transfers it to the general bound \((4/9)n^2+O(n)\), but its leading coefficient does not tend to zero. Neither the finite table nor any fixed-\(n\) computation supplies the uniform-in-\(\varepsilon\) step. This is the precise obstruction; resolving it is the famous \((7,4)\)-conjecture itself, strong enough to imply the four-term Szemerédi theorem.

6. Reproduction

Standalone checker:

python runs/erdos1178_wave8i_reverify.py

Observed output:

construction sizes: [3, 4, 6, 7, 9, 12]
quadruple-union histograms:
  n=7: {}
  n=8: {8: 1}
  n=9: {8: 9, 9: 6}
  n=10: {8: 19, 9: 14, 10: 2}
  n=11: {8: 54, 9: 51, 10: 21}
  n=12: {8: 162, 9: 204, 10: 126, 12: 3}
graph-lemma six-edge candidates rejected: 376740
density arithmetic: 6*(2/27, 1/3) = (4/9, 2)
naive n=13, m=15 candidates: 3687925805170703984190160
ALL CHECKS PASSED

Full checker source:

#!/usr/bin/env python3
"""Independent exact checks for runs/erdos1178_wave8i.md.

Only the Python standard library is used.  The script verifies:

* explicit (7,4)-free triple systems attaining the reported values for
  7 <= n <= 12;
* every union-size histogram quoted in the report;
* the deletion-averaging upper-bound arithmetic;
* by exhaustive enumeration, the eight-vertex graph lemma used to rule out
  eight triples on ten vertices; and
* the arithmetic in the 2026 finite-density corollary.
"""

from collections import Counter
from fractions import Fraction
from itertools import combinations
from math import comb


def edge(*vertices: int) -> frozenset[int]:
    result = frozenset(vertices)
    assert len(result) == 3
    return result


def union_histogram(edges: tuple[frozenset[int], ...]) -> Counter[int]:
    return Counter(len(frozenset().union(*four)) for four in combinations(edges, 4))


def check_construction(
    n: int,
    edges: tuple[frozenset[int], ...],
    expected_size: int,
    expected_histogram: dict[int, int],
) -> None:
    assert len(edges) == len(set(edges)) == expected_size
    assert len(frozenset().union(*edges)) == n
    histogram = union_histogram(edges)
    assert histogram == Counter(expected_histogram), (n, histogram)
    assert all(union_size >= 8 for union_size in histogram)


Q12 = (
    edge(0, 4, 9),
    edge(0, 5, 7),
    edge(0, 8, 11),
    edge(1, 5, 6),
    edge(1, 7, 10),
    edge(1, 9, 11),
    edge(2, 4, 5),
    edge(2, 6, 8),
    edge(2, 10, 11),
    edge(3, 4, 10),
    edge(3, 6, 9),
    edge(3, 7, 8),
)

CONSTRUCTIONS = {
    7: (edge(0, 1, 2), edge(0, 3, 4), edge(0, 5, 6)),
    8: (edge(0, 1, 2), edge(0, 3, 4), edge(0, 5, 6), edge(1, 3, 7)),
    9: (
        edge(0, 1, 2),
        edge(3, 4, 5),
        edge(6, 7, 8),
        edge(0, 3, 6),
        edge(1, 4, 7),
        edge(2, 5, 8),
    ),
    10: tuple(e for e in Q12 if e.isdisjoint({0, 4})),
    11: tuple(e for e in Q12 if e.isdisjoint({0})),
    12: Q12,
}

EXACT_VALUES = {7: 3, 8: 4, 9: 6, 10: 7, 11: 9, 12: 12}
EXPECTED_HISTOGRAMS = {
    7: {},
    8: {8: 1},
    9: {8: 9, 9: 6},
    10: {8: 19, 9: 14, 10: 2},
    11: {8: 54, 9: 51, 10: 21},
    12: {8: 162, 9: 204, 10: 126, 12: 3},
}


def verify_constructions_and_averaging() -> None:
    for n in range(7, 13):
        check_construction(
            n, CONSTRUCTIONS[n], EXACT_VALUES[n], EXPECTED_HISTOGRAMS[n]
        )

    degrees = Counter(v for e in Q12 for v in e)
    assert degrees == Counter({v: 3 for v in range(12)})
    assert all(len(a & b) <= 1 for a, b in combinations(Q12, 2))

    assert (8 * EXACT_VALUES[7]) // (8 - 3) == EXACT_VALUES[8]
    assert (9 * EXACT_VALUES[8]) // (9 - 3) == EXACT_VALUES[9]
    assert (10 * EXACT_VALUES[9]) // (10 - 3) == 8
    assert (11 * EXACT_VALUES[10]) // (11 - 3) == EXACT_VALUES[11]
    assert (12 * EXACT_VALUES[11]) // (12 - 3) == EXACT_VALUES[12]


def verify_eight_vertex_graph_lemma() -> int:
    pairs = tuple((1 << u) | (1 << v) for u, v in combinations(range(8), 2))
    rejected = 0
    for candidate in combinations(pairs, 6):
        has_small_three_edge_union = any(
            (a | b | c).bit_count() <= 4
            for a, b, c in combinations(candidate, 3)
        )
        assert has_small_three_edge_union
        rejected += 1

    assert rejected == comb(comb(8, 2), 6) == 376_740

    five_edge_example = (
        (1 << 0) | (1 << 1),
        (1 << 1) | (1 << 2),
        (1 << 3) | (1 << 4),
        (1 << 4) | (1 << 5),
        (1 << 6) | (1 << 7),
    )
    assert all(
        (a | b | c).bit_count() >= 5
        for a, b, c in combinations(five_edge_example, 3)
    )
    return rejected


def verify_reduction_and_density_arithmetic() -> None:
    for r in range(3, 20):
        for e_count in range(3, 20):
            assert e_count + 3 + (r - 3) * e_count == (r - 2) * e_count + 3
            conflict_bound = comb(r, 3) * (e_count - 1) + 1
            assert conflict_bound >= 1

    quadratic = Fraction(4 - 2, 3**2 * ((3 - 2) * (4 - 2) + 1))
    linear = Fraction(1, 3)
    assert quadratic == Fraction(2, 27)
    assert 6 * quadratic == Fraction(4, 9)
    assert 6 * linear == 2
    assert comb(comb(13, 3), 15) == 3_687_925_805_170_703_984_190_160


def main() -> None:
    verify_constructions_and_averaging()
    rejected = verify_eight_vertex_graph_lemma()
    verify_reduction_and_density_arithmetic()
    print("construction sizes:", [EXACT_VALUES[n] for n in range(7, 13)])
    print("quadruple-union histograms:")
    for n in range(7, 13):
        print(f"  n={n}: {dict(sorted(union_histogram(CONSTRUCTIONS[n]).items()))}")
    print(f"graph-lemma six-edge candidates rejected: {rejected}")
    print("density arithmetic: 6*(2/27, 1/3) = (4/9, 2)")
    print("naive n=13, m=15 candidates: 3687925805170703984190160")
    print("ALL CHECKS PASSED")


if __name__ == "__main__":
    main()

PARTIAL: reduced all uniformities to the exact \(r=3\) core, proved \(f_3(n,7,4)=3,4,6,7,9,12\) for \(7\le n\le12\) with a standalone exhaustive checker, and derived \(f_3(n,7,4)<\frac49n^2+2n\) modulo Gishboliner–Solymosi (2026); the required \(o(n^2)\) density-decay lemma remains open.