Alon's star-forest extremal-graph conjecture

About 10 years old · traced to

Let HH be a star forest, meaning a vertex-disjoint union of stars. For a graph GG, let N(G,H)N(G,H) be the number of subgraphs of GG isomorphic to HH, and let

N(m,H)=max⁡{N(G,H):e(G)=m}.N(m,H)=\max\{N(G,H):e(G)=m\}.

Alon's star-forest extremal-graph conjecture. For every integer m>0m>0, or at least for all sufficiently large mm, there exists a star forest GmG_m with e(Gm)=me(G_m)=m such that

N(m,H)=N(Gm,H).N(m,H)=N(G_m,H).

The conjecture describes the form of an extremal graph for counting a fixed star forest with a prescribed number of edges. The supplied text gives no resolution evidence, so whether the assertion holds for every mm or only eventually remains open.

References

Primary source

Peiru Kuang, Shuang Sun, Yan Wang and Jiasheng Zeng, “Proofs of Two Conjectures of Alon on Subgraph Counts”, arXiv:2606.18321 (2026).

Additional references

2 papers in this index state this conjecture (2016–2026). The statement above is taken from the most recent of them; the others are arXiv:1601.01211.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.