Generalized Turán extremal graph conjecture for edge blow-ups of cycles and paths

Let Ck3C_k^3 and Pk3P_k^3 denote the edge blow-ups of the cycle CkC_k and path PkP_k, respectively. For integers p,tp,t, let Tp(nt+1)T_p(n-t+1) be the balanced pp-partite complete graph on nt+1n-t+1 vertices, let

H(n,p,t)=Kt1+Tp(nt+1),H(n,p,t)=K_{t-1}+T_p(n-t+1),

and let H+(n,p,t)H^+(n,p,t) be obtained from H(n,p,t)H(n,p,t) by adding an extra edge within one class of Tp(nt+1)T_p(n-t+1). Write ex(n,K3,F)\operatorname{ex}(n,K_3,F) for the maximum number of copies of K3K_3 in an FF-free graph on nn vertices. Generalized Turán extremal graph conjecture. When k4k\geq 4 and nn is sufficiently large, H(n,2,k12+1)H(n,2,\lfloor\frac{k-1}{2}\rfloor+1) is the unique extremal graph for both ex(n,K3,Ck3)\operatorname{ex}(n,K_3,C_k^3) and ex(n,K3,Pk3)\operatorname{ex}(n,K_3,P_k^3) when kk is odd, while H+(n,2,k12+1)H^+(n,2,\lfloor\frac{k-1}{2}\rfloor+1) is the unique extremal graph when kk is even. The conjecture extends the paper's results for the edge blow-ups of triangles and three-edge paths to general edge blow-ups of cycles and paths, with the asserted uniqueness expected for sufficiently large nn.

Sources & referencesView supporting material

Primary source

Zequn Lv, Ervin Győri, Zhen He, Nika Salia, Casey Tompkins, Kitti Varga and Xiutao Zhu, “Generalized Turan number for the edge blow-up graph”, arXiv:2210.11914 (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.