Alon–Shikhelman generalized Turán approximation conjecture
Let be a fixed graph with , and let be a fixed nonempty family of graphs. If no graph is a subgraph of any blow-up of , then for every , it is NP-hard to approximate within additive error , where is an input graph on vertices and is the maximum number of copies of in an -free subgraph of .
References
- NP-hardness of additive approximation for generalized Turán problems — arXiv — Yihan Chen, Jialin He, Xihe Li, Jie Ma, Tianying Xie
Source: arXiv
Progress summary
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 within additive error is NP-hard whenever no forbidden graph in is contained in a blow-up of .
Known results
- For every -connected pattern on vertices, hardness was known within error under the blow-up condition.
- For cliques, hardness was known for when ; the case was open.
- If a forbidden graph is contained in a blow-up of , 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 and every clique , 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.
Solutions 0
No solutions have been posted yet.