Lidický–Murphy conjecture on generalized Turán numbers

Let HH be a graph, let rr be an integer with r>χ(H)r>\chi(H), and let nn be a positive integer. For positive integers n1,n2,,nr1n_1,n_2,\dots,n_{r-1} satisfying

n1+n2++nr1=n,n_1+n_2+\dots+n_{r-1}=n,

Lidický–Murphy conjecture. There exist such integers for which

ex(n,H,Kr)=H(Kn1,n2,,nr1).\operatorname{ex}(n,H,K_r)=H(K_{n_1,n_2,\dots,n_{r-1}}).

This conjectures that the maximum number of copies of HH in an nn-vertex KrK_r-free graph is attained by a complete (r1)(r-1)-partite graph. The paper presents a counterexample to this conjecture, so the conjecture is refuted.

Sources & referencesView supporting material

Primary source

Andrzej Grzesik, Ervin Győri, Nika Salia and Casey Tompkins, “Subgraph densities in K_r-free graphs”, arXiv:2205.13455 (2022).

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.