Empty-intersection conjecture for copies of complete graphs above the Turán threshold

About 6 years old · traced to

Let V1,V2,…,Vk−1V_1,V_2,\ldots,V_{k-1} be the vertex classes of the balanced Turán graph Tk−1(n)T_{k-1}(n), with sizes satisfying ⌈n2⌉≥∣V1∣≥⋯≥∣Vk−1∣≥⌊n2⌋\left\lceil\frac n2\right\rceil\geq |V_1|\geq\cdots\geq |V_{k-1}|\geq\left\lfloor\frac n2\right\rfloor and ∑i∣Vi∣=n\sum_i|V_i|=n. Let Tk−1⊏T_{k-1}^{\sqsubset} be obtained from Tk−1(n)T_{k-1}(n) by adding an edge {x,y}\{x,y\} in V1V_1, adding an edge {u,v}\{u,v\} in V2V_2, and deleting the edge {u,x}\{u,x\}. Empty-intersection conjecture. If a graph on nn vertices has tk−1(n)+1t_{k-1}(n)+1 edges and the copies of KkK_k have empty intersection, then the number of copies of KkK_k is at least the number in Tk−1⊏T_{k-1}^{\sqsubset}, namely

(∣V2∣−1)∣V3∣⋅∣V4∣⋯∣Vk−1∣+(∣V1∣−1)∣V3∣⋅∣V4∣⋯∣Vk−1∣=(∣V1∣+∣V2∣−2)∣V3∣⋅∣V4∣⋯∣Vk−1∣.(|V_2|-1)|V_3|\cdot|V_4|\cdots|V_{k-1}|+(|V_1|-1)|V_3|\cdot|V_4|\cdots|V_{k-1}|=(|V_1|+|V_2|-2)|V_3|\cdot|V_4|\cdots|V_{k-1}|.

This would generalize the paper's theorem for triangles, but the source gives no resolution and presents it as an open problem.

References

Primary source

Chuanqi Xiao and Gyula O. H. Katona, “The number of triangles is more when they have no common vertex”, arXiv:2003.04450 (2020).

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.