Gerbner–Palmer's generalized Turán conjecture for trees

Let TT be a tree on kk vertices and let r3r\geq3. Write

n=a(k1)+b,0b<k1.n=a(k-1)+b,\qquad 0\leq b<k-1.

For a graph GG, let N(Kr,G){\mathcal N}(K_r,G) denote the number of copies of KrK_r in GG, and let ex(n,Kr,T){\mathrm{ex}}(n,K_r,T) be the maximum of this number over all nn-vertex TT-free graphs. Gerbner–Palmer's conjecture.

ex(n,Kr,T)=N(Kr,aKk1Kb)=a(k1r)+(br).{\mathrm{ex}}(n,K_r,T)={\mathcal N}\bigl(K_r,aK_{k-1}\cup K_b\bigr)=a\binom{k-1}{r}+\binom{b}{r}.

The conjecture asserts that aKk1KbaK_{k-1}\cup K_b maximizes the number of rr-cliques among all nn-vertex TT-free graphs. The paper verifies it for r=k2r=k-2 and for r=k35r=k-3\geq5, but the general statement remains open in the supplied source.

Sources & referencesView supporting material

Primary source

Junpeng Zhou and Xiying Yuan, “Counting large cliques in graphs with a forbidden tree”, arXiv:2607.23960 (2026).

Additional references

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

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.