← All problems

Alon–Shikhelman generalized Turán approximation conjecture

Let TT be a fixed graph with e(T)>0e(T)>0, and let F\mathcal{F} be a fixed nonempty family of graphs. If no graph F∈FF\in\mathcal{F} is a subgraph of any blow-up of TT, then for every ε>0\varepsilon>0, it is NP-hard to approximate ex⁡(G,T,F)\operatorname{ex}(G,T,\mathcal{F}) within additive error nv(T)−εn^{v(T)-\varepsilon}, where GG is an input graph on nn vertices and ex⁡(G,T,F)\operatorname{ex}(G,T,\mathcal{F}) is the maximum number of copies of TT in an F\mathcal{F}-free subgraph of GG.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new preprint proves the conjectured hardness for all bipartite patterns and cliques, but arbitrary patterns remain unresolved.

Alon and Shikhelman’s conjecture, published on March 25, 2022, predicts that approximating ex⁡(G,T,F)\operatorname{ex}(G,T,\mathcal{F}) within additive error nv(T)−εn^{v(T)-\varepsilon} is NP-hard whenever no forbidden graph in F\mathcal{F} is contained in a blow-up of TT.

Known results

  • For every 33-connected pattern TT on tt vertices, hardness was known within error nt−2−εn^{t-2-\varepsilon} under the blow-up condition.
  • For cliques, hardness was known for ex⁡(G,Km,Kk)\operatorname{ex}(G,K_m,K_k) when k≥m+2k\ge m+2; the case k=m+1k=m+1 was open.
  • If a forbidden graph is contained in a blow-up of TT, a polynomial-time additive approximation is known.

October 12, 2026 preprint

Chen, He, Li, Ma, and Xie claim the full conjectured error bound for every bipartite pattern TT and every clique TT, using reductions based on leaf additions, rooted extensions, and random transversals. This is substantive claimed progress, but the general-pattern case remains open and the preprint has not been independently verified.

Current status (as of October 2026): the conjectured hardness is claimed for all bipartite patterns and cliques, while the assertion for arbitrary patterns remains open.

Sources

Solutions 0

No solutions have been posted yet.