← All problems

Alon–Shikhelman conjecture

For every integer s≥2s\ge 2 and every graph family H\mathcal{H} such that χ(H)>s\chi(H)>s for every H∈HH\in\mathcal{H}, define ex⁡(G,Ks,H)\operatorname{ex}(G,K_s,\mathcal{H}) to be the maximum number of copies of KsK_s in an H\mathcal{H}-free subgraph of GG. The conjecture asserts that computing ex⁡(G,Ks,H)\operatorname{ex}(G,K_s,\mathcal{H}) is NP-hard. Moreover, for every fixed δ>0\delta>0, it is NP-hard to approximate ex⁡(G,Ks,H)\operatorname{ex}(G,K_s,\mathcal{H}) within additive error ns−δn^{s-\delta} on nn-vertex input graphs.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new preprint reports the conjecture for every finite forbidden family, while the broader case of possibly infinite families remains open.

The Alon–Shikhelman conjecture predicts a computational hardness threshold for generalized Turán problems. The newly reported result extends the conjectured statement beyond the previously established special case.

Known results

  • The earlier work gives additive approximation algorithms and hardness-motivated conjectures for finite forbidden families, but does not prove the full conjecture (Alon, Shikhelman, 2018).

October 2026 finite-family result

On October 22, 2026, a report on the preprint NP-Hardness of Generalized-Turán Graph Modification Problems by Lior Gishboliner, Yevgeny Levanzov, and Asaf Shapira stated that the hardness conjecture is proved for finite graph families, with an elementary recovery of the earlier s=2s=2 case. This is a claimed advance, not independently verified here; arbitrary, possibly infinite forbidden families remain outside the result.

Current status (as of October 2026): The finite-family case is claimed proved but remains unverified; the conjecture for arbitrary, possibly infinite forbidden families remains open.

Sources

Solutions 0

No solutions have been posted yet.