Erdős–Stone problem

For an integer $r\ge 2$ and a real number $0<\delta<1/r$ , let $b_n(r,\delta)$ be the largest integer $b$ such that every graph $G$ on $n$ vertices satisfying $e(G)\geq (1-1/r+\delta)\binom{n}{2}$ contains a copy of the balanced complete $(r+1)$ -partite graph $K_{r+1}(b)$ , with $b$ vertices in each part. Determine the asymptotic order of $b_n(r,\delta)$ as $n\to\infty$ . The cited preprint claims that, for every fixed $r$ and $\delta$ in this range, $b_n(r,\delta)=\Theta\!\left(\frac{\log n}{(1/r-\delta)r\log(1/\delta)}\right)$ , completing the bound for all edge densities; this claim is presently unverified.

References

Primary source

arXiv

Additional references

A Tight Erdős–Stone Bound for All Graph Densities — arXiv

extremal-graph-theory probabilistic-combinatorics

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A September 2026 preprint claims to complete the tight bound for balanced multipartite patterns in graphs of every density, but the result has not been checked.

The problem concerns the asymptotic number of balanced complete multipartite subgraphs in graphs, seeking the correct bound across all edge densities. The reported development claims to settle the remaining high-density regime and combine it with earlier work.

September 2026 claimed completion

On September 1, 2026, a preprint titled A Tight Erdős–Stone Bound for All Graph Densities claimed the correct asymptotic order in the remaining high-density regime, thereby completing a tight bound for every density. The theorem is presented in an unrefereed preprint and remains unverified.

Current status (as of September 2026): A preprint claims the Erdős–Stone problem is solved for all densities, but the claimed theorem remains unverified.

Sources

No solutions have been posted yet.