Brown-Erdos-Sos Conjecture on Sparse Triple Systems

Brown-Erdos-Sos Conjecture on Sparse Triple Systems

Definitions and mathematical statement

A $3$-uniform hypergraph $H$ has distinct three-element sets as edges. For every fixed $k\ge3$ and ${\varepsilon}>0$, the Brown--Erdős--Sós conjecture seeks $N=N(k,{\varepsilon})$ such that \[ |V(H)|=n\ge N,\quad |E(H)|\ge{\varepsilon} n^2 \quad\Longrightarrow\quad \exists e_1,\ldots,e_k\text{ distinct}:\left|\bigcup_{i=1}^k e_i\right|\le k+3. \] Equivalently, the maximum size of a hypergraph avoiding every such configuration is $o(n^2)$ for fixed $k$. The small union need not induce exactly those $k$ edges; additional edges are allowed. The vertex threshold is $k+3$, not $k+2$, and the assertion covers every fixed $k$, not just a selected family of cases.

Formulation and concept references: [S1].

Short English statement

Must every quadratically dense triple system contain any prescribed fixed number of edges supported on at most three more vertices than edges?

Research attempt

Scope, process, and first gap.

This GPT-6 Astra Ultra attempt, dated 27 September 2026, reduces the problem to linear triple systems with a controlled density loss, recovers the known three-edge case using triangle removal, and tests the proposed induction from three edges to arbitrarily many. No new general Brown--Erdős--Sós bound is claimed.

The quantifiers matter: $k$ is fixed before $n$ tends to infinity, while the threshold may depend on both $k$ and the density. A configuration can have additional edges among its vertices. The first gap will be an extension principle that preserves the excess of vertices over edges. Ordinary density alone does not justify extending a particular small configuration.

Removing repeated pairs at constant cost.

Call a triple system linear if two distinct edges meet in at most one vertex. Suppose $H$ avoids $k$ edges on at most $k+3$ vertices. A pair of vertices can belong to at most $k-1$ edges: otherwise, $k$ triples through that pair use at most $k+2$ vertices, already contradicting avoidance.

Make a graph whose vertices are the triples of $H$, joining two vertices when the corresponding triples share a pair. Each triple has three pairs, and each pair belongs to at most $k-2$ other triples. Consequently this conflict graph has maximum degree at most $3(k-2)$. Greedily choosing a vertex and deleting it and its neighbors produces an independent set of size at least \[ \frac{|E(H)|}{3k-5}. \tag{417.1} \] The chosen triples form a linear subsystem $H'$ on the same vertex set.

Therefore it is enough to prove the conjecture for linear systems. Indeed, if the general instance is not already solved by a pair of large codegree, $417.1$ leaves density at least $\varepsilon/(3k-5)$. A threshold for linear systems at that density becomes a threshold for the original system. The converse implication is immediate because linear systems are special cases. The loss depends only on fixed $k$, not on $n$.

This reduction does not say that every dense system is itself nearly linear in edit distance. It only extracts a constant fraction of its edges, which is sufficient for an $o(n^2)$ assertion.

The known three-edge case, with the counting step exposed.

For $k=3$, the preceding extraction preserves at least one quarter of the edges. Suppose, toward a contradiction, that $H'$ is linear, has at least $\varepsilon n^2/4$ edges, and has no three edges whose union has at most six vertices.

Its shadow graph $G$ has one graph edge for each pair contained in a triple. Each hyperedge gives a triangle in $G$. Linearity means that these triangles are pairwise edge-disjoint.

Consider any triangle $abc$ in $G$. If it is not itself a hyperedge, the three pairs $ab,bc,ca$ must lie in three distinct hyperedges. If two pairs came from one triple, that triple would be $abc$. The three distinct supporting hyperedges have union of size at most six: the three displayed vertices and at most one additional vertex for each pair. This is forbidden. Thus every triangle of $G$ is one of the hyperedges of $H'$, and \[ \#\{\text{triangles of }G\}=|E(H')| \le \frac{\binom n2}{3}<\frac{n^2}{6}. \tag{417.2} \]

Now use the triangle case of the removal lemma, stated as Theorem 3 in [S1]: for each $\eta>0$, a graph containing at least $\eta n^2$ edge-disjoint triangles has at least $\delta(\eta)n^3$ triangles, for some positive $\delta(\eta)$. Taking $\eta=\varepsilon/4$ contradicts $417.2$ once $n>1/(6\delta(\eta))$.

This recovers the established $(6,3)$ theorem through a standard consequence of triangle removal. The deep input is explicitly the removal lemma; the argument above is not an independent elementary proof of that lemma. A density parameter for which the assumed graph cannot exist simply makes the implication vacuous.

Why reducing the vertex threshold by one fails.

There are quadratically dense linear systems, so one cannot expect three edges on at most five vertices. An explicit family uses the affine space $\mathbb F_3^r$. Its vertices are the $n=3^r$ vectors, and its edges are the three-point affine lines.

For any distinct $a,b$, the third point of their unique line is $-a-b$. It is distinct from both: equality with $a$ would give $b=-2a=a$ in characteristic three. Every pair belongs to exactly one triple, and hence the number of edges is \[ |E|=\frac{\binom n2}{3}=\frac{n(n-1)}6. \tag{417.3} \] For any three distinct edges of a linear system, inclusion--exclusion gives \[ |e_1\cup e_2\cup e_3| =9-\sum_{i<j}|e_i\cap e_j|+|e_1\cap e_2\cap e_3| \ge6. \] Thus $417.3$ avoids three edges on five vertices at positive quadratic density. This is a counterexample to the strengthened threshold $k+2$ at $k=3$, and is fully consistent with the stated threshold $k+3$.

The example also explains why merely making the system linear has not made it sparse. Linearity gives an upper bound of order $n^2$, exactly the density scale where the conjecture begins.

The extension step that density does not supply.

Suppose a configuration has $e$ edges and exactly $e+3$ vertices. To adjoin one new edge while retaining at most $(e+1)+3$ vertices, the new edge must add at most one vertex. It must therefore meet the old vertex set in at least two vertices.

A large average vertex degree does not force such an edge through a prescribed constant-size set. For a direct stress test, take an isolated loose triangle \[ \{a,b,x\},\qquad \{b,c,y\},\qquad \{c,a,z\}, \] on six distinct vertices, and put a large affine system from $417.3$ on a disjoint vertex set. The union remains linear and has asymptotic density $1/6$. Nevertheless no further edge meets the displayed six-vertex component at all, so that particular three-edge configuration cannot be extended.

This is not a counterexample to any case of the conjecture: the other component may contain the required configuration. It refutes only the proposed rule that an arbitrary already-found configuration can always be extended using global density. A successful induction must choose its configuration with a stronger abundance or extension property, or find the desired larger object by a different argument.

Taking several disjoint six-vertex configurations also fails to preserve the required excess. The union of $t$ such configurations has $3t$ edges and $6t$ vertices, so its excess is $3t$, not three. Even plentiful small configurations must overlap in a controlled way.

Verification and outcome.

The accompanying finite checks construct the affine systems in dimensions one through three, count their pairs and triples exactly, and check linearity. They enumerate triples of triples on six vertices to verify the small union calculation, and test the conflict-degree extraction on all triple systems with at most five vertices. These tests validate the reductions and countertests; they do not verify the removal lemma or the asymptotic conjecture computationally.

UNRESOLVED. The linear reduction and the known $k=3$ case are justified, and two overstrong shortcuts are ruled out. The remaining gap is to force, for every fixed $k$, an exactly $k$-edge configuration with vertex excess at most three. Neither unrestricted extension of a chosen configuration nor disjoint packing supplies that step.

Sources

• S1 David Conlon, Lior Gishboliner, Yevgeny Levanzov and Asaf Shapira, A New Bound for the Brown-Erdos-Sos Problem, author-hosted manuscript. https://www.math.tau.ac.il/~asafico/bes.pdf. Formulation source.