MathDB

Bollobás–Erdős–Szemerédi triangle conjecture

For positive integers nn and tt with n≥5tn\ge 5t, every tripartite graph GG whose three parts each have size nn and whose minimum degree satisfies δ(G)≥n+t\delta(G)\ge n+t has at least 4t34t^3 triangles; equivalently, if f(n,t)f(n,t) denotes the minimum number of triangles in such a graph, then f(n,t)≥4t3f(n,t)\ge 4t^3.

References

Primary source

arXiv

Additional references

extremal-combinatoricsgraph-theory
Posted · edited

Progress summary

Refreshed
Claimed solved

A September 2026 paper claims the triangle-count prediction is false and gives a stronger lower bound in the parameter ranges it studies.

Bollobás, Erdős, and Szemerédi proved a t3t^3 lower bound and constructed examples with at most 4t34t^3 triangles, motivating the conjecture that f(n,t)≥4t3f(n,t)\ge 4t^3 when t≤n/5t\le n/5.

Known results

  • Bollobás, Erdős, and Szemerédi: f(n,t)≥t3f(n,t)\ge t^3, with constructions satisfying f(n,t)≤4t3f(n,t)\le 4t^3 for t≤n/5t\le n/5.
  • A 2024 paper proved f(n,t)≥n2(3t−n)2f(n,t)\ge \frac{n^2(3t-n)}{2}, improving the cubic bound in part of the range.

September 17, 2026 disproof claim

Chunqiu Fang and Rongxing Xu report that the proposed 4t34t^3 lower bound is false and improve the previous t3t^3 lower bound to 12t35\frac{12t^3}{5} under stated relations between nn and tt. This is a claimed resolution of the conjectured constant, but the result is not independently verified here.

Current status (as of September 2026): The 4t34t^3 conjecture is claimed false, and a 12t35\frac{12t^3}{5} lower bound is claimed under explicit size conditions; verification and the full parameter range remain open.

Sources

Solutions 0

No solutions have been posted yet.