Conjecture on clique counts forcing long cycles in bipartite graphs

About 2 years old · traced to

Let GG be a connected bipartite graph with bipartition (X,Y)(X,Y). Suppose

∣X∣=n≤∣Y∣=b,|X|=n\le |Y|=b,

let h=⌊n−k2⌋h=\left\lfloor\frac{n-k}{2}\right\rfloor, and assume that δ(G)≥r≥1\delta(G)\ge r\ge 1, where n≥2k+2rn\ge 2k+2r and k∈Zk\in\mathbb{Z}. For positive integers ss and tt, write N(Ks,t,G)N(K_{s,t},G) for the number of copies of Ks,tK_{s,t} in GG. Clique-count long-cycle conjecture. If

N(Ks,t,G)>{max⁡{fs,t(b,n,n−k,r),fs,s(b,n,n−k,h)},s=t,max⁡{fs,t(b,n,n−k,r)+ft,s(b,n,n−k,r),fs,t(b,n,n−k,h)+ft,s(b,n,n−k,h)},s≠t,N(K_{s,t},G)>\begin{cases}\max\{f_{s,t}(b,n,n-k,r),f_{s,s}(b,n,n-k,h)\},&s=t,\\[2pt]\max\{f_{s,t}(b,n,n-k,r)+f_{t,s}(b,n,n-k,r),\\f_{s,t}(b,n,n-k,h)+f_{t,s}(b,n,n-k,h)\},&s\ne t,\end{cases}

then GG contains a cycle of length 2n−2k2n-2k. This conjecture proposes a clique-count extremal condition for forcing a cycle of the specified length in a not necessarily balanced bipartite graph; the supplied excerpt gives no resolution or further context for the functions fs,tf_{s,t}, so the claim remains open here.

References

Primary source

Changchang Dong, Mei Lu, Jixiang Meng and Bo Ning, “The generalized Tur'an number of long cycles in graphs and bipartite graphs”, arXiv:2406.17371 (2024).

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.