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

At least 3 years old · documented by

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(n−t+1)T_p(n-t+1) be the balanced pp-partite complete graph on n−t+1n-t+1 vertices, let

H(n,p,t)=Kt−1+Tp(n−t+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(n−t+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 k≥4k\geq 4 and nn is sufficiently large, H(n,2,⌊k−12⌋+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,⌊k−12⌋+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.

References

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.